Circuits resilient to additive attacks with applications to secure computation

Daniel Genkin, Yuval Ishai, Manoj M. Prabhakaran, Amit Sahai, Eran Tromer

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We study the question of protecting arithmetic circuits against additive attacks, which can add an arbitrary fixed value to each wire in the circuit. This extends the notion of algebraic manipulation detection (AMD) codes, which protect information against additive attacks, to that of AMD circuits which protect computation. We present a construction of such AMD circuits: any arithmetic circuit C over a finite field F can be converted into a functionally-equivalent randomized arithmetic circuit Ĉ of size O(|C|) that is fault-tolerant in the following sense. For any additive attack on the wires of Ĉ its effect on the output of Ĉ can be simulated, up to O(|C|/|F|) statistical distance, by an additive attack on just the input and output. Given a small tamper-proof encoder/decoder for AMD codes, the input and output can be protected as well. We also give an alternative construction, applicable to small fields (for example, to protect Boolean circuits against wire-toggling attacks). It uses a small tamper-proof decoder to ensure that, except with negligible failure probability, either the output is correct or tampering is detected. Our study of AMD circuits is motivated by simplifying and improving protocols for secure multiparty computation (MPC). Typically, securing MPC protocols against active adversaries is much more difficult than securing them against passive adversaries. We observe that in simple passive-secure MPC protocols for circuit evaluation, the effect of any active adversary corresponds precisely to an additive attack on the original circuit's wires. Thus, to securely evaluate a circuit C in the presence of active adversaries, it suffices to apply the passive-secure protocol to Ĉ. We use this methodology to simplify feasibility results and attain efficiency improvements in several standard MPC models

Original languageEnglish (US)
Title of host publicationSTOC 2014 - Proceedings of the 2014 ACM Symposium on Theory of Computing
PublisherAssociation for Computing Machinery
Pages495-504
Number of pages10
ISBN (Print)9781450327107
DOIs
StatePublished - Jan 1 2014
Event4th Annual ACM Symposium on Theory of Computing, STOC 2014 - New York, NY, United States
Duration: May 31 2014Jun 3 2014

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other4th Annual ACM Symposium on Theory of Computing, STOC 2014
CountryUnited States
CityNew York, NY
Period5/31/146/3/14

Keywords

  • Cryptography
  • Fault tolerant circuits
  • Secure computation

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Circuits resilient to additive attacks with applications to secure computation'. Together they form a unique fingerprint.

  • Cite this

    Genkin, D., Ishai, Y., Prabhakaran, M. M., Sahai, A., & Tromer, E. (2014). Circuits resilient to additive attacks with applications to secure computation. In STOC 2014 - Proceedings of the 2014 ACM Symposium on Theory of Computing (pp. 495-504). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/2591796.2591861