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

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

λ

bits of information reduces the quality of computational entropy by a factor of 2

λ

and its quantity by

λ

.