On obfuscating point functions

ABSTRACT

We investigate the possibility of obfuscating point functions in the framework of Barak et al. from Crypto '01. A point function is a Boolean function that assumes the value 1 at exactly one point. Our main results are as follows:We provide a simple construction of efficient obfuscators for point functions for a slightly relaxed notion of obfuscation, for which obfuscating general circuits is nonetheless impossible. Our construction relies on the existence of a very strong one-way permutation, and yields the first non-trivial obfuscator under general assumptions in the standard model. We also obtain obfuscators for point functions with multi-bit output and for prefix matching.Our assumption is that there is a one-way permutation wherein any polynomial-sized circuit inverts the permutation on at most a polynomial number of inputs. We show that a similar assumption is in fact necessary, and that our assumption holds relative to a random permutation oracle.Finally, we establish two impossibility results which indicate that the limitations on our construction, namely simulating only adversaries with single-bit output and using nonuniform advice in our simulator, are in some sense inherent.Previous work gave negative results for the general class of circuits (Barak et al., Crypto '01) and positive results in the random oracle model (Lynn et al., Eurocrypt '04) or under non-standard number-theoretic assumptions (Canetti, Crypto '97). This work represents the first effort to bridge the gap between the two for a natural class of functionalities.

REFERENCES

• 1: Boaz Barak , Oded Goldreich , Russell Impagliazzo , Steven Rudich , Amit Sahai , Salil P. Vadhan , Ke Yang, On the (Im)possibility of Obfuscating Programs, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.1-18, August 19-23, 2001
• 2: 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]
• 3: Ran Canetti, Towards Realizing Random Oracles: Hash Functions That Hide All Partial Information, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.455-469, August 17-21, 1997
• 4: Ran Canetti , Oded Goldreich , Shai Halevi, The random oracle methodology, revisited (preliminary version), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.209-218, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276741]
• 5: Ran Canetti , Daniele Micciancio , Omer Reingold, Perfectly one-way probabilistic hash functions (preliminary version), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.131-140, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276721]
• 6: Yevgeniy Dodis , Adam Smith, Correcting errors without leaking partial information, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060688]
• 7: Cynthia Dwork , Moni Naor , Amit Sahai, Concurrent zero-knowledge, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.409-418, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276853]
• 8: R. Gennaro , L. Trevisan, Lower bounds on the efficiency of generic cryptographic constructions, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.305, November 12-14, 2000
• 9: Oded Goldreich, Foundations of Cryptography: Basic Tools, Cambridge University Press, New York, NY, 2000
• 10: Oded Goldreich , Hugo Krawczyk, On the Composition of Zero-Knowledge Proof Systems, SIAM Journal on Computing, v.25 n.1, p.169-192, Feb. 1996 [doi>10.1137/S0097539791220688]
• 11: O. Goldreich , L. A. Levin, A hard-core predicate for all one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.25-32, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73010]
• 12: Nathan Linial , Yishay Mansour , Noam Nisan, Constant depth circuits, Fourier transform, and learnability, Journal of the ACM (JACM), v.40 n.3, p.607-620, July 1993 [doi>10.1145/174130.174138]
• 13: A. Lubotzky, R. Philips, and P. Sarnak. Ramanujan graphs. Combinatorica, 8(3):261--277, 1988.
• 14: Michael George Luby , Luby Michael, Pseudorandomness and Cryptographic Applications, Princeton University Press, Princeton, NJ, 1994
• 15: B. Lynn, M. Prabhakaran, and A. Sahai. Positive results and techniques for obfuscation. In Proc. Eurocrypt '04, 2004.
• 16: Jesper Buus Nielsen, Separating Random Oracle Proofs from Complexity Theoretic Proofs: The Non-committing Encryption Case, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.111-126, August 18-22, 2002
• 17: David Wagner , Ian Goldberg, Proofs of Security for the Unix Password Hashing Algorithm, Proceedings of the 6th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.560-572, December 03-07, 2000
• 18: A. Yao. Theory and applications of trapdoor functions. In Proc. 23rd FOCS, 1982.

INDEX TERMS

Primary Classification:
  E. Data
  E.0 GENERAL

General Terms:
Security, Theory

Keywords:
obfuscation