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.
Category / Keywords: Weak Pseudo-Random Function, Known-Plaintext Attack, Chosen-Ciphertext Attack, Symmetric Encryption Date: received 24 Feb 2006, last revised 23 Jul 2007 Contact author: jsjoedin at gmail com Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation 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. Version: 20070723:123522 (All versions of this report) Short URL: ia.cr/2006/071 Discussion forum: Show discussion | Start new discussion