Paper 2012/005
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.
Note: This revision corrects some errors and has more complete proofs.
Metadata
- Available format(s)
- PDF PS
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. Short version to appear in Theory of Cryptography 2012
- Keywords
- Deterministic encryptiontrapdoor functionshardcore functionscomputational entropy$q$-bounded security
- Contact author(s)
- bfuller @ cs bu edu
- History
- 2014-01-07: last of 7 revisions
- 2012-01-05: received
- See all versions
- Short URL
- https://ia.cr/2012/005
- License
-
CC BY