Deterministic Encryption: Definitional Equivalences and Constructions without Random Oracles
Adam O'Neill, and
We strengthen the foundations of deterministic public-key encryption via definitional
equivalences and standard-model constructs based on general assumptions. Specifically
we consider seven notions of privacy for deterministic encryption, including six
forms of semantic security and an indistinguishability notion, and show them all
equivalent. We then present a deterministic scheme for the secure encryption of
uniformly and independently distributed messages based solely on the existence of
trapdoor one-way permutations. We show a generalization of the construction that
allows secure deterministic encryption of independent high-entropy messages.
Finally we show relations between deterministic and standard (randomized)
A preliminary version of this paper will appear in Advances in Cryptology -- CRYPTO '08.
Full version of the paper is available as a pdf.
List of Updates:
February 2009 - Fixed a couple of typos in full version of paper.
June 2008 - Put up full version of paper.