International Association for Cryptologic Research

International Association
for Cryptologic Research


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

Alexandra Boldyreva
Serge Fehr
Adam O'Neill
Search ePrint
Search Google
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.
  title={On Notions of Security for Deterministic Encryption, and Efficient Constructions without Random Oracles},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / deterministic encryption, lossy trapdoor functions, leftover hash lemma, standard model},
  note={Preliminary version to appear in CRYPTO 2008 14103 received 12 Aug 2008},
  author={Alexandra Boldyreva and Serge Fehr and Adam O'Neill},