Circuits resilient to additive attacks with applications to secure computation

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 • C of size O(|C|) that is fault-tolerant in the following sense. For any additive attack on the wires of C, its effect on the output of C 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 C. We use this methodology to simplify feasibility results and attain efficiency improvements in several standard MPC models.

References

1. S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and hardness of approximation problems. In FOCS, pages 14--23, 1992.
2. M. Ben-Or, C. Crépeau, D. Gottesman, A. Hassidim, and A. Smith. Secure multiparty quantum computation with (only) a strict honest majority. In FOCS, pages 249--260, 2006.
3. M. Ben-Or, S. Goldwasser, and A. Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In STOC, pages 1--10, 1988.
4. E. Ben-Sasson, S. Fehr, and R. Ostrovsky. Near-linear unconditionally-secure multiparty computation with a dishonest minority. In CRYPTO, pages 663--680, 2012.
5. R. Bendlin, I. Damgård, C. Orlandi, and S. Zakarias. Semi-homomorphic encryption and multiparty computation. In EUROCRYPT, pages 169--188, 2011.
6. D. Chaum, C. Crépeau, and I. Damgård. Multiparty unconditionally secure protocols (extended abstract). In STOC, pages 11--19, 1988.
7. R. Cramer, Y. Dodis, S. Fehr, C. Padró, and D. Wichs. Detection of algebraic manipulation with applications to robust secret sharing and fuzzy extractors. In EUROCRYPT, pages 471--488, 2008.
8. D. Dachman-Soled and Y. T. Kalai. Securing circuits against constant-rate tampering. In CRYPTO, pages 533--551, 2012.
9. D. Dachman-Soled and Y. T. Kalai. Securing circuits and protocols against 1/poly(k) tampering rate. In TCC, pages 540--565, 2014.
10. I. Damgård, Y. Ishai, and M. Kroigaard. Perfectly secure multiparty computation and the computational overhead of cryptography. In EUROCRYPT, pages 445--465, 2010.
11. I. Damgård and J. B. Nielsen. Scalable and unconditionally secure multiparty computation. In CRYPTO, pages 572--590, 2007.
12. R. Dobrushin and E. Ortyukov. Upper bound on the redundancy of self-correcting arrangements of unreliable functional elements. Problems of Information Transmission, 23(2):203--218, 1977.
13. S. Faust, K. Pietrzak, and D. Venturi. Tamper-proof circuits: How to trade leakage for tamper-resilience. In ICALP, pages 391--402, 2011.
14. A. Gál and M. Szegedy. Fault tolerant circuits and probabilistically checkable proofs. In Structure in Complexity Theory Conference, pages 65--73, 1995.
15. R. Gennaro, A. Lysyanskaya, T. Malkin, S. Micali, and T. Rabin. Algorithmic tamper-proof (ATP) security: Theoretical foundations for security against hardware tampering. In TCC, pages 258--277, 2004.
16. O. Goldreich. The Foundations of Cryptography Volume 2, Basic Applications. Cambridge University Press, 2004.
17. O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game or a completeness theorem for protocols with honest majority. In STOC, pages 218--229, 1987.
18. Y. Ishai, E. Kushilevitz, S. Meldgaard, C. Orlandi, and A. Paskin-Cherniavsky. On the power of correlated randomness in secure computation. In TCC, pages 600--620, 2013.
19. Y. Ishai, E. Kushilevitz, R. Ostrovsky, M. Prabhakaran, and A. Sahai. Efficient non-interactive secure computation. In EUROCRYPT, pages 406--425, 2011.
20. Y. Ishai, M. Prabhakaran, and A. Sahai. Founding cryptography on oblivious transfer -- efficiently. In CRYPTO, pages 572--591, 2008.
21. Y. Ishai, M. Prabhakaran, and A. Sahai. Secure arithmetic computation with no honest majority. In TCC, pages 294--314, 2009.
22. Y. Ishai, M. Prabhakaran, A. Sahai, and D. Wagner. Private circuits ii: Keeping secrets in tamperable circuits. In EUROCRYPT, pages 308--327, 2006.
23. Y. Ishai, A. Sahai, and D. Wagner. Private circuits: Securing hardware against probing attacks. In CRYPTO, pages 463--481, 2003.
24. Y. T. Kalai, B. Kanukurthi, and A. Sahai. Cryptography with tamperable and leaky memory. In CRYPTO, pages 373--390, 2011.
25. Y. T. Kalai, A. B. Lewko, and A. Rao. Formulas resilient to short-circuit errors. In FOCS, pages 490--499, 2012.
26. M. G. Karpovsky and P. Nagvajara. Optimal codes for minimax criterion on error detection. IEEE Transactions on Information Theory, 35(6):1299--1305, 1989.
27. J. Kilian. Founding cryptography on oblivious transfer. In STOC, pages 20--31, 1988.
28. D. J. Kleitman, F. T. Leighton, and Y. Ma. On the design of reliable boolean circuits that contain partially unreliable gates. In FOCS, pages 332--346, 1994.
29. F.-H. Liu and A. Lysyanskaya. Tamper and leakage resilience in the split-state model. In CRYPTO, pages 517--532, 2012.
30. M. Naor and B. Pinkas. Oblivious polynomial evaluation. SIAM J. Comput., 35(5):1254--1281, 2006.
31. N. Pippenger. On networks of noisy gates. In FOCS, pages 30--38, 1985.
32. T. Rabin and M. Ben-Or. Verifiable secret sharing and multiparty protocols with honest majority (extended abstract). In STOC, pages 73--85, 1989.
33. J. von Neumann. Probabilistic logics and synthesis of reliable organisms from unreliable components. Automata Studies, 34:43--98, 1956.
34. A. C.-C. Yao. How to generate and exchange secrets (extended abstract). In FOCS, pages 162--167, 1986.

Index Terms

• Theory of computation

  • Models of computation

    • Interactive computation