Cryptography with constant computational overhead

ABSTRACT

Current constructions of cryptographic primitives typically involve a large multiplicative computational overhead that grows with the desired level of security. We explore the possibility of implementing basic cryptographic primitives, such as encryption, authentication, signatures, and secure two-party computation, while incurring only a constant computational overhead compared to insecure implementations of the same tasks. Here we make the usual security requirement that the advantage of any polynomial-time attacker must be negligible in the input length.

We obtain affirmative answers to this question for most central cryptographic primitives under plausible, albeit sometimes nonstandard, intractability assumptions. We start by showing that pairwise-independent hash functions can be computed by linear-size circuits, disproving a conjecture of Mansour, Nisan, and Tiwari (STOC 1990). This construction does not rely on any unproven assumptions and is of independent interest. Our hash functions can be used to construct message authentication schemes with constant overhead from any one-way function. Under an intractability assumption that generalizes a previous assumption of Alekhnovich (FOCS 2003), we get (public and private key) encryption schemes with constant overhead. Using an exponentially strong version of the previous assumption, we get signature schemes of similar complexity. Assuming the existence of pseudorandom generators in NC z with polynomial stretch together with the existence of an (arbitrary) oblivious transfer protocol, we get similar results for the seemingly very complex task of secure two-party computation. More concretely, we get general protocols for secure two-party computation in the semi-honest model in which the two parties can be implemented by circuits whose size is a constant multiple of the size s of the circuit to be evaluated. In the malicious model, we get protocols whose communication complexity is a constant multiple of s and whose computational complexity is slightly super-linear in s. For natural relaxations of security in the malicious model that are still meaningful in practice, we can also keep the computational complexity linear in s. These results extend to the case of a constant number of parties, where an arbitrary subset of the parties can be corrupted.

Our protocols rely on non-black-box techniques, and suggest the intriguing possibility that the ultimate efficiency in this area of cryptography can be obtained via such techniques.

REFERENCES

