Paper 2008/352

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

Alexandra Boldyreva, Serge Fehr, and Adam O'Neill


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.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Preliminary version to appear in CRYPTO 2008
deterministic encryptionlossy trapdoor functionsleftover hash lemmastandard model
Contact author(s)
amoneill @ cc gatech edu
2009-07-29: last of 2 revisions
2008-08-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Alexandra Boldyreva and Serge Fehr and Adam O'Neill},
      title = {On Notions of Security for Deterministic Encryption, and Efficient Constructions without Random Oracles},
      howpublished = {Cryptology ePrint Archive, Paper 2008/352},
      year = {2008},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.