Advertisement

Equivalence between Semantic Security and Indistinguishability against Chosen Ciphertext Attacks

  • Yodai Watanabe
  • Junji Shikata
  • Hideki Imai
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2567)

Abstract

The aim of this work is to examine the relation between the notions of semantic security and indistinguishability against chosen ciphertext attacks. For this purpose, a new security notion called nondividability is introduced independent of attack models, and is shown to be equivalent to each of the previous two notions. This implies the equivalence between semantic security and indistinguishability under any form of attack.

Keywords

Encryption Scheme Attack Model Membership Problem Message Space Security Notion 
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

  1. [1]
    J.H. An, Y. Dodis and T. Rabin, On the security of joint signature and encryption, In Proceedings of Advances in Cryptology–Eurocrypt 2002, Lecture Notes in Computer Science Vol. 2332, L. Knudsen ed., pp. 83–107, Springer-Verlag, 2002. 83Google Scholar
  2. [2]
    M. Bellare, A. Desai, D. Pointcheval and P. Rogaway, Relations among notions of security for public-key encryption schemes. In Proceedings of Advances in Cryptology–Crypto’98, Lecture Notes in Computer Science Vol. 1462, H. Krawczyk ed., pp. 26–45, Springer-Verlag, 1998. The latest version is available from http://wwwcse. ucsd.edu/users/mihir/72, 73, 74, 75Google Scholar
  3. [3]
    M. Bellare and P. Rogaway, Optimal asymmetric encryption. In Proceedings of Advances in Cryptology–Eurocrypt’94, Lecture Notes in Computer Science Vol. 950, A. De Santis ed., pp. 92–111, Springer-Verlag, 1994. 72Google Scholar
  4. [4]
    M. Bellare and A. Sahai, Non-Malleable Encryption: Equivalence between Two Notions, and an Indistinguishability-Based Characterization. In Proceedings of Advances in Cryptology–Crypto’99, Lecture Notes in Computer Science Vol. 1666, M. Wiener ed., pp. 519–536, Springer-Verlag, 1999. 78, 79Google Scholar
  5. [5]
    R. Cramer and V. Shoup, A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack. In Proceedings of Advances in Cryptology–Crypto’98, Lecture Notes in Computer Science Vol. 1462, H. Krawczyk, ed., pp. 13–25, Springer-Verlag 1998. 72Google Scholar
  6. [6]
    D. Dolev, D. Dwork and M. Naor, Non-malleable cryptography, In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, pp. 542–552, 1991; 71 D. Dolev, D. Dwork and M. Naor, Non-malleable cryptography, SIAM Journal on Computing 30, pp. 391–437, 2000.Google Scholar
  7. [7]
    O. Goldreich, Foundations of cryptography: basic tools, Cambridge: New York, Cambridge University Press, 2001. The Volume II of this book is available fromhttp://www.wisdom.weizmann.ac.il/~oded/PSBookFrag/enc2.ps 72, 73, 74, 78
  8. [8]
    O. Goldreich, Foundations of cryptography, Volume II (third posted version), 2002. available from http://www.wisdom.weizmann.ac.il/~oded/PSBookFrag/enc.ps 72
  9. [9]
    O. Goldreich, A uniform complexity treatment of encryption and zero-knowledge, Journal of Cryptology, Vol. 6, pp. 21–53, 1993.Google Scholar
  10. [10]
    S. Goldwasser and S. Micali, Probabilistic encryption. Journal of Computer and System Sciences 28, pp. 270–299, 1984. 71, 72, 73, 74, 78zbMATHCrossRefMathSciNetGoogle Scholar
  11. [11]
    S. Micali, C. Racko. and R. Sloan, The notion of security for probabilistic cryptosystems, SIAM Journal on Computing 17, pp. 412–426, 1988.zbMATHCrossRefMathSciNetGoogle Scholar
  12. [12]
    M. Naor and M. Yung, Public-key cryptosystems provably secure against chosen ciphertext attacks, In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, pp. 427–437, 1990. 72Google Scholar
  13. [13]
    C. Racko. and D. Simon, Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack, In Proceedings of Advances in Cryptology–Crypto’91, Lecture Notes in Computer Science Vol. 576, J. Feigenbaum ed., pp. 433–444, Springer-Verlag, 1991. 72Google Scholar
  14. [14]
    C.E. Shannon, Communication theory of secrecy systems, Bell System Technical Journal 28, pp. 656–715, 1949. 71, 74MathSciNetGoogle Scholar
  15. [15]
    V. Shoup, OAEP Reconsidered, In Proceedings of Advances in Cryptology–Crypto 2001, Lecture Notes in Computer Science Vol. 2139, J. Kilian ed., pp. 239–259, Springer-Verlag, 2001. 72Google Scholar
  16. [16]
    A. Yao, Theory and applications of trapdoor functions, In Proceedings of the 23rd Symposium on Foundations of Computer Science, pp. 80–91, IEEE, 1982.Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2003

Authors and Affiliations

  • Yodai Watanabe
    • 1
  • Junji Shikata
    • 2
  • Hideki Imai
    • 3
  1. 1.RIKEN Brain Science InstituteSaitamaJapan
  2. 2.Graduate School of Environment and Information SciencesYokohama National UniversityYokohamaJapan
  3. 3.Institute of Industrial ScienceUniversity of TokyoTokyoJapan

Personalised recommendations