Paper 2010/533

Deterministic Public-Key Encryption Revisited

Adam O'Neill

Abstract

This paper revisits the notion of determinsitic public-key encryption (DE) --- introduced by Bellare, Boldyreva, and O'Neill~(CRYPTO 2007) and further studied by Bellare et al.~(CRYPTO 2008), Boldyreva et al.~(CRYPTO 2008), and Hemenway et al.~(ePrint 2010) --- which hides all possible partial information about high-entropy messages. Our results serve to unify as well as generalize/strengthen the prior work. First, we propose a general construction of DE that reduces the latter to trapdoor functions admitting certain kinds of hardcore functions. Roughly, the latter should be {\em robust}, meaning remain hardcore when the input is conditioned on an event that occurs with good probability; for the resulting DE scheme to be multi-message secure, the hardcore function should also be ``correlated-input secure.'' We then show that most known DE schemes, both in the random oracle and standard models, can be viewed as instantiations of our general construction or optimizations thereof, thereby explaining how these different schemes come about. We also give novel instantiations in the standard model, in both the single and multi-message cases: * In the single-message case, we give an instantiation one-way trapdoor functions, whereas previous constructions based on one-wayness due to Bellare et al.~required a trapdoor permutation. In particular, we can use a trapdoor function that is super-polynomially hard to invert on high-entropy distributions but exponentially-hard to invert on uniform inputs. * In the multi-message case, we give an instantiation meeting a new notion of ``$q$-bounded'' multi-message security we introduce, for any polynomial $q$, based on lossy trapdoor functions losing an $\Omega(1-1/q)$ fraction of their input. Prior work achieved only $q = 1$ in the standard model. We also give an optimized version of this instantiation by extending some ideas of Boldyreva et al. Both of these results are based on generalizations of the (Crooked) Leftover Hash Lemma (LHL) that build on that of Kiltz et al.~(EUROCRYPT 2009). Interestingly, the optimized scheme relies on the fact that the Crooked LHL is more tolerant of ``imperfection'' of the hash function than the classical one. An additional contribution is to give a more precise definitional equivalence (between semantic security and indistinguishability style security notions) for DE as compared to prior work. In particular, this makes our security proofs for instantiations based on one-wayness simpler than in prior work.

Note: Subsumed by report 2012/005