Rafael Pass
ABSTRACT
We show that the security of some well-known cryptographic protocols, primitives and assumptions (e.g., the Schnorr identification scheme, commitments secure under adaptive selective-decommitment, the 'one-more' discrete logarithm assumption) cannot be based on any standard assumption using a Turing (i.e., black-box) reduction. These results follow from a general result showing that Turing reductions cannot be used to prove security of constant-round sequentially witness-hiding special-sound protocols for unique witness relations, based on standard assumptions; we emphasize that this result holds even if the protocol makes non-black-box use of the underlying assumption.
Supplemental Material
- 0}AAGIU00Fredrik Almgren, Gunnar Andersson, Torbjörn Granlund, Lars Ivansson, and Staffan Ulfberg. How we cracked the code book ciphers. Manuscript, 2000. http://codebook.org/codebook_solution.pdf.Google Scholar
- Adi Akavia, Oded Goldreich, Shafi Goldwasser, and Dana Moshkovitz. On basing one-way functions on NP-hardness. In STOC '06, pages 701--710, 2006. Google ScholarDigital Library
- Boaz Barak. How to go beyond the black-box simulation barrier. In FOCS '01, volume 0, pages 106--115, 2001. Google ScholarDigital Library
- Boaz Barak, Oded Goldreich, Shafi Goldwasser, and Yehuda Lindell. Resettably-sound zero-knowledge and its applications. In FOCS '02, pages 116--125, 2001. Google ScholarDigital Library
- Mihir Bellare, Dennis Hofheinz, and Scott Yilek. Possibility and impossibility results for encryption and commitment secure under selective opening. In EUROCRYPT, pages 1--35, 2009. Google ScholarDigital Library
- M. Blum. How to prove a theorem so no one else can claim it. Proc. of the International Congress of Mathematicians, pages 1444--1451, 1986.Google Scholar
- Emmanuel Bresson, Jean Monnerat, and Damien Vergnaud. Separation results on the "one-more" computational problems. In CT-RSA, pages 71--87, 2008. Google ScholarDigital Library
- Mihir Bellare, Chanathip Namprempre, David Pointcheval, and Michael Semanko. The one-more-rsa-inversion problems and the security of chaum's blind signature scheme. J. Cryptology, 16(3):185--215, 2003.Google ScholarCross Ref
- Mihir Bellare and Adriana Palacio. Gq and schnorr identification schemes: Proofs of security against impersonation under active and concurrent attacks. In CRYPTO, pages 162--177, 2002. Google ScholarDigital Library
- Mihir Bellare and Phillip Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In ACM Conference on Computer and Communications Security, pages 62--73, 1993. Google ScholarDigital Library
- Gilles Brassard. Relativized cryptography. IEEE Transactions on Information Theory, 29(6):877--893, 1983.Google ScholarDigital Library
- Andrej Bogdanov and Luca Trevisan. On worst-case to average-case reductions for np problems. In FOCS, pages 308--317, 2003. Google ScholarDigital Library
- Dan Boneh and Ramarathnam Venkatesan. Breaking rsa may not be equivalent to factoring. In EUROCRYPT, pages 59--71, 1998.Google ScholarCross Ref
- Ronald Cramer, Ivan Damgård, and Berry Schoenmakers. Proofs of partial knowledge and simplified design of witness hiding protocols. In CRYPTO, pages 174--187, 1994. Google ScholarDigital Library
- Ran Canetti, Oded Goldreich, Shafi Goldwasser, and Silvio Micali. Resettable zero-knowledge (extended abstract). In STOC '00, pages 235--244, 2000. Google ScholarDigital Library
- Ran Canetti, Oded Goldreich, and Shai Halevi. The random oracle methodology, revisited. J. ACM, 51(4):557--594, 2004. Google ScholarDigital Library
- David Chaum. Blind signatures for untraceable payments. In CRYPTO, pages 199--203, 1982.Google Scholar
- Ran Canetti, Huijia Lin, and Rafael Pass. Adaptive hardness and composable security in the plain model from standard assumptions. In FOCS, pages 541--550, 2010. Google ScholarDigital Library
- Yi Deng, Vipul Goyal, and Amit Sahai. Resolving the simultaneous resettability conjecture and a new non-black-box simulation strategy. In FOCS, pages 251--260, 2009. Google ScholarDigital Library
- Cynthia Dwork, Moni Naor, Omer Reingold, and Larry J. Stockmeyer. Magic functions. J. ACM, 50(6):852--921, 2003. Google ScholarDigital Library
- Cynthia Dwork, Moni Naor, and Amit Sahai. Concurrent zero-knowledge. J. ACM, 51(6):851--898, 2004. Google ScholarDigital Library
- Yevgeniy Dodis, Roberto Oliveira, and Krzysztof Pietrzak. On the generic insecurity of the full domain hash. In CRYPTO, pages 449--466, 2005. Google ScholarDigital Library
- Joan Feigenbaum and Lance Fortnow. Random-self-reducibility of complete sets. SIAM Journal on Computing, 22(5):994--1005, 1993. Google ScholarDigital Library
- Uriel Feige and Adi Shamir. Witness indistinguishable and witness hiding protocols. In STOC '90, pages 416--426, 1990. Google ScholarDigital Library
- Marc Fischlin and Dominique Schröder. On the impossibility of three-move blind signature schemes. In EUROCRYPT, pages 197--215, 2010. Google ScholarDigital Library
- Oded Goldreich and Hugo Krawczyk. On the composition of zero-knowledge proof systems. SIAM Journal on Computing, 25(1):169--192, 1996. Google ScholarDigital Library
- Shafi Goldwasser and Yael Tauman Kalai. On the (in)security of the fiat-shamir paradigm. In FOCS '03, pages 102--111, 2003. Google ScholarDigital Library
- Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof systems. SIAM Journal on Computing, 18(1):186--208, 1989. Google ScholarDigital Library
- Oded Goldreich, Silvio Micali, and Avi Wigderson. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. J. ACM, 38(3):690--728, 1991. Google ScholarDigital Library
- Oded Goldreich. Foundations of Cryptography -- Basic Tools. Cambridge University Press, 2001. Google ScholarDigital Library
- Craig Gentry and Daniel Wichs. Separating succint non-interactive arguments from all falsifiable assumptions. To appear in STOC '11, 2011. Google ScholarDigital Library
- Iftach Haitner and Thomas Holenstein. On the (im)possibility of key dependent encryption. In TCC, pages 202--219, 2009. Google ScholarDigital Library
- Johan Håstad, Russell Impagliazzo, Leonid Levin, and Michael Luby. A pseudorandom generator from any one-way function. SIAM Journal on Computing, 28:12--24, 1999. Google ScholarDigital Library
- Iftach Haitner, Alon Rosen, and Ronen Shaltiel. On the (im)possibility of arthur-merlin witness hiding protocols. In TCC, pages 220--237, 2009. Google ScholarDigital Library
- Russell Impagliazzo and Steven Rudich. Limits on the provable consequences of one-way permutations. In CRYPTO '88, pages 8--26, 1988. Google ScholarDigital Library
- Joe Kilian and Erez Petrank. Concurrent and resettable zero-knowledge in poly-loalgorithm rounds. In STOC '01, pages 560--569, 2001. Google ScholarDigital Library
- Moni Naor. Bit commitment using pseudorandomness. Journal of Cryptology, 4:151--158, 1991.Google ScholarDigital Library
- Moni Naor. On cryptographic assumptions and challenges. In CRYPTO, pages 96--109, 2003.Google ScholarCross Ref
- Tatsuaki Okamoto. Provably secure and practical identification schemes and corresponding signature schemes. In CRYPTO, pages 31--53, 1992. Google ScholarDigital Library
- Rafael Pass. Simulation in quasi-polynomial time, and its application to protocol composition. In EUROCRYPT, pages 160--176, 2003. Google ScholarDigital Library
- Rafael Pass. Parallel repetition of zero-knowledge proofs and the possibility of basing cryptography on np-hardness. In IEEE Conference on Computational Complexity, pages 96--110, 2006. Google ScholarDigital Library
- Rafael Pass and Alon Rosen. Concurrent non-malleable commitments. In FOCS '05, pages 563--572, 2005. Google ScholarDigital Library
- David Pointcheval and Jacques Stern. Security arguments for digital signatures and blind signatures. J. Cryptology, 13(3):361--396, 2000.Google ScholarDigital Library
- Rafael Pass, Wei-Lung Dustin Tseng, and Muthuramakrishan Venkitasubramaniam. Towards non-black-box separations in cryptography. To appear in TCC 2011, 2010. Google ScholarDigital Library
- Rafael Pass and Muthuramakrishnan Venkitasubramaniam. On constant-round concurrent zero-knowledge. In TCC '08, pages 553--570, 2008. Google ScholarDigital Library
- Ransom Richardson and Joe Kilian. On the concurrent composition of zero-knowledge proofs. In Eurocrypt ''99, pages 415--432, 1999. Google ScholarDigital Library
- Omer Reingold, Luca Trevisan, and Salil P. Vadhan. Notions of reducibility between cryptographic primitives. In TCC, pages 1--20, 2004.Google ScholarCross Ref
- Guy N. Rothblum and Salil P. Vadhan. Are pcps inherent in efficient arguments? Computational Complexity, 19(2):265--304, 2010. Google ScholarDigital Library
- Claus-Peter Schnorr. Efficient signature generation by smart cards. J. Cryptology, 4(3):161--174, 1991.Google ScholarDigital Library
- Victor Shoup. Lower bounds for discrete logarithms and related problems. In EUROCRYPT, pages 256--266, 1997. Google ScholarDigital Library
Index Terms
- Limits of provable security from standard assumptions
Recommendations
Improved convertible authenticated encryption scheme with provable security
Convertible authenticated encryption (CAE) schemes allow a signer to produce an authenticated ciphertext such that only a designated recipient can decrypt it and verify the recovered signature. The conversion property further enables the designated ...
Unprovable Security of Perfect NIZK and Non-interactive Non-malleable Commitments
We present barriers to provable security of two important cryptographic primitives, perfect non-interactive zero knowledge (NIZK) and non-interactive non-alleable commitments: źBlack-box reductions cannot be used to demonstrate adaptive soundness (i.e., ...
Two-Round Adaptively Secure Multiparty Computation from Standard Assumptions
Theory of CryptographyAbstractWe present the first two-round multiparty computation (MPC) protocols secure against malicious adaptive corruption in the common reference string (CRS) model, based on DDH, LWE, or QR. Prior two-round adaptively secure protocols were known only in ...
Comments