On Plaintext-Aware Public-Key Encryption Schemes

James Birkett

(2010)

James Birkett (2010) On Plaintext-Aware Public-Key Encryption Schemes.

Our Full Text Deposits

Full text access: Open

Full Text - 766.2 KB

Links to Copies of this Item Held Elsewhere

Mathematics Departmental Web Page

Abstract

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.

Information about this Version

This is a Published version
This version's date is: 15/04/2010
This item is peer reviewed

Link to this Version

https://repository.royalholloway.ac.uk/items/9d38ad1d-2409-ee40-2dc8-2457c278c156/1/

Item TypeThesis (Doctoral)
TitleOn Plaintext-Aware Public-Key Encryption Schemes
AuthorsBirkett, James
DepartmentsFaculty of Science\Mathematics

Deposited by () on 23-Jun-2010 in Royal Holloway Research Online.Last modified on 15-Feb-2017

Notes

References

[1] Jee Hea An, Yevgeniy Dodis, and Tal Rabin. On the security of joint
signature and encryption. In EUROCRYPT, volume 2332 of Lecture Notes
in 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, pages
26{45. Springer, 1998.

[3] Mihir Bellare and Adriana Palacio. Towards plaintext-aware public-key
encryption without random oracles. In ASIACRYPT, volume 3329 of
Lecture Notes in Computer Science, pages 48{62. Springer, 2004.

[4] Mihir Bellare and Phillip Rogaway. Optimal asymmetric encryption. In
EUROCRYPT, volume 950 of Lecture Notes in Computer Science, pages
92{111. Springer, 1994.

[5] James Birkett and Alexander W. Dent. Constructing plaintext-aware
encryption 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. Concrete
chosen-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 security
from identity-based encryption. In EUROCRYPT, volume 3027 of Lecture
Notes 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 cryptosystem
provably 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 paradigm
for 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 in
Computer Science, pages 445{456. Springer, 1991.

[14] Alexander W. Dent. The Cramer-Shoup encryption scheme is plaintext
aware in the standard model. In EUROCRYPT, volume 4004 of Lecture
Notes 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 Jacques
Stern. 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 on
Mathematical 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-random
generation from one-way functions (extended abstracts). In STOC, pages
12{24. ACM, 1989.

[21] Hugo Krawczyk. The order of encryption and authentication for protect-
ing communications (or: How secure is ssl?). In CRYPTO, volume 2139
of Lecture Notes in Computer Science, pages 310{331. Springer, 2001.
186

[22] Kaoru Kurosawa and Yvo Desmedt. A new paradigm of hybrid encryption
scheme. 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. In
CRYPTO, 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 secure
against chosen ciphertext attacks. In STOC, pages 427{437. ACM, 1990.

[26] Juan Manuel Gonz¶alez Nieto, Colin Boyd, and Ed Dawson. A public key
cryptosystem 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 degree
residuosity classes. In EUROCRYPT, volume 1592 of Lecture Notes in
Computer 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 of
Technology, Cambridge, MA, USA, 1979.
187

[29] Charles Racko® and Daniel R. Simon. Non-interactive zero-knowledge
proof of knowledge and chosen ciphertext attack. In CRYPTO, volume
576 of Lecture Notes in Computer Science, pages 433{444. Springer, 1991.

[30] Mario Di Raimondo, Rosario Gennaro, and Hugo Krawczyk. Deniable
authentication and key exchange. In ACM Conference on Computer and
Communications 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 in
security 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 standard
model 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 hash
functions. In FOCS, pages 175{182. IEEE, 1979.

Details