-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.
Category / Keywords: public-key cryptography / Deterministic encryption, trapdoor functions, hardcore functions, computational entropy, $q$-bounded security Original Publication (with major differences): IACR-TCC-2012 Date: received 3 Jan 2012, last revised 7 Jan 2014 Contact author: bfuller at cs bu edu Available format(s): PDF | BibTeX Citation Note: This paper appeared in Theory of Cryptology 2012. This version has significant new material and appears in Journal of Cryptology 2013. Version: 20140107:203142 (All versions of this report) Short URL: ia.cr/2012/005 Discussion forum: Show discussion | Start new discussion