A Fast and Key-Efficient Reduction of Chosen- Ciphertext to Known-Plaintext Security

Ueli Maurer; Johan Sjödin

Paper 2006/071

A Fast and Key-Efficient Reduction of Chosen- Ciphertext to Known-Plaintext Security

Ueli Maurer and Johan Sjödin

Abstract

Motivated by the quest for reducing assumptions in security proofs in cryptography, this paper is concerned with designing efficient symmetric encryption and authentication schemes based on any weak pseudorandom function (PRF) which can be much more efficiently implemented than PRFs. Damgard and Nielsen (CRYPTO '02) have shown how to construct an efficient symmetric encryption scheme based on any weak PRF that is provably secure against chosen-plaintext attacks. The main ingredient is a range-extension construction for weak PRFs. By using well-known techniques, they also showed how their scheme can be made secure against the stronger chosen-ciphertext attacks. The results of our paper are three-fold. First, we give a range-extension construction for weak PRFs that is optimal within a large and natural class of reductions (especially all known today). Second, we propose a construction of a regular PRF from any weak PRF. Third, these two results imply a (for long messages) much more efficient chosen-ciphertext secure encryption scheme than the one proposed by Damgard and Nielsen. The results also give answers to open questions posed by Naor and Reingold (CRYPTO '98) and by Damgard and Nielsen.

Note: An earlier version of this paper was published unter the title "From Known-Plaintext to Chosen-Ciphertext Security". This is the EUROCRYPT '07 version.

Metadata

Available format(s): PDF PS
Publication info: Published elsewhere. Unknown where it was published
Keywords: Weak Pseudo-Random Function Known-Plaintext Attack Chosen-Ciphertext Attack Symmetric Encryption
Contact author(s): jsjoedin @ gmail com
History: 2007-07-23: last of 2 revisions; 2006-02-24: received; See all versions
Short URL: https://ia.cr/2006/071
License: CC BY

BibTeX

@misc{cryptoeprint:2006/071,
      author = {Ueli Maurer and Johan Sjödin},
      title = {A Fast and Key-Efficient Reduction of Chosen- Ciphertext to Known-Plaintext Security},
      howpublished = {Cryptology {ePrint} Archive, Paper 2006/071},
      year = {2006},
      url = {https://eprint.iacr.org/2006/071}
}