Abstract
Recently, methods from provable security, that had been developped for the last twenty years within the research community, have been extensively used to support emerging standards. This in turn has led researchers as well as practitioners to raise some concerns about this methodology. Should provable security be restricted to the standard computational model or can it rely on the so-called random oracle model? In the latter case, what is the practical meaning of security estimates obtained using this model? Also, the fact that proofs themselves need time to be validated through public discussion was somehow overlooked. Building on two case studies, we discuss these concerns. One example covers the public key encryption formatting scheme OAEP originally proposed in [[3]]. The other comes from the area of signature schemes and is related to the security proof of ESIGN [[43]]. Both examples show that provable security is more subtle than it at first appears.
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
M. Bellare, A. Desai, D. Pointcheval, and P. Rogaway. Relations among Notions of Security for Public-Key Encryption Schemes. In Crypto’ 98, Lecture Notes in Computer Science 1462, Springer-Verlag, Berlin, 1998, 26–45.
M. Bellare and P. Rogaway. Random Oracles Are Practical: a Paradigm for Designing Efficient Protocols. In Proc. of the 1st CCS, ACM Press, New York, 1993, 62–73.
M. Bellare and P. Rogaway. Optimal Asymmetric Encryption — How to Encrypt with RSA. In Eurocrypt’ 94, Lecture Notes in Computer Science 950, Springer-Verlag, Berlin, 1995, 92–111.
M. Bellare and P. Rogaway. The Exact Security of Digital Signatures — How to Sign with RSA and Rabin. In Eurocrypt’ 96, Lecture Notes in Computer Science 1070, Springer-Verlag, Berlin, 1996, 399–416.
D. Bleichenbacher. A Chosen Ciphertext Attack against Protocols based on the RSA Encryption Standard PKCS #1. In Crypto’ 98, Lecture Notes in Computer Science 1462, Springer-Verlag, Berlin, 1998, 1–12.
D. Boneh. Simplified OAEP for the RSA and Rabin Functions. In Crypto’ 2001, Lecture Notes in Computer Science 2139, Springer-Verlag, Berlin, 2001, 275–291.
D. Boneh and R. Venkatesan. Breaking RSA may not be equivalent to factoring. In Eurocrypt’ 98, Lecture Notes in Computer Science 1402, Springer-Verlag, Berlin, 1998, 59–71,.
E. Brickell and J. M. DeLaurentis. An Attack on a Signature Scheme proposed by Okamoto and Shiraishi. In Crypto’ 85, Lecture Notes in Computer Science 218, 28–32, Springer-Verlag, Berlin, 1986, 28–32.
E. Brickell, D. Pointcheval, S. Vaudenay, and M. Yung. Design Validations for Discrete Logarithm Based Signature Schemes. In PKC’ 2000, Lecture Notes in Computer Science 1751, Springer-Verlag, Berlin, 2000, 276–292.
D. R. L. Brown. The Exact Security of ECDSA, January 2001. Available from http://grouper.ieee.org/groups/1363/.
R. Canetti, O. Goldreich, and S. Halevi. The Random Oracles Methodology, Revisited. In Proc. of the 30th STOC, ACM Press, New York, 1998, 209–218.
D. Coppersmith. Finding a Small Root of a Univariate Modular Equation. In Eurocrypt’ 96, Lecture Notes in Computer Science 1070, Springer-Verlag, Berlin, 1996, 155–165.
D. Coppersmith, S. Halevi and C. Jutla. ISO 9796-1 and the New Forgery Strategy. Presented at the Rump session of Crypto’ 99.
J.-S. Coron. On the Exact Security of Full-Domain-Hash. In Crypto’ 2000, Lecture Notes in Computer Science 1880, Springer-Verlag, Berlin, 2000, 229–235.
J.-S. Coron. Optimal Security Proofs for PSS and other Signature Schemes. In Eurocrypt’ 2002 Lecture Notes in Computer Science 2332, Springer-Verlag, Berlin, 2002, 272–287. Also appeared in the Cryptology ePrint Archive 2001/062, June 2001, available from http://eprint.iacr.org/, 2001.
J.-S. Coron, D. Naccache and J. P. Stern. On the Security of RSA Padding. In Crypto’ 99, Lecture Notes in Computer Science 1666, Springer, Berlin, 1999, 1–18.
R. Cramer and V. Shoup. A Practical Public key Cryptosystem Provably Secure Against Adaptive Chosen Ciphertext Attacks. In Crypto’98, Lecture Notes in Computer Science 1462, 1998, 13–25.
R. Cramer and V. Shoup. Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public Key Encryption. In Eurocrypt’2002, Lecture Notes in Computer Science 2332, 45–64.
W. Diffie and M.E. Hellman. New Directions in Cryptography, IEEE Transactions on Information Theory, v. IT-22,6, Nov 1976, 644–654.
D. Dolev, C. Dwork, and M. Naor. Non-Malleable Cryptography. SIAM Journal on Computing, 30(2), 2000, 391–437.
A. Fiat and A. Shamir. How to Prove Yourself: Practical Solutions of Identification and Signature Problems. In Crypto’ 86, Lecture Notes in Computer Science 263, Springer-Verlag, Berlin, 1987, 186–194.
E. Fujisaki, T. Okamoto, D. Pointcheval, and J. Stern. RSA—OAEP is Secure under the RSA Assumption. In Crypto’ 2001, Lecture Notes in Computer Science 2139, Springer-Verlag, Berlin, 2001, 260–274. Also appeared in the Cryptology ePrint Archive 2000/061, November 2000, available from http://eprint.iacr.org/.
T. El Gamal. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Transactions on Information Theory, IT-31(4), 1985, 469–472.
M. Girault, P. Toffin and B. Vallée. Computation of Approximate L-th Roots Modulo n and Application to Cryptography. In Crypto’ 88, Lecture Notes in Computer Science 403, Springer-Verlag, Berlin, 1989, 100–118.
S. Goldwasser and S. Micali. Probabilistic Encryption. Journal of Computer and System Sciences, 28, 1984, 270–299.
S. Goldwasser, S. Micali, and C. Rackoff. The Knowledge Complexity of Interactive Proof Systems. In Proc. of the 17th STOC, ACM Press, New York, 1985, 291–304.
S. Goldwasser, S. Micali, and R. Rivest. A “Paradoxical” Solution to the Signature Problem. In Proc. of the 25th FOCS, IEEE, New York, 1984, 441–448.
S. Goldwasser, S. Micali, and R. Rivest. A Digital Signature Scheme Secure Against Adaptative Chosen-Message Attacks. SIAM Journal of Computing, 17(2), 1988, 281–308.
L. Granboulan. How to repair ESIGN. NESSIE internal document, May 2002. See http://www.cryptonessie.org, Document NES/DOC/ENS/WP5/019.
C. Hall, I. Goldberg, and B. Schneier. Reaction Attacks Against Several Public-Key Cryptosystems. In Proc. of ICICS’99, Lecture Notes in Computer Science, Springer-Verlag, 1999, 2–12.
J. Jonsson. Security Proofs for RSA-PSS and Its Variants. Cryptology ePrint Archive 2001/053, June 2001. Available from http://eprint.iacr.org/.
IEEE P1363. Standard Specifications for Public Key Cryptography, August 1998. Available from http://grouper.ieee.org/groups/1363/.
B. Kaliski and J. Staddon. IETF RFC 2437: PKCS #1: RSA Cryptography Specifications Version 2.0. October 1998.
J. Manger. A Chosen Ciphertext Attack on RSA Optimal Asymmetric Encryption Padding (OAEP) as Standardized in PKCS #1. In Crypto’ 2001, Lecture Notes in Computer Science 2139, Springer-Verlag, Berlin, 2001, 230–238.
M. Naor and M. Yung. Public-Key Cryptosystems Provably Secure against Chosen Ciphertext Attacks. In Proc. of the 22nd STOC, ACM Press, New York, 1990, 427–437.
NIST. Digital Signature Standard (DSS). Federal Information Processing Standards Publication 186, November 1994.
NIST. Secure Hash Standard (SHS). Federal Information Processing Standards Publication 180-1, April 1995.
NIST. Digital Signature Standard (DSS). Federal Information Processing Standards Publication 186-2, January 2000.
A. K. Lenstra, H. W. Lenstra and L. Lovász. Factoring Polynomials with Rational Coefficients, Mathematische Ann., 261, 1982, 513–534.
D. Naccache, D. Pointcheval, and J. Stern. Twin Signatures: an Alternative to the Hash-and-Sign Paradigm. In Proc. of the 8th CCS, ACM Press, New York, 2001 20–27.
V. I. Nechaev. Complexity of a Determinate Algorithm for the Discrete Logarithm. Mathematical Notes, 55(2), 1994, 165–172.
T. Okamoto. A Fast Signature Scheme Based on Congruential Polynomial Operations. IEEE Transactions on Information Theory, IT-36(1), 1990, 47–53.
T. Okamoto, E. Fujisaki and H. Morita. TSH-ESIGN: Efficient Digital Signature Scheme Using Trisection Size Hash, Submission to P1363a, 1998.
T. Okamoto and D. Pointcheval. REACT: Rapid Enhanced-security Asymmetric Cryptosystem Transform. In CT — RSA’ 2001, Lecture Notes in Computer Science 2020, Springer-Verlag, Berlin, 2001, 159–175.
T. Okamoto and A. Shiraishi. A Fast Signature Scheme Based on Quadratic Inequalities. Proc. of the ACM Symp. Security and Privacy, ACM Press, 1985, 123–132.
T. Okamoto and J. Stern. Almost uniform density of power residues and the security proof of ESIGN. Unpublished manuscript.
G. Pólya. Über die Verteilung des quadratischen Reste und Nichtreste. Göttinger Nachtrichten (1918), 21–26.
D. Pointcheval and J. Stern. Security Proofs for Signature Schemes. In Eurocrypt’ 96, Lecture Notes in Computer Science 1070, Springer-Verlag, Berlin, 1996, 387–398.
D. Pointcheval and J. Stern. Security Arguments for Digital Signatures and Blind Signatures. Journal of Cryptology, 13(3), 2000, 361–396.
C. Rackoff and D. R. Simon. Non-Interactive Zero-Knowledge Proof of Knowledge and Chosen Ciphertext Attack. In Crypto’ 91, Lecture Notes in Computer Science 576, Springer-Verlag, Berlin, 1992, 433–444.
R. Rivest, A. Shamir, and L. Adleman. A Method for Obtaining Digital Signatures and Public Key Cryptosystems. Communications of the ACM, 21(2), 1978, 120–126.
RSA Laboratories. PKCS # 1 Version 1.5: RSA Cryptography Standard. November 1993, http://www.rsa.com/rsalabs/pubs/PKCS/.
RSA Laboratories. PKCS # 1 Version 2.1: RSA Cryptography Standard. Draft, January 2001, http://www.rsa.com/rsalabs/pubs/PKCS/.
C. P. Schnorr. Efficient Identification and Signatures for Smart Cards. In Crypto’ 89, Lecture Notes in Computer Science 435, Springer-Verlag, Berlin, 1990, 235–251.
C. P. Schnorr. Efficient Signature Generation by Smart Cards. Journal of Cryptology, 4(3), 1991, 161–174.
C. P. Schnorr and M. Jakobsson. Security of Signed ElGamal Encryption. In Asiacrypt’ 2000, Lecture Notes in Computer Science 1976, Springer-Verlag, Berlin, 2000, 458–469.
V. Shoup. Lower Bounds for Discrete Logarithms and Related Problems. In Eurocrypt’ 97, Lecture Notes in Computer Science 1233, Springer-Verlag, Berlin, 1997, 256–266.
V. Shoup. OAEP Reconsidered. In Crypto’ 2001, Lecture Notes in Computer Science 2139, Springer-Verlag, Berlin, 2001, 239–259. Also appeared in the Cryptology ePrint Archive 2000/060, November 2000, available from http://eprint.iacr.org/.
J. Stern, D. Pointcheval, J. Malone-Lee, and N. Smart. Flaws in Applying Proof Methodologies to Signature Schemes. In Crypto’ 02, Lecture Notes in Computer Science 2442, Springer-Verlag, Berlin, 2002, 93–110.
B. Vallée, M. Girault, and P. Toffin. How to break Okamoto’s Cryptosystem by Reducing Lattice Bases. In Eurocrypt’ 88, Lecture Notes in Computer Science 330, Springer-Verlag, Berlin, 1988, 281–292.
B. Vallée, M. Girault and P. Toffin. How to Guess ℓth Roots Modulo n by Reducing Lattice Bases. In AAECC-6, Lecture Notes in Computer Science 357, Springer-Verlag, Berlin, 1988, 427–442.
I.M. Vinogradov. Sur la distributions des résidus et des non-résidus des puissances. J. Phys.-Math. Soc. Perm. 1 (1918), 94–96.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 International Association for Cryptologic Research
About this paper
Cite this paper
Stern, J. (2003). Why Provable Security Matters?. In: Biham, E. (eds) Advances in Cryptology — EUROCRYPT 2003. EUROCRYPT 2003. Lecture Notes in Computer Science, vol 2656. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-39200-9_28
Download citation
DOI: https://doi.org/10.1007/3-540-39200-9_28
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-14039-9
Online ISBN: 978-3-540-39200-2
eBook Packages: Springer Book Archive