Asymmetric cryptography and practical security

Authors

  • David Pointcheval LIENS – CNRS, Ecole Normale Superieure, Paris, France

DOI:

https://doi.org/10.26636/jtit.2002.4.146

Keywords:

cryptography, digital signatures, public-key encryption, provable security, random oracle model

Abstract

Since the appearance of public-key cryptography in Diffie-Hellman seminal paper, many schemes have been proposed, but many have been broken. Indeed, for many people, the simple fact that a cryptographic algorithm withstands cryptanalytic attacks for several years is considered as a kind of validation. But some schemes took a long time before being widely studied, and maybe thereafter being broken. A much more convincing line of research has tried to provide "provable" security for cryptographic protocols, in a complexity theory sense: if one can break the cryptographic protocol, one can efficiently solve the underlying problem. Unfortunately, very few practical schemes can be proven in this so-called "standard model" because such a security level rarely meets with efficiency. A convenient but recent way to achieve some kind of validation of efficient schemes has been to identify some concrete cryptographic objects with ideal random ones: hash functions are considered as behaving like random functions, in the so-called "random oracle model", block ciphers are assumed to provide perfectly independent and random permutations for each key in the "ideal cipher model", and groups are used as black-box groups in the "generic model". In this paper, we focus on practical asymmetric protocols together with their "reductionist" security proofs. We cover the two main goals that public-key cryptography is devoted to solve: authentication with digital signatures, and confidentiality with public-key encryption schemes.

Downloads

Download data is not yet available.

References

[1] American National Standards Institute. Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm. ANSI X9.62-1998. Jan. 1999.
View in Google Scholar

[2] N. Barić and B. Pfitzmann, "Collision-free accumulators and failstop signature schemes without trees", in Advances in Cryptology - Proceedings of EUROCRYPT '97, W. Fumy, Ed., Lecture Notes in Computer Science. Berlin: Springer, 1997, vol. 1233, pp. 480-484.
View in Google Scholar

