**A Unified Approach to Deterministic Encryption: New Constructions and a Connection to Computational Entropy**

*Benjamin Fuller and Adam O'Neill and Leonid Reyzin*

**Abstract: **We propose a general construction of deterministic encryption schemes that unifies prior work and gives novel schemes. Specifically, its instantiations provide:

- A construction from any trapdoor function that has sufficiently many hardcore bits.

- A construction that provides "bounded" multi-message security from lossy trapdoor functions.

The security proofs for these schemes are enabled by three tools that are of broader interest:

- A weaker and more precise sufficient condition for semantic security on a high-entropy message distribution. Namely, we show that to establish semantic security on a distribution M of messages, it suffices to establish indistinguishability for all conditional distribution M|E, where E is an event of probability at least 1/4. (Prior work required indistinguishability on all distributions of a given entropy.)

- A result about computational entropy of conditional distributions. Namely, we show that conditioning on an event E of probability p reduces the quality of computational entropy by a factor of p and its quantity by log_2 1/p.

- A generalization of leftover hash lemma to correlated distributions.

We also extend our result about computational entropy to the average case, which is useful in reasoning about leakage-resilient cryptography: leaking \lambda bits of information reduces the quality of computational entropy by a factor of 2^\lambda and its quantity by \lambda.

**Category / Keywords: **public-key cryptography / Deterministic encryption, trapdoor functions, hardcore functions, computational entropy, $q$-bounded security

**Publication Info: **Short version to appear in Theory of Cryptography 2012

**Date: **received 3 Jan 2012, last revised 20 Aug 2012

**Contact author: **bfuller at cs bu edu

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Note: **This revision corrects some errors and has more complete proofs.

**Version: **20120821:043734 (All versions of this report)

**Short URL: **ia.cr/2012/005

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]