* 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.Category / Keywords: public-key cryptography / Deterministic encryption, trapdoor functions, hardcore funtions, lossy trapdoor functions, $q$-bounded security Date: received 18 Oct 2010, last revised 24 Mar 2011, withdrawn 5 Jan 2012 Contact author: adamo at cs utexas edu Available format(s): (-- withdrawn --) Note: Subsumed by report 2012/005 Version: 20120105:145532 (All versions of this report) Short URL: ia.cr/2010/533 Discussion forum: Show discussion | Start new discussion