Paper 2012/005

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

Benjamin Fuller, Adam O'Neill, and Leonid Reyzin

Abstract

This paper addresses deterministic public-key encryption schemes (DE), which are designed to provide meaningful security when only source of randomness in the encryption process comes from the message itself. We propose a general construction of DE that unifies prior work and gives novel schemes. Specifically, its instantiations include: -The first construction from any trapdoor function that has sufficiently many hardcore bits. -The first construction that provides "bounded" multi-message security (assuming 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 paper appeared in Theory of Cryptology 2012. This version has significant new material and appears in Journal of Cryptology 2013.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in TCC 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
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/005,
      author = {Benjamin Fuller and Adam O'Neill and Leonid Reyzin},
      title = {A Unified Approach to Deterministic Encryption: New Constructions and a Connection to Computational Entropy},
      howpublished = {Cryptology ePrint Archive, Paper 2012/005},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/005}},
      url = {https://eprint.iacr.org/2012/005}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.