[3] O. Baudron, D. Pointcheval, and J. Stern, "Extended notions of security for multicast public key cryptosystems", in Proceedings of the 27th International Colloquium on Automata, Languages and Programming (ICALP '2000), J. D. P. R. U. Montanari and E. Welzl, Eds., Lecture Notes in Computer Science. Berlin: Springer, 2000, vol. 1853, pp. 499-511.
View in Google Scholar

[4] M. Bellare, "Practice-oriented provable security", in Proceedings of First International Workshop on Information Security (ISW '97), E. Okamoto, G. Davida, and M. Mambo, Eds., Lecture Notes in Computer Science. Berlin: Springer, 1997, vol. 1396.
View in Google Scholar

[5] M. Bellare, A. Boldyreva, and S. Micali, "Public-key encryption in a multi-user setting: security proofs and improvements", in Advances in Cryptology - Proceedings of EUROCRYPT '2000, B. Preneel, Ed., Lecture Notes in Computer Science. Berlin: Springer, 2000, vol. 1807, pp. 259-274.
View in Google Scholar

[6] M. Bellare, A. Desai, D. Pointcheval, and P. Rogaway, "Relations among notions of security for public-key encryption schemes", in Advances in Cryptology - Proceedings of CRYPTO '98, H. Krawczyk, Ed., Lecture Notes in Computer Science. Berlin: Springer, 1998, vol. 1462, pp. 26-45.
View in Google Scholar

[7] M. Bellare, D. Pointcheval, and P. Rogaway, "Authenticated key exchange secure against dictionary attacks", in Advances in Cryptology - Proceedings of EUROCRYPT '2000, B. Preneel, Ed., Lecture Notes in Computer Science. Berlin: Springer, 2000, vol. 1807, pp. 139-155.
View in Google Scholar

[8] M. Bellare and P. Rogaway, "Random oracles are practical: a paradigm for designing efficient protocols", in Proceedings of the 1st ACM Conference on Computer and Communications Security. New York: ACM Press, 1993, pp. 62-73.
View in Google Scholar

[9] M. Bellare and P. Rogaway, "Optimal asymmetric encryption - how to encrypt with RSA", in Advances in Cryptology - Proceedings of EUROCRYPT '94, A. D. Santis, Ed., Lecture Notes in Computer Science. Berlin: Springer, 1995, vol. 950, pp. 92-111.
View in Google Scholar

[10] M. Bellare and P. Rogaway, "The exact security of digital signatures - how to sign with RSA and Rabin", in Advances in Cryptology - Proceedings of EUROCRYPT '96, U. Maurer, Ed., Lecture Notes in Computer Science. Berlin: Springer, 1996, vol. 1070, pp. 399-416.
View in Google Scholar

[11] E. Biham and A. Shamir, "Differential fault analysis of secret key cryptosystems", in Advances in Cryptology - Proceedings of CRYPTO '97, B. Kaliski, Ed., Lecture Notes in Computer Science. Berlin: Springer, 1997, vol. 1294, pp. 513-525.
View in Google Scholar

[12] D. Bleichenbacher, "Generating El Gamal signatures without knowing the secret key", in Advances in Cryptology - Proceedings of EUROCRYPT '96, U. Maurer, Ed., Lecture Notes in Computer Science. Berlin: Springer, 1996, vol. 1070, pp. 10-18.
View in Google Scholar

[13] D. Bleichenbacher, "A chosen ciphertext attack against protocols based on the RSA encryption standard PKCS #1", in Advances in Cryptology - Proceedings of CRYPTO '98, H. Krawczyk, Ed., Lecture Notes in Computer Science. Berlin: Springer, 1998, vol. 1462, pp. 1-12.
View in Google Scholar

[14] D. Boneh, "Simplified OAEP for the RSA and Rabin functions", in Advances in Cryptology - Proceedings of CRYPTO '2001, J. Kilian, Ed., Lecture Notes in Computer Science. Berlin: Springer, 2001, vol. 2139, pp. 275-291.
View in Google Scholar

[15] D. Boneh, R. DeMillo, and R. Lipton, "On the importance of checking cryptographic protocols for faults", in Advances in Cryptology - Proceedings of EUROCRYPT '97, W. Fumy, Ed., Lecture Notes in Computer Science. Berlin: Springer, 1997, vol. 1233, pp. 37-51.
View in Google Scholar

[16] E. Brickell, D. Pointcheval, S. Vaudenay, and M. Yung, "Design validations for discrete logarithm-based signature schemes", in Workshop on Practice and Theory in Public-Key Cryptography (PKC '2000), H. Imai and Y. Zheng, Eds., Lecture Notes in Computer Science. Berlin: Springer, 2000, vol. 1751, pp. 276-292.
View in Google Scholar

[17] D. R. L. Brown and D. B. Johnson, "Formal security proofs for a signature scheme with partial message recovery", in The Cryptographers' Track at RSA Conference '2001 (RSA '2001), D. Naccache, Ed., Lectures Notes in Computer Science. Berlin: Springer, 2001, vol. 2020, pp. 126-142.
View in Google Scholar

[18] R. Canetti, O. Goldreich, and S. Halevi, "The random oracles methodology, revisited", in Proceedings of the 30th ACM Symposium on the Theory of Computing (STOC '98). New York: ACM Press, 1998, pp. 209-218.
View in Google Scholar

[19] S. Cavallar, B. Dodson, A. K. Lenstra, W. Lioen, P. L. Montgomery, B. Murphy, H. Riele, K. Aardal, J. Gilchrist, G. Guillerm, P. Leyland, J. Marchand, F. Morain, A. Muffett, C. Putnam, C. Putnam, and P. Zimmermann, "Factorization of a 512-bit RSA modulus", in Advances in Cryptology - Proceedings of EUROCRYPT '2000, B. Preneel, Ed., Lecture Notes in Computer Science. Berlin: Springer, 2000, vol. 1807, pp. 1-18.
View in Google Scholar

[20] B. Chor and R. L. Rivest, "A knapsack type public key cryptosystem based on arithmetic in finite fields", in Advances in Cryptology - Proceedings of CRYPTO '84, B. Blakley and D. Chaum, Eds., Lecture Notes in Computer Science. Berlin: Springer, 1985, vol. 196, pp. 54-65.
View in Google Scholar

[21] J.-S. Coron, "On the exact security of full-domain-hash", in Advances in Cryptology - Proceedings of CRYPTO '2000, M. Bellare, Ed., Lecture Notes in Computer Science. Berlin: Springer, 2000, vol. 1880, pp. 229-235.
View in Google Scholar

[22] R. Cramer and V. Shoup, "A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack", in Advances in Cryptology - Proceedings of CRYPTO '98, H. Krawczyk, Ed., Lecture Notes in Computer Science. Berlin: Springer, 1998, vol. 1462, pp. 13-25.
View in Google Scholar

[23] R. Cramer and V. Shoup, "Signature scheme based on the Strong RSA assumption", in Proceedings of the 6th ACM Conference on Computer and Communications Security. New York: ACM Press, 1999, pp. 46-51.
View in Google Scholar

[24] W. Diffie and M. E. Hellman, "New directions in cryptography", IEEE Trans. Inform. Theory, vol. IT-22, no. 6, pp. 644-654, 1976.
View in Google Scholar

[25] D. Dolev, C. Dwork, and M. Naor, "Non-malleable cryptography", SIAM J. Comput., vol. 30, no. 2, pp. 391-437, 2000.
View in Google Scholar

[26] T. El Gamal, "A public key cryptosystem and a signature scheme based on discrete logarithms", IEEE Trans. Inform. Theory, vol. IT-31, no. 4, pp. 469-472, 1985.
View in Google Scholar

[27] A. Fiat and A. Shamir, "How to prove yourself: practical solutions of identification and signature problems", in Advances in Cryptology - Proceedings of CRYPTO '86, A. M. Odlyzko, Ed., Lecture Notes in Computer Science. Berlin: Springer, 1987, vol. 263, pp. 186-194.
View in Google Scholar

[28] E. Fujisaki and T. Okamoto, "Statistical zero knowledge protocols to prove modular polynomial relations", in Advances in Cryptology - Proceedings of CRYPTO '97, B. Kaliski, Ed., Lecture Notes in Computer Science. Berlin: Springer, 1997, vol. 1294, pp. 16-30.
View in Google Scholar

[29] E. Fujisaki and T. Okamoto, "How to enhance the security of public-key encryption at minimum cost", in Workshop on Practice and Theory in Public-Key Cryptography (PKC '99), H. Imai and Y. Zheng, Eds., Lecture Notes in Computer Science. Berlin: Springer, 1999, vol. 1560, pp. 53-68.
View in Google Scholar

[30] E. Fujisaki and T. Okamoto, "Secure integration of asymmetric and symmetric encryption schemes", in Advances in Cryptology - Proceedings of CRYPTO '99, M. Wiener, Ed., Lecture Notes in Computer Science. Berlin: Springer, 1999, vol. 1666, pp. 537-554.
View in Google Scholar

[31] E. Fujisaki, T. Okamoto, D. Pointcheval, and J. Stern, "RSA-OAEP is secure under the RSA assumption", in Advances in Cryptology - Proceedings of CRYPTO '2001, J. Kilian, Ed., Lecture Notes in Computer Science. Berlin: Springer, 2001, vol. 2139, pp. 260-274.
View in Google Scholar

[32] O. Goldreich, S. Goldwasser, and S. Micali, "How to construct random functions", J. ACM, vol. 33, no. 4, pp. 792-807, 1986.
View in Google Scholar

[33] S. Goldwasser and S. Micali, "Probabilistic encryption", J. Comput. Syst. Sci., vol. 28, pp. 270-299, 1984.
View in Google Scholar

[34] S. Goldwasser, S. Micali, and C. Rackoff, "The knowledge complexity of interactive proof systems", in Proceedings of the 17th ACM Symposium on the Theory of Computing (STOC '85). New York: ACM Press, 1985, pp. 291-304.
View in Google Scholar

[35] S. Goldwasser, S. Micali, and R. Rivest, "A "paradoxical" solution to the signature problem", in Proceedings of the 25th Symposium on the Foundations of Computer Science (FOCS '84). New York: IEEE, 1984, pp. 441-448.
View in Google Scholar

[36] S. Goldwasser, S. Micali, and R. Rivest, "A digital signature scheme secure against adaptative chosen-message attacks", SIAM J. Comput., vol. 17, no. 2, pp. 281-308, 1988.
View in Google Scholar

[37] C. Hall, I. Goldberg, and B. Schneier, "Reaction attacks against several public-key cryptosystems", in Proceedings of the International Conference on Information and Communications Security 1999, Lecture Notes in Computer Science. Springer, 1999, pp. 2-12.
View in Google Scholar

[38] J. Hastad, "Solving simultaneous modular equations of low degree", SIAM J. Comput., vol. 17, pp. 336-341, 1988.
View in Google Scholar

[39] A. Joux and R. Lercier, "Improvements to the general Number Field Sieve for discrete logarithms in prime fields", Math. Comput., 2000.
View in Google Scholar

[40] M. Joye, J. J. Quisquater, and M. Yung, "On the power of misbehaving adversaries and security analysis of the original EPOC", in The Cryptographers' Track at RSA Conference '2001 (RSA '2001), D. Naccache, Ed., Lectures Notes in Computer Science. Berlin: Springer, 2001, vol. 2020, pp. 208-222.
View in Google Scholar

[41] KCDSA Task Force Team. The Korean Certificate-based Digital Signature Algorithm. Submission to IEEE P1363a. Aug. 1998.
View in Google Scholar

[42] P. C. Kocher, "Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems", in Advances in Cryptology - Proceedings of CRYPTO '96, N. Koblitz, Ed., Lecture Notes in Computer Science. Berlin: Springer, 1996, vol. 1109, pp. 104-113.
View in Google Scholar

[43] P. C. Kocher, J. Jaffe, and B. Jun, "Differential power analysis", in Advances in Cryptology - Proceedings of CRYPTO '99, M. Wiener, Ed., Lecture Notes in Computer Science. Berlin: Springer, 1999, vol. 1666, pp. 388-397.
View in Google Scholar

[44] A. Lenstra and H. Lenstra, The Development of the Number Field Sieve, Lecture Notes in Mathematics. Springer, 1993, vol. 1554.
View in Google Scholar

[45] A. Lenstra and E. Verheul, "Selecting cryptographic key sizes", in Workshop on Practice and Theory in Public-Key Cryptography (PKC '2000), H. Imai and Y. Zheng, Eds., Lecture Notes in Computer Science. Berlin: Springer, 2000, vol. 1751, pp. 446-465.
View in Google Scholar

[46] A. K. Lenstra, H. W. Lenstra, and L. Lovasz, "Factoring polynomials with rational coefficients", Math. Ann., vol. 261, no. 4, pp. 515-534, 1982.
View in Google Scholar

[47] H. Lenstra, "On the Chor-Rivest knapsack cryptosystem", J. Crypt., vol. 3, pp. 149-155, 1991.
View in Google Scholar

[48] J. Manger, "A chosen ciphertext attack on RSA optimal asymmetric encryption padding (OAEP) as standardized in PKCS #1", in Advances in Cryptology - Proceedings of CRYPTO '2001, J. Kilian, Ed., Lecture Notes in Computer Science. Berlin: Springer, 2001, vol. 2139, pp. 230-238.
View in Google Scholar

[49] R. J. McEliece, "A public-key cryptosystem based on algebraic coding theory". DSN Progress Rep., 42-44:114-116, 1978. Jet Propulsion Laboratories, CALTECH.
View in Google Scholar

[50] G. Miller, "Riemann's hypothesis and tests for primality", J. Comput. Syst. Sci., vol. 13, pp. 300-317, 1976.
View in Google Scholar

[51] D. M'Ra?hi, D. Naccache, D. Pointcheval, and S. Vaudenay, "Computational alternatives to random number generators", in Fifth Annual Workshop on Selected Areas in Cryptography (SAC '98), Lectures Notes in Computer Science. Berlin: Springer, 1998, vol. 1556, pp. 72-80.
View in Google Scholar

[52] M. Naor and M. Yung, "Public-key cryptosystems provably secure against chosen ciphertext attacks", in Proceedings of the 22nd ACM Symposium on the Theory of Computing (STOC '90). New York: ACM Press, 1990, pp. 427-437.
View in Google Scholar

[53] V. I. Nechaev, "Complexity of a determinate algorithm for the discrete logarithm", Math. Not., vol. 55, no. 2, pp. 165-172, 1994.
View in Google Scholar

[54] NIST. Digital Signature Standard (DSS). Federal Information Processing Standards PUBlication 186, Nov. 1994.
View in Google Scholar

[55] NIST. Secure Hash Standard (SHS). Federal Information Processing Standards PUBlication 180-1, Apr. 1995.
View in Google Scholar

[56] NIST. Secure Hash Algorithm 256/384/512. Oct. 2000.
View in Google Scholar

[57] K. Ohta and T. Okamoto, "On concrete security treatment of signatures derived from identification", in Advances in Cryptology - Proceedings of CRYPTO '98, H. Krawczyk, Ed., Lecture Notes in Computer Science. Berlin: Springer, 1998, vol. 1462, pp. 354-369.
View in Google Scholar

[58] T. Okamoto and D. Pointcheval, "REACT: rapid enhanced-security asymmetric cryptosystem transform", in The Cryptographers' Track at RSA Conference '2001 (RSA '2001), D. Naccache, Ed., Lectures Notes in Computer Science. Berlin: Springer, 2001, vol. 2020, pp. 159-175.
View in Google Scholar

[59] T. Okamoto and D. Pointcheval, "RSA-REACT: an alternative to RSA-OAEP", in Second NESSIE Worksh., Sept. 2001.
View in Google Scholar

[60] T. Okamoto and D. Pointcheval, "The gap-problems: a new class of problems for the security of cryptographic schemes", in Workshop on Practice and Theory in Public-Key Cryptography (PKC '2001), K. Kim, Ed., Lecture Notes in Computer Science. Berlin: Springer, 2001, vol. 1992.
View in Google Scholar

[61] D. Pointcheval, "Chosen-ciphertext security for any one-way cryptosystem", in Workshop on Practice and Theory in Public-Key Cryptography (PKC '2000), H. Imai and Y. Zheng, Eds., Lecture Notes in Computer Science. Berlin: Springer, 2000, vol. 1751, pp. 129-146.
View in Google Scholar

[62] D. Pointcheval and J. Stern, "Security proofs for signature schemes", in Advances in Cryptology - Proceedings of EUROCRYPT '96, U. Maurer, Ed., Lecture Notes in Computer Science. Berlin: Springer, 1996, vol. 1070, pp. 387-398.
View in Google Scholar

[63] D. Pointcheval and J. Stern, "Security arguments for digital signatures and blind signatures", J. Crypt., vol. 13, no. 3, pp. 361-396, 2000.
View in Google Scholar

[64] D. Pointcheval and S. Vaudenay, "On provable security for digital signature algorithms". Technical Rep., Laboratoire d'Informatique de l'Ecole Normale Superieure, Oct. 1996.
View in Google Scholar

[65] J. M. Pollard, "Monte Carlo methods for index computation (mod p)", Math. Comput., vol. 32, no. 143, pp. 918-924, 1978.
View in Google Scholar

[66] M. O. Rabin, "Digitalized signatures", in Foundations of Secure Computation, R. Lipton and R. D. Millo, Eds. New York: Academic Press, 1978, pp. 155-166.
View in Google Scholar

[67] C. Rackoff and D. R. Simon, "Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack", in Advances in Cryptology - Proceedings of CRYPTO '91, J. Feigenbaum, Ed., Lecture Notes in Computer Science. Berlin: Springer, 1992, vol. 576, pp. 433-444.
View in Google Scholar

[68] R. Rivest, "The MD5 message-digest algorithm". RFC 1321. The Internet Engineering Task Force, Apr. 1992.
View in Google Scholar

[69] R. Rivest, A. Shamir, and L. Adleman, "A method for obtaining digital signatures and public key cryptosystems", Commun. ACM, vol. 21, no. 2, pp. 120-126, 1978.
View in Google Scholar

[70] RSA Data Security, Inc. Public Key Cryptography Standards - PKCS.
View in Google Scholar

[71] C. P. Schnorr, "Efficient identification and signatures for smart cards", in Advances in Cryptology - Proceedings of CRYPTO '89, G. Brassard, Ed., Lecture Notes in Computer Science. Berlin: Springer, 1990, vol. 435, pp. 235-251.
View in Google Scholar

[72] C. P. Schnorr, "Efficient signature generation by smart cards", J. Crypt., vol. 4, no. 3, pp. 161-174, 1991.
View in Google Scholar

[73] C. P. Schnorr and M. Jakobsson, "Security of signed El Gamal encryption", in Advances in Cryptology - Proceedings of ASIACRYPT '2000, T. Okamoto, Ed., Lecture Notes in Computer Science. Berlin: Springer, 2000, vol. 1976, pp. 458-469.
View in Google Scholar

[74] D. Shanks, "Class number, a theory of factorization, and Genera", in Proceedings of the Symposium on Pure Mathematics. AMS, 1971, vol. 20, pp. 415-440.
View in Google Scholar

[75] C. E. Shannon, "Communication theory of secrecy systems", Bell Syst. Tech. J., vol. 28, no. 4, pp. 656-715, 1949.
View in Google Scholar

[76] H. Shimizu, "On the improvement of the Hastad bound", in 1996 IEICE Fall Conf., 1996, vol. A-162 (in Japanese).
View in Google Scholar

[77] V. Shoup, "Lower bounds for discrete logarithms and related problems", in Advances in Cryptology - Proceedings of EUROCRYPT '97, W. Fumy, Ed., Lecture Notes in Computer Science. Berlin: Springer, 1997, vol. 1233, pp. 256-266.
View in Google Scholar

[78] V. Shoup, "OAEP reconsidered", in Advances in Cryptology - Proceedings of CRYPTO '2001, J. Kilian, Ed., Lecture Notes in Computer Science. Berlin: Springer, 2001, vol. 2139, pp. 239-259.
View in Google Scholar

[79] Y. Tsiounis and M. Yung, "On the security of El Gamal based encryption", in Workshop on Practice and Theory in Public-Key Cryptography (PKC '98), H. Imai and Y. Zheng, Eds., Lecture Notes in Computer Science. Berlin: Springer, 1998.
View in Google Scholar

[80] S. Vaudenay, "Cryptanalysis of the Chor-Rivest scheme", in Advances in Cryptology - Proceedings of CRYPTO '98, H. Krawczyk, Ed., Lecture Notes in Computer Science. Berlin: Springer, 1998, vol. 1462, pp. 243-256.
View in Google Scholar

[81] G. S. Vernam, "Cipher printing telegraph systems for secret wire and radio telegraphic communications", J. Am. Inst. Electr. Eng., vol. 45, pp. 109-115, 1926.
View in Google Scholar

Downloads

Published

2002-12-30

Issue

Section

RESEARCH ARTICLES

How to Cite

[1]
D. Pointcheval, “Asymmetric cryptography and practical security”, JTIT, vol. 10, no. 4, pp. 41–56, Dec. 2002, doi: 10.26636/jtit.2002.4.146.