On basing one-way functions on NP-hardness

ABSTRACT

We consider the possibility of basing one-way functions on NP-Hardness; that is, we study possible reductions from a worst-case decision problem to the task of average-case inverting a polynomial-time computable function f. Our main findings are the following two negative results:

• If given y one can efficiently compute |f^-1(y)| then the existence of a (randomized) reduction of NP to the task of inverting f implies that coNP ⊆ AM. Thus, it follows that such reductions cannot exist unless coNP ⊆ AM.
• For any function f, the existence of a (randomized) non-adaptive reduction of NP to the task of average-case inverting f implies that coNP ⊆ AM.

Our work builds upon and improves on the previous works of Feigenbaum and Fortnow (SIAM Journal on Computing, 1993) and Bogdanov and Trevisan (44th FOCS, 2003), while capitalizing on the additional "computational structure" of the search problem associated with the task of inverting polynomial-time computable functions. We believe that our results illustrate the gain of directly studying the context of one-way functions rather than inferring results for it from a the general study of worst-case to average-case reductions.

REFERENCES

• 1: D. Aharonov and O. Regev. Lattice Problems in NP intersect coNP. In 45th FOCS, 2004.
• 2: W. Aiello and J. Hastad. Perfect Zero-Knowledge Languages can be Recognized in Two Rounds. In 28th FOCS, pages 439--448, 1987.
• 3: M. Ajtai, Generating hard instances of lattice problems (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.99-108, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237838]
• 4: A. Akavia, O. Goldreich, S. Goldwasser, and D. Moshkovitz. On Basing One-Way Functions on NP-Hardness. In preparations, to be posted on ECCC.
• 5: L Babai, Trading group theory for randomness, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.421-429, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22192]
• 6: László Babai , Shlomo Moran, Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity class, Journal of Computer and System Sciences, v.36 n.2, p.254-276, April 1988 [doi>10.1016/0022-0000(88)90028-1]
• 7: László Babai , Sophie Laplante, Stronger Separations for Random-Self-Reducibility, Rounds, and Advice, Proceedings of the Fourteenth Annual IEEE Conference on Computational Complexity, p.98, May 04-06, 1999
• 8: B. Barak (Machtey Award Co-winner), How to Go Beyond the Black-Box Simulation Barrier, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.106, October 14-17, 2001
• 9: Boaz Barak, Constant-Round Coin-Tossing with a Man in the Middle or Realizing the Shared Random String Model, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.345-355, November 16-19, 2002
• 10: Shai Ben-David , Benny Chor , Oded Goldreich , Michael Luby, On the theory of average case complexity, Journal of Computer and System Sciences, v.44 n.2, p.193-219, April 1992 [doi>10.1016/0022-0000(92)90019-F]
• 11: 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]
• 12: Andrej Bogdanov , Luca Trevisan, On Worst-Case to Average-Case Reductions for NP Problems, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.308, October 11-14, 2003
• 13: G. Brassard. Relativized Cryptography. In 20th FOCS, pages 383--391, 1979.
• 14: Giovanni Di Crescenzo , Russell Impagliazzo, Security-preserving hardness-amplification for any regular one-way function, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.169-178, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301296]
• 15: Shimon Even , Alan L. Selman , Yacov Yacobi, The complexity of promise problems with applications to public-key cryptography, Information and Control, v.61 n.2, p.159-173, May 1984 [doi>10.1016/S0019-9958(84)80056-X]
• 16: Joan Feigenbaum , Lance Fortnow, Random-self-reducibility of complete sets, SIAM Journal on Computing, v.22 n.5, p.994-1005, Oct. 1993 [doi>10.1137/0222061]
• 17: Joan Feigenbaum , Lance Fortnow , Carsten Lund , Daniel Spielman, The power of adaptiveness and additional queries in random-self-reductions, Computational Complexity, v.4 n.2, p.158-174, April 1994 [doi>10.1007/BF01202287]
• 18: L. Fortnow, The complexity of perfect zero-knowledge, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.204-209, January 1987, New York, New York, United States [doi>10.1145/28395.28418]
• 19: Oded Goldreich, Foundations of Cryptography: Basic Tools, Cambridge University Press, New York, NY, 2000
• 20: O. Goldreich, R. Impagliazzo, L.A. Levin, R. Venkatesan, and D. Zuckerman. Security Preserving Amplification of Hardness. In 31st FOCS, pages 318--326, 1990.
• 21: Oded Goldreich , Hugo Krawczyk , Michael Luby, On the existence of pseudorandom generators, SIAM Journal on Computing, v.22 n.6, p.1163-1175, Dec. 1993 [doi>10.1137/0222069]
• 22: Oded Goldreich , Salil Vadhan , Avi Wigderson, On interactive proofs with a laconic prover, Computational Complexity, v.11 n.1/2, p.1-53, January 2003 [doi>10.1007/s00037-002-0169-0]
• 23: S Goldwasser , M Sipser, Private coins versus public coins in interactive proof systems, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.59-68, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12137]
• 24: I. Haitner, O. Horvitz, J. Katz, C.Y. Koo, R. Morselli, and R. Shaltiel. Reducing complexity assumptions for statistically-hiding commitment. In Eurocrypt, Springer, LNCS3494, pages 58--77, 2005.
• 25: Edith Hemaspaandra , Ashish V. Naik , Mitsunori Ogihara , Alan L. Selman, P-selective sets and reducing search to decision vs. self-reducibility, Journal of Computer and System Sciences, v.53 n.2, p.194-209, Oct. 1996 [doi>10.1006/jcss.1996.0061]
• 26: Johan HÅstad , Russell Impagliazzo , Leonid A. Levin , Michael Luby, A Pseudorandom Generator from any One-way Function, SIAM Journal on Computing, v.28 n.4, p.1364-1396, Aug. 1999 [doi>10.1137/S0097539793244708]
• 27: R. Impagliazzo and L.A. Levin. No Better Ways to Generate Hard NP Instances than Picking Uniformly at Random. In 31st FOCS, 1990, pages 812--821.
• 28: Jonathan Katz , Luca Trevisan, On the efficiency of local decoding procedures for error-correcting codes, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.80-86, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335315]
• 29: S. Micali, editor. Advances in Computing Research: a research annual, Vol. 5 (Randomness and Computation), 1989.
• 30: Daniele Micciancio , Oded Regev, Worst-Case to Average-Case Reductions Based on Gaussian Measures, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.372-381, October 17-19, 2004 [doi>10.1109/FOCS.2004.72]
• 31: A.C. Yao. Theory and Application of Trapdoor Functions. In 23rd FOCS, pages 80--91, 1982.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Complexity hierarchies

General Terms:
Theory

Keywords:
adaptive versus non-adaptive machines, average-case complexity, interactive proof systems, one-way functions, reductions