• 1: Michael Alekhnovich, More on Average Case vs Approximation Complexity, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.298, October 11-14, 2003
• 2: . Alon, J. Bruck, J. Naor, M. Naor, and R. M. Roth. Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs. IEEE Transactions on Information Theory 38(2) (1992).
• 3: Benny Applebaum , Yuval Ishai , Eyal Kushilevitz, Cryptography in $NC^0$, SIAM Journal on Computing, v.36 n.4, p.845-888, December 2006 [doi>10.1137/S0097539705446950]
• 4: Benny Applebaum , Yuval Ishai , Eyal Kushilevitz, COMPUTATIONALLY PRIVATE RANDOMIZING POLYNOMIALS AND THEIR APPLICATIONS, Computational Complexity, v.15 n.2, p.115-162, June 2006 [doi>10.1007/s00037-006-0211-8]
• 5: B. Applebaum, Y. Ishai, and E. Kushilevitz. On pseudorandom generators with linear stretch in mathrmNC0. In Proc. 10th Random, 2006.
• 6: B. Applebaum, Y. Ishai, and E. Kushilevitz. Cryptography with Constant Input Locality. In Proc. of Crypto, 2007.
• 7: Y. Aumann and Yehuda Lindell. Security Against Covert Adversaries: Efficient Protocols for Realistic Adversaries. In Proc. TCC 2007, pages 137--156.
• 8: Donald Beaver, Precomputing Oblivious Transfer, Proceedings of the 15th Annual International Cryptology Conference on Advances in Cryptology, p.97-109, August 27-31, 1995
• 9: Donald Beaver, Correlated pseudorandomness and the complexity of private computations, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.479-488, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237996]
• 10: Michael Ben-Or , Shafi Goldwasser , Avi Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.1-10, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62213]
• 11: Avrim Blum , Adam Kalai , Hal Wasserman, Noise-tolerant learning, the parity problem, and the statistical query model, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.435-440, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335355]
• 12: Manuel Blum , Silvio Micali, How to generate cryptographically strong sequences of pseudo-random bits, SIAM Journal on Computing, v.13 n.4, p.850-864, Nov. 1984 [doi>10.1137/0213053]
• 13: . L. Bordewijk. Inter-reciprocity applied to electrical networks. Applied Scientific Research B: Electrophysics, Acoustics, Optics, Mathematical Methods, 6: 1--74, 1956.
• 14: R. Canetti. Security and composition of multipartycryptographic protocols. In J. of Cryptology, 13(1), 2000.
• 15: R. Canetti, Y. Dodis, S. Halevi, E. Kushilevitz, and A. Sahai. Exposure-Resilient Functions and All-or-Nothing Transforms. In Proc EUROCRYPT 2000, pages 453--469.
• 16: Michael Capalbo , Omer Reingold , Salil Vadhan , Avi Wigderson, Randomness conductors and constant-degree lossless expanders, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510003]
• 17: L. Carter and M. N. Wegman. Universal Classes of Hash Functions. J. Comput. Syst. Sci. 18(2): 143--154 (1979).
• 18: Benny Chor , Oded Goldreich , Johan Hasted , Joel Freidmann , Steven Rudich , Roman Smolensky, The bit extraction problem or t-resilient functions, Proceedings of the 26th Annual Symposium on Foundations of Computer Science (sfcs 1985), p.396-407, October 21-23, 1985 [doi>10.1109/SFCS.1985.55]
• 19: Mary Cryan , Peter Bro Miltersen, On Pseudorandom Generators in NC, Proceedings of the 26th International Symposium on Mathematical Foundations of Computer Science, p.272-284, August 27-31, 2001
• 20: R. L. Dobrushin, S. I. Gelfand, and M. S. Pinsker. On complexity of coding. In Proc. 2nd Internat. Symp. on Information Theory, pages 174-184, 1973.
• 21: Danny Dolev , Cynthia Dwork , Moni Naor, Nonmalleable Cryptography, SIAM Journal on Computing, v.30 n.2, p.391-437, 2000 [doi>10.1137/S0097539795291562]
• 22: Shimon Even , Oded Goldreich , Abraham Lempel, A randomized protocol for signing contracts, Communications of the ACM, v.28 n.6, p.637-647, June 1985 [doi>10.1145/3812.3818]
• 23: Uri Feige , Joe Killian , Moni Naor, A minimal model for secure computation (extended abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.554-563, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195408]
• 24: M. J. Freedman, K. Nissim, and B. Pinkas. Efficient Private Matching and Set Intersection. In EUROCRYPT 2004, pages 1-19.
• 25: Oded Goldreich, Foundations of Cryptography: Basic Tools, Cambridge University Press, New York, NY, 2000
• 26: Oded Goldreich, Foundations of Cryptography: Volume 2, Basic Applications, Cambridge University Press, New York, NY, 2004
• 27: O. Goldreich. Candidate one-way functions based on expander graphs. Electronic Colloquium on Computational Complexity (ECCC), 7(090), 2000.
• 28: Oded Goldreich , Shafi Goldwasser , Silvio Micali, How to construct random functions, Journal of the ACM (JACM), v.33 n.4, p.792-807, Oct. 1986 [doi>10.1145/6490.6503]
• 29: Shafi Goldwasser , Silvio Micali , Po Tong, Why and how to establish a private code on a public network, Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982), p.134-144, November 03-05, 1982
• 30: Oded Goldreich , Silvio Micali , Avi Wigderson, How to prove all NP-statements in zero-knowledge, and a methodology of cryptographic protocol design, Proceedings on Advances in cryptology---CRYPTO '86, p.171-185, January 1987, Santa Barbara, California, United States
• 31: Oded Goldreich , Ronen Vainish, How to Solve any Protocol Problem - An Efficiency Improvement, A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, p.73-86, August 16-20, 1987
• 32: V. Guruswami , P. Indyk, Expander-Based Constructions of Efficiently Decodable Codes, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.658, October 14-17, 2001
• 33: R. Impagliazzo , L. A. Levin , M. Luby, Pseudo-random generation from one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.12-24, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73009]
• 34: Yuval Ishai , Eyal Kushilevitz, Perfect Constant-Round Secure Computation via Perfect Randomizing Polynomials, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.244-256, July 08-13, 2002
• 35: Yuval Ishai , Eyal Kushilevitz , Rafail Ostrovsky , Amit Sahai, Zero-knowledge from secure multiparty computation, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250794]
• 36: Joe Kilian, Founding crytpography on oblivious transfer, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.20-31, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62215]
• 37: V. Lyubashevsky. The Parity Problem in the Presence of Noise, Decoding Random Linear Codes, and the Subset Sum Problem. In Proc. APPROX-RANDOM 2005, pages 378--389.
• 38: Y. Mansour , N. Nisan , P. Tiwari, The computational complexity of universal hashing, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.235-243, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100246]
• 39: Elchanan Mossel , Amir Shpilka , Luca Trevisan, On e-Biased Generators in NC0, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.136, October 11-14, 2003
• 40: Joseph (Seffi) Naor , Moni Naor, Small-bias probability spaces: efficient constructions and applications, SIAM Journal on Computing, v.22 n.4, p.838-856, Aug. 1993 [doi>10.1137/0222053]
• 41: Moni Naor , Kobbi Nissim, Communication preserving protocols for secure function evaluation, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.590-599, July 2001, Hersonissos, Greece [doi>10.1145/380752.380855]
• 42: M. Naor , M. Yung, Universal one-way hash functions and their cryptographic applications, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.33-43, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73011]
• 43: M.O. Rabin. How to exchange secrets by oblivious transfer. TR-81, Harvard, 1981.
• 44: M. Sipser , D. A. Spielman, Expander codes, Proceedings of the Proceedings 35th Annual Symposium on Foundations of Computer Science, p.566-576, November 20-22, 1994 [doi>10.1109/SFCS.1994.365734]
• 45: W. D. Smith. 1. AES seems weak. 2. Linear time secure cryptography. Cryplology ePrint report 2007/248.
• 46: Daniel A. Spielman, Linear-time encodable and decodable error-correcting codes, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.388-397, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225165]
• 47: Andrew C. Yao, Theory and application of trapdoor functions, Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982), p.80-91, November 03-05, 1982
• 48: Andrew Chi-Chih Yao, How to generate and exchange secrets, Proceedings of the 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), p.162-167, October 27-29, 1986 [doi>10.1109/SFCS.1986.25]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Security, Theory

Keywords:
constant computational overhead, cryptography, universal hashing