Cryptology ePrint Archive: Report 2008/352

On Notions of Security for Deterministic Encryption, and Efficient Constructions without Random Oracles

Alexandra Boldyreva and Serge Fehr and Adam O'Neill

Abstract: The study of deterministic public-key encryption was initiated by Bellare et al. (CRYPTO~'07), who provided the ``strongest possible" notion of security for this primitive (called PRIV) and constructions in the random oracle (RO) model. We focus on constructing efficient deterministic encryption schemes \emph{without} random oracles. To do so, we propose a slightly weaker notion of security, saying that no partial information about encrypted messages should be leaked as long as each message is a-priori hard-to-guess \emph{given the others} (while PRIV did not have the latter restriction). Nevertheless, we argue that this version seems adequate for certain practical applications. We show equivalence of this definition to single-message and indistinguishability-based ones, which are easier to work with. Then we give general constructions of both chosen-plaintext (CPA) and chosen-ciphertext-attack (CCA) secure deterministic encryption schemes, as well as efficient instantiations of them under standard number-theoretic assumptions. Our constructions build on the recently-introduced framework of Peikert and Waters (STOC '08) for constructing CCA-secure \emph{probabilistic} encryption schemes, extending it to the deterministic-encryption setting and yielding some improvements to their original results as well.

Category / Keywords: public-key cryptography / deterministic encryption, lossy trapdoor functions, leftover hash lemma, standard model

Publication Info: Preliminary version to appear in CRYPTO 2008

Date: received 12 Aug 2008, last revised 29 Jul 2009

Contact author: amoneill at cc gatech edu

Available format(s): PDF | BibTeX Citation

Version: 20090729:110016 (All versions of this report)

Short URL: ia.cr/2008/352

Discussion forum: Show discussion | Start new discussion