Abstract
We consider average-case strengthenings of the traditional assumption that coNP is not contained in AM. Under these assumptions, we rule out generic and potentially non-black-box constructions of various cryptographic primitives (e.g., one-way permutations, collision-resistant hash-functions, constant-round statistically hiding commitments, and constant-round black-box zero-knowledge proofs for NP) from one-way functions, assuming the security reductions are black-box.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Almgren, F., Andersson, G., Granlund, T., Ivansson, L., Ulfberg, S.: How we cracked the code book ciphers (2000) (manuscript), http://codebook.org/codebook_solution.pdf
Akavia, A., Goldreich, O., Goldwasser, S., Moshkovitz, D.: On basing one-way functions on NP-hardness. In: STOC 2006, pp. 701–710 (2006)
Aharonov, D., Regev, O.: Lattice problems in NP cap coNP. J. ACM 52(5), 749–765 (2005)
Barak, B.: How to go beyond the black-box simulation barrier. In: FOCS 2001, vol. 0, pp. 106–115 (2001)
Blum, A., Furst, M., Kearns, M., Lipton, R.: Cryptographic Primitives Based on Hard Learning Problems. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 278–291. Springer, Heidelberg (1994)
Babai, L., Fortnow, L., Lund, C.: Non-deterministic exponential time has two-prover interactive protocols. Computational Complexity 1, 3–40 (1991)
Blum, M., Micali, S.: How to generate cryptographically strong sequences of pseudo-random bits. SIAM Journal on Computing 13(4), 850–864 (1984)
Brassard, G.: Relativized cryptography. IEEE Transactions on Information Theory 29(6), 877–893 (1983)
Bogdanov, A., Trevisan, L.: On worst-case to average-case reductions for np problems. In: FOCS 2003, pp. 308–317 (2003)
Bellare, M., Yung, M.: Certifying permutations: Noninteractive zero-knowledge based on any trapdoor permutation. J. Cryptology 9(3), 149–166 (1996)
Dolev, D., Dwork, C., Naor, M.: Nonmalleable cryptography. SIAM Journal on Computing 30(2), 391–437 (2000)
Damgård, I., Pedersen, T.P., Pfitzmann, B.: Statistical secrecy and multibit commitments. IEEE Transactions on Information Theory 44(3), 1143–1151 (1998)
Daemen, J., Rijmen, V.: The Design of Rijndael. Springer, New York, Inc. (2002)
Feige, U., Kim, J.H., Ofek, E.: Witnesses for non-satisfiability of dense random 3cnf formulas. In: FOCS 2006, pp. 497–508 (2006)
Feige, U., Shamir, A.: Witness indistinguishable and witness hiding protocols. In: STOC 1990, pp. 416–426 (1990)
Goldreich, O., Goldwasser, S.: On the limits of nonapproximability of lattice problems. J. Comput. Syst. Sci. 60(3), 540–563 (2000)
Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. Journal of ACM 33(4), 792–807 (1986)
Goldreich, O., Kahan, A.: How to construct constant-round zero-knowledge proof systems for NP. Journal of Cryptology 9(3), 167–190 (1996)
Goldreich, O., Krawczyk, H.: On the composition of zero-knowledge proof systems. SIAM Journal on Computing 25(1), 169–192 (1996)
Goldwasser, S., Micali, S.: Probabilistic encryption. J. Comput. Syst. Sci. 28(2), 270–299 (1984)
Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity for all languages in np have zero-knowledge proof systems. J. ACM 38(3), 691–729 (1991)
Håstad, J.: Some optimal inapproximability results. J. ACM 48(4), 798–859 (2001)
Haitner, I., Hoch, J.J., Reingold, O., Segev, G.: Finding collisions in interactive protocols - a tight lower bound on the round complexity of statistically-hiding commitments. In: FOCS, pp. 669–679 (2007)
Håstad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. SIAM J. Comput. 28(4), 1364–1396 (1999)
Haitner, I., Mahmoody, M., Xiao, D.: A new sampling protocol and applications to basing cryptographic primitives on the hardness of NP. In: IEEE Conference on Computational Complexity, pp. 76–87 (2010)
Haitner, I., Reingold, O.: Statistically-hiding commitment from any one-way function. In: STOC 2007, pp. 1–10 (2007)
Impagliazzo, R., Rudich, S.: Limits on the Provable Consequences of One-Way Permutations. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 8–26. Springer, Heidelberg (1990)
Miltersen, P.B., Vinodchandran, N.V.: Derandomizing arthur-merlin games using hitting sets. Computational Complexity 14(3), 256–279 (2005)
Naor, M.: Bit commitment using pseudorandomness. J. Cryptology 4(2), 151–158 (1991)
Naor, M., Ostrovsky, R., Venkatesan, R., Yung, M.: Perfect zero-knowledge arguments for p using any one-way permutation. J. Cryptology 11(2), 87–108 (1998)
Nisan, N., Wigderson, A.: Hardness vs randomness. J. Comput. Syst. Sci. 49(2), 149–167 (1994)
Pass, R.: Parallel repetition of zero-knowledge proofs and the possibility of basing cryptography on NP-hardness. In: IEEE Conference on Computational Complexity, pp. 96–110 (2006)
Pass, R., Venkitasubramaniam, M.: Private coins versus public coins in zero-knowledge proofs. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 588–605. Springer, Heidelberg (2010)
Rabin, M.O.: Probabilistic algorithm for testing primality. Journal of Number Theory 12(1), 128–138 (1980)
Simon, D.R.: Findings Collisions on a One-Way Street: Can Secure Hash Functions Be Based on General Assumptions? In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 334–345. Springer, Heidelberg (1998)
Yao, A.C.-C.: Theory and applications of trapdoor functions (extended abstract). In: FOCS 1982, pp. 80–91 (1982)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 International Association for Cryptologic Research
About this paper
Cite this paper
Pass, R., Tseng, WL.D., Venkitasubramaniam, M. (2011). Towards Non-Black-Box Lower Bounds in Cryptography. In: Ishai, Y. (eds) Theory of Cryptography. TCC 2011. Lecture Notes in Computer Science, vol 6597. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-19571-6_35
Download citation
DOI: https://doi.org/10.1007/978-3-642-19571-6_35
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-19570-9
Online ISBN: 978-3-642-19571-6
eBook Packages: Computer ScienceComputer Science (R0)