Deterministic Public-Key Encryption Schemes

Today reading group has been given by Ming-Feng and Peter. Their presentation focused on public-key deterministic encryption. In particular, Ming-Feng outlined the results in the Crypto08 paper by Boldyreva, Fehr and O'Neill  [BFO] while Peter described more recent results by Fuller, O'Neill and Reyzin [FOR].

Ming-Feng started the presentation by describing three security definitions: PRIV, PRIV-1 and PRIV-IND. PRIV requires that, given the encryption of a list of messages, it is hard to guess any partial information about these messages, as long as each message has high entropy given the others.

PRIV-1 is  the single-message version of PRIV and PRIV-IND requires that it is hard to distinguish the encryption of two messages drawn from a different high-entropy distribution on the message space.

Ming-Feng mentioned that the above three definitions are equivalent. Then, he moved to describe

two general constructions: a CPA-secure scheme and a CCA-secure one.

For the CPA-secure construction we need the notion of deterministic encryption with Hidden Hash Mode (HHM). Informally, we say that AE=(K, K1, E, D) is a HHM deterministic encryption scheme if (K,E,D) is a deterministic encryption scheme, K1 is a key generation algorithm which produces only a public key and induces a hash function and any poly-time adversary has negligible advantage in distinguishing the first output of K from that of K1. For a formal definition of HHM deterministic encryption see [BFO] (pag. 14). A HHM deterministic encryption scheme where the hash function induced by K1 is universal is PRIV-secure.      

Finally, Ming-Feng described the CCA-secure construction which makes use of universal target-collision resistant hash functions and lossy trapdoor functions that operate in two possible modes, injective one and a lossy mode. Details of the construction are in [BFO] (pag. 15).

In the second part of the presentation, Peter gave details and the idea behind the deterministic encryption scheme based on trapdoor functions in  [FOR]. The scheme follows the Encrypt-with-Hardcore (EwHCore) paradigm: let E be any public-key encryption algorithm and let f be a TDF with a hardcore function hc. A message m is encrypted as follows: y = f (m) and then y is encrypted using

E with hc(m) as randomness, (i.e., the encryption of m is E (f (m); hc(m))).

The output of hc must be long enough to provide sufficient randomness for the encryption algorithm.

and satisfy an extra property called ``robustness``.

Finally, Peter mentioned that possible instantiations of hard-core functions  can be obtained from iterated trapdoor permutation and Lossy TDFs.