## Tuesday, May 22, 2012

### 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.