Shielding circuits with groups

ABSTRACT

We show how to efficiently compile any given circuit C into a leakage-resistant circuit C' such that any function on the wires of C' that leaks information during a computation C'(x) yields advantage in computing the product of |C'|^Ω(1) elements of the alternating group A_u. In combination with new compression bounds for A_u products, also obtained here, C' withstands leakage from virtually any class of functions against which average-case lower bounds are known. This includes communication protocols, and AC⁰ circuits augmented with few arbitrary symmetric gates. If NC¹ ' TC⁰ then then the construction resists TC⁰ leakage as well. We also conjecture that our construction resists NC¹ leakage. In addition, we extend the construction to the multi-query setting by relying on a simple secure hardware component. We build on Barrington's theorem [JCSS '89] and on the previous leakage-resistant constructions by Ishai et al. [Crypto '03] and Faust et al. [Eurocrypt '10]. Our construction exploits properties of A_u beyond what is sufficient for Barrington's theorem.

References

1. Eric Allender, Vikraman Arvind, and Fengming Wang. Uniform derandomization from pathetic lower bounds. In Workshop on Randomization and Computation (RANDOM), pages 380--393, 2010.
2. Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. Cryptography in NC$^0$. SIAM J. on Computing, 36(4):845--888, 2006.
3. Eric Allender. The division breakthroughs. Bulletin of the EATCS, 74:61--77, 2001.
4. David A. Mix Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in NC$^1$. J. of Computer and System Sciences, 38(1):150--164, 1989.
5. }BarakGIRSVY01Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, and Ke Yang. On the (im)possibility of obfuscating programs. In Int. Cryptology Conf. (CRYPTO), pages 1--18, 2001.
6. László Babai, Noam Nisan, and Márió Szegedy. Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs. J. of Computer and System Sciences, 45(2):204--232, 1992.
7. Ashok K. Chandra, Merrick L. Furst, and Richard J. Lipton. Multi-party protocols. In 15th ACM Symp. on the Theory of Computing (STOC), pages 94--99, 1983.
8. Jin-yi Cai and Richard J. Lipton. Subquadratic simulations of balanced formulae by branching programs. SIAM J. on Computing, 23(3):563--572, 1994.
9. Richard Cleve. Towards optimal simulations of formulas by bounded-width programs. Computational Complexity, 1:91--105, 1991.
10. Stephen A. Cook and Pierre McKenzie. Problems complete for deterministic logarithmic space. J. Algorithms, 8(3):385--394, 1987.
11. Fan R. K. Chung and Prasad Tetali. Communication complexity and quasi randomness. SIAM J. Discrete Math., 6(1):110--123, 1993.
12. Stefan Dziembowski and Sebastian Faust. Leakage-resilient circuits without computational assumptions. In Theory of Cryptography Conf. (TCC), pages 230--247, 2012.
13. Bella Dubrov and Yuval Ishai. On the randomness complexity of efficient sampling. In 38th ACM Symposium on Theory of Computing (STOC), pages 711--720, 2006.
14. Andrew Drucker. New limits to classical and quantum instance compression. In IEEE Symp. on Foundations of Computer Science (FOCS), 2012.
15. Uriel Feige, Joe Kilian, and Moni Naor. A minimal model for secure computation (extended abstract). In ACM Symp. on the Theory of Computing (STOC), pages 554--563, 1994.
16. }FaustRRTV10Sebastian Faust, Tal Rabin, Leonid Reyzin, Eran Tromer, and Vinod Vaikuntanathan. Protecting circuits from leakage: the computationally-bounded and noisy cases. In Int. Conf. on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), pages 135--156, 2010.
17. }GoldwasserGHKR08Shafi Goldwasser, Dan Gutfreund, Alexander Healy, Tali Kaufman, and Guy Rothblum. A (de)constructive approach to program checking. In 40th ACM Symposium on Theory of Computing (STOC), pages 143--152, 2008.
18. Shafi Goldwasser and Guy N. Rothblum. Securing computation against continuous leakage. In Int. Cryptology Conf. (CRYPTO), pages 59--79, 2010.
19. Shafi Goldwasser and Guy N. Rothblum. How to compute in the presence of leakage. In IEEE Symp. on Foundations of Computer Science (FOCS), 2012.
20. Danny Harnik and Moni Naor. On the compressibility of NP instances and cryptographic applications. SIAM J. on Computing, 39(5):1667--1713, 2010.
21. Derek Holt and W. Plesken. Perfect Groups. Oxford Mathematical Monographs. Clarendon Press, 1989.
22. Yuval Ishai, Amit Sahai, and David Wagner. Private circuits: Securing hardware against probing attacks. In Int. Cryptology Conf. (CRYPTO), pages 463--481, 2003.
23. Ali Juma and Yevgeniy Vahlis. Protecting cryptographic keys against continual leakage. In Int. Cryptology Conf. (CRYPTO), pages 41--58, 2010.
24. Joe Kilian. Founding cryptography on oblivious transfer. In ACM Symp. on the Theory of Computing (STOC), pages 20--31, 1988.
25. Hans Kurzweil and Bernd Stellmacher. The Theory of Finite Groups: An Introduction. Springer, 2004.
26. Silvio Micali and Leonid Reyzin. Physically observable cryptography. In Theory of Cryptography Conf. (TCC), pages 278--296, 2004.
27. Noam Nisan. The communication complexity of threshold gates. In Combinatorics, Paul Erd\Hos is Eighty, number 1 in Bolyai Society Mathematical Studies, pages 301--315, 1993.
28. Ran Raz. The BNS-Chung criterion for multi-party communication complexity. Comput. Complexity, 9(2):113--122, 2000.
29. Guy N. Rothblum. How to compute under AC$^0$ leakage without secure hardware. In Int. Cryptology Conf. (CRYPTO), pages 552--569, 2012.
30. Emanuele Viola. Pseudorandom bits for constant-depth circuits with few arbitrary symmetric gates. SIAM J. on Computing, 36(5):1387--1403, 2007.
31. Emanuele Viola. Selected results in additive combinatorics: An exposition. Theory of Computing Library, Graduate Surveys series, 3:1--15, 2011.
32. Emanuele Viola and Avi Wigderson. Norms, XOR lemmas, and lower bounds for GF(2) polynomials and multiparty protocols. Theory of Computing, 4:137--168, 2008.

Index Terms

• Computer systems organization

  • Architectures

    • Parallel architectures

      • Cellular architectures

• Hardware

  • Emerging technologies

    • Quantum technologies

      • Quantum dots and cellular automata

• Theory of computation

  • Models of computation