On Provable Security of Cryptographic Schemes

Abstract

Provable security is an important issue in modern cryptography because it satisfies the security of the encryption schemes in a theoretical way via a reduction method. Typically, a mathematically hard problem M is reduced to breaking the scheme S that is wanted to be proven secure. Existence of such a reduction implies that the problem of breaking the scheme S is as hard as M. This reduction results in a contradiction by arguing that if there exists a polynomial time algorithm A breaking S, then one consructs a polynomial time algorithm B to solve M by using A as a subroutine. Besides, to prove the security of a cryptographic scheme, it is necessarry to define the goals and the capabilities of the adversary. In this paper, we review security models in terms of the adversarial goals and the adversarial capabilities. We define what security actually means to decide whether a scheme is secure. We review the definition of provably security by means of several games between the challenger and the adversary in some security models, namely the standard model and the random oracle model. We state the main differences between these two models and observe the advantage of the success probability of the adversary in breaking the cryptographic schemes. We investigate the security of some public key encryption schemes such as RSA, ElGamal, Cramer-Shoup and discuss under which circumstances they satisfy which security notions.

Keywords

• —provable security, security notions, public key encryption, standard model, random oracle model

References

1. M. Bellare, P. Rogaway, Random oracles are practical: A Paradigm for designing efficient protocols. Proc. of the First ACM Conference on Computer and Communications Security, pp. 62-73, 1993.
2. M. Bellare, P. Rogaway, Optimal Asymmetric Encryption How to encrypt with RSA. Extended abstract in Advances in Cryptology - Proc., LNCS, vol. 950, EUROCRYPT’94.
3. R. Canetti, O. Goldreich, S. Halevi, The random oracle methodology, revisited, Proc. of the 30th ACM Symp. on Theory of Computing (STOC), pp. 209-218, 1998.
4. R. Cramer, Victor Shoup, A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack, Proc. of the 18th Annual International Cryptology Conference on Advances in Cryptology, pp. 13-25, CRYPTO ’98.
5. I. Damgard, Towards Practical Public Key Systems Secure Against Chosen Ciphertext Attacks, In Advances in CryptologyCRYPTO’91.
6. Y. Desmedt, D. Phan, A CCA secure Hybrid Damgard’s ElGamal Encryption, Lecture Notes in Computer Science, vol. 5324, pp. 68-82, 2008.
7. W. Diffie, M. E. Hellman, New Directions in Cryptography, IEEE Transactions on Information Theory, vol. IT-22, pp. 644– 654, 1976.
8. D. Dolev, C. Dwork, M. Naor, Non-Malleable Cryptography, STOC’91.

9. T. Elgamal, A public key cryptosystem and a signature scheme based on discrete logaritms, IEEE Transactions on Information Theory, pp. 469-472, 1984.
10. E.Fujisaki, T.Okamoto, How to Enhance the Security of PublicKey Encryption at Minimum Cost. PKC’99, LNCS 1560, pp. 53-68, 1999.
11. S. Goldwasser, S. Micali, Probabilistic encryption, Journal of Computer and System Sciences, pp. 270–299, 1984.
12. J. Katz, LectureNotes,http://www.cs.umd.edu/ jkatz
13. J. Katz, Y. Lindell, Introduction to Modern Cryptography, 2008.
14. M. Naor, M. Yung, Public key cryptosystems provably secure against chosen ciphertext attacks, Proceedings of the 22-th annual ACM Symposium of Theory and Computing, 1990.
15. M. Rabin, Digitalized Signatures and Public-Key Functions as Intractable as Factorization, MIT Laboratory for Computer Science, January 1979.
16. C. Rackoff, D. Simon, Noninteractive zero-knowledge proof of knowl-edge and chosen ciphertext attack, In Advances in Cryptology, pp. 433-444, CRYPTO’91.
17. R. Rivest, A. Shamir, L. Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, Communications of the ACM 21 (2), pp. 120-126, 1978.
18. Y. Zeng, J. Seberry, Immunizing public key cryptosystems against chosen ciphertext attacks, IEEE Journal on Selected Areas in Communications, 1992.