James Birkett (2010) On Plaintext-Aware Public-Key Encryption Schemes.
Full text access: Open
Plaintext awareness is a property of a public-key encryption scheme intended to capture the idea that the only way to produce a valid ciphertext is to take a message and encrypt it. The idea is compelling, but the devil, as always, is in the details. The established de¯nition of plaintext awareness in the standard model is known as PA2 plaintext awareness and was introduced by Bellare and Palacio. We propose a modi¯ed de¯nition of plaintext awareness, which we call 2PA2, in which the arbitrary stateful plaintext creators of the PA2 de¯nition are replaced with a choice of two ¯xed stateless plaintext creators. We show that under reasonable conditions our new de¯nition is equivalent to the standard one. We also adapt techniques used by Teranishi and Ogata to show that no encryption scheme which allows arbitrarily long messages can be PA2 plaintext aware, a disadvantage which our new de¯nition does not appear to share. Dent has shown that a variant of the Cramer-Shoup encryption scheme based on the Di±e-Hellman problem is PA2 plaintext aware under the Di±e- Hellman Knowledge (DHK) assumption. We present a generalisation of this assumption to arbitrary subset membership problems, which we call the Sub- set Witness Knowledge (SWK) assumption, and use it to show that the generic Cramer-Shoup and Kurosawa-Desmedt encryption schemes based on hash proof systems are plaintext aware. In the case of the Di±e-Hellman problem, the SWK assumption is exactly the Di±e-Hellman Knowledge assumption, but we also discuss several other possible instantiations of this assumption.
This is a Published version This version's date is: 15/04/2010 This item is peer reviewed
https://repository.royalholloway.ac.uk/items/9d38ad1d-2409-ee40-2dc8-2457c278c156/1/
Deposited by () on 23-Jun-2010 in Royal Holloway Research Online.Last modified on 15-Feb-2017
[1] Jee Hea An, Yevgeniy Dodis, and Tal Rabin. On the security of jointsignature and encryption. In EUROCRYPT, volume 2332 of Lecture Notesin Computer Science, pages 83{107. Springer, 2002.
[2] Mihir Bellare, Anand Desai, David Pointcheval, and Phillip Rogaway.Relations among notions of security for public-key encryption schemes.In CRYPTO, volume 1462 of Lecture Notes in Computer Science, pages26{45. Springer, 1998.
[3] Mihir Bellare and Adriana Palacio. Towards plaintext-aware public-keyencryption without random oracles. In ASIACRYPT, volume 3329 ofLecture Notes in Computer Science, pages 48{62. Springer, 2004.
[4] Mihir Bellare and Phillip Rogaway. Optimal asymmetric encryption. InEUROCRYPT, volume 950 of Lecture Notes in Computer Science, pages92{111. Springer, 1994.
[5] James Birkett and Alexander W. Dent. Constructing plaintext-awareencryption schemes. 2007. Unpublished Manuscript.
[6] Dan Boneh. Simpli¯ed oaep for the rsa and rabin functions. In CRYPTO,volume 2139 of Lecture Notes in Computer Science, pages 275{291.Springer, 2001.
[7] Jaimee Brown, Juan Manuel Gonz¶alez Nieto, and Colin Boyd. Concretechosen-ciphertext secure encryption from subgroup membership prob-lems. In CANS, volume 4301 of Lecture Notes in Computer Science,pages 1{18. Springer, 2006.
[8] Ran Canetti, Shai Halevi, and Jonathan Katz. Chosen-ciphertext securityfrom identity-based encryption. In EUROCRYPT, volume 3027 of LectureNotes in Computer Science, pages 207{222, 2004.
[9] Ran Canetti, Hugo Krawczyk, and Jesper Buus Nielsen. Relaxing chosen-ciphertext security. In CRYPTO, volume 2729 of Lecture Notes in Com-puter Science, pages 565{582. Springer, 2003.
[10] Ronald Cramer and Victor Shoup. A practical public key cryptosystemprovably secure against adaptive chosen ciphertext attack. In CRYPTO,volume 1462 of Lecture Notes in Computer Science, pages 13{25. Springer,1998.
[11] Ronald Cramer and Victor Shoup. Universal hash proofs and a paradigmfor adaptive chosen ciphertext secure public-key encryption. In EURO-CRYPT, volume 2332 of Lecture Notes in Computer Science, pages 45{64.Springer, 2002.
[12] Ronald Cramer and Victor Shoup. Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack.SIAM Journal on Computing, 33(1):167{226, 2003.
[13] Ivan Damgºard. Towards practical public key systems secure against cho-sen ciphertext attacks. In CRYPTO, volume 576 of Lecture Notes inComputer Science, pages 445{456. Springer, 1991.
[14] Alexander W. Dent. The Cramer-Shoup encryption scheme is plaintextaware in the standard model. In EUROCRYPT, volume 4004 of LectureNotes in Computer Science, pages 289{307. Springer, 2006.
[15] W. Di±e and M. Hellman. New directions in cryptography. IEEE Trans-actions on Information Theory, 22:644{654, 1976.
[16] Eiichiro Fujisaki, Tatsuaki Okamoto, David Pointcheval, and JacquesStern. Rsa-oaep is secure under the rsa assumption. In CRYPTO, vol-ume 2139 of Lecture Notes in Computer Science, pages 260{274. Springer,2001.
[17] D. Galindo and J. L. Villar. An instantiation of the Cramer-Shoup en-cryption paradigm using bilinear map groups. In Proc. Workshop onMathematical Problems and Techniques in Cryptology, Bellaterra, Spain,2005.
[18] Sha¯ Goldwasser and Silvio Micali. Probabilistic encryption. J. Comput.Syst. Sci., 28(2):270{299, 1984.
[19] Johan Hºastad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby.A pseudorandom generator from any one-way function. SIAM J. Comput.,28(4):1364{1396, 1999.
[20] Russell Impagliazzo, Leonid A. Levin, and Michael Luby. Pseudo-randomgeneration from one-way functions (extended abstracts). In STOC, pages12{24. ACM, 1989.
[21] Hugo Krawczyk. The order of encryption and authentication for protect-ing communications (or: How secure is ssl?). In CRYPTO, volume 2139of Lecture Notes in Computer Science, pages 310{331. Springer, 2001.186
[22] Kaoru Kurosawa and Yvo Desmedt. A new paradigm of hybrid encryptionscheme. In CRYPTO, volume 3152 of Lecture Notes in Computer Science,pages 426{442. Springer, 2004.
[23] James Manger. A chosen ciphertext attack on rsa optimal asymmet-ric encryption padding (oaep) as standardized in pkcs #1 v2.0. InCRYPTO, volume 2139 of Lecture Notes in Computer Science, pages 230{238. Springer, 2001.
[24] Moni Naor. On cryptographic assumptions and challenges. In CRYPTO,volume 2729 of Lecture Notes in Computer Science, pages 96{109.Springer, 2003.
[25] Moni Naor and Moti Yung. Public-key cryptosystems provably secureagainst chosen ciphertext attacks. In STOC, pages 427{437. ACM, 1990.
[26] Juan Manuel Gonz¶alez Nieto, Colin Boyd, and Ed Dawson. A public keycryptosystem based on the subgroup membership problem. In ICICS, vol-ume 2229 of Lecture Notes in Computer Science, pages 352{363. Springer,2001.
[27] Pascal Paillier. Public-key cryptosystems based on composite degreeresiduosity classes. In EUROCRYPT, volume 1592 of Lecture Notes inComputer Science, pages 223{238. Springer, 1999.
[28] M. O. Rabin. Digitalized signatures and public-key functions as in-tractable as factorization. Technical report, Massachusetts Institute ofTechnology, Cambridge, MA, USA, 1979.187
[29] Charles Racko® and Daniel R. Simon. Non-interactive zero-knowledgeproof of knowledge and chosen ciphertext attack. In CRYPTO, volume576 of Lecture Notes in Computer Science, pages 433{444. Springer, 1991.
[30] Mario Di Raimondo, Rosario Gennaro, and Hugo Krawczyk. Deniableauthentication and key exchange. In ACM Conference on Computer andCommunications Security, pages 400{409. ACM, 2006.
[31] Victor Shoup. A proposal for an iso standard for public key encryption.Cryptology ePrint Archive, Report 2001/112, 2001. http://eprint.iacr.org/2001/112.
[32] Victor Shoup. Sequences of games: A tool for taming complexity insecurity proofs. Cryptology ePrint Archive, Report 2004/332, 2004. http://eprint.iacr.org/2004/332.
[33] Victor Shoup. A Computational Introduction to Number Theory and Al-gebra. Cambridge University Press, 2005.
[34] Isamu Teranishi and Wakaha Ogata. Relationship between standardmodel plaintext awareness and message hiding. In ASIACRYPT, vol-ume 4284 of Lecture Notes in Computer Science, pages 226{240. Springer,2006.
[35] Mark N. Wegman and Larry Carter. New classes and applications of hashfunctions. In FOCS, pages 175{182. IEEE, 1979.