TCC : Tuesday PM

Draging oneself away from the lovely views of Mount Etna in Taormina to go to a bunch of talks on cryptography can be difficult. But the talks this afternoon made it worthwhile. There were a total of eight talks, so I only select a few highlights (mainly from the first part on PRFs).

The first two talks on constructing PRF's I thought were particularly well delivered. The first by Berman and Haitner looked at the problem of constructing an adaptively secure PRF (i.e. the adversaries queries are determined adaptively) from a weaker PRF (namely a non-adaptive PRF) F and a pairwise independent hash function H. The speaker showed that this could be done by simply applying H and then applying F; the hash function however needed to be restricted to have co-domain the size of the "running time" T of an adversary that could break F with probability 1/T. 

The second talk by Jain, Pietrzak and Tentes took a different approach to constructing a PRF namely from a PRG G whose co-domain is twice that of the input size. The trick was quite neat. Firstly they look athe GGM construction which compute PRF(k,x) in two steps:

•  First write G(y) as two functions G_0(y)||G_1(y) where G_i has co-domain n-bits in length.
• Write x in binary as x_n,....,x_1
• Output G_{x_n}(G_{x_{n-1}}(....G_{x_1}(k)))

Call this function GGM(k,x). This function requires we call the function G n-times to evaluate it on a string of size n bits.  A trick of Levin is to first apply a hash function with co-domain m-bit strings so as to compute the function  GGM(k,H(x)).  Which requires m calls of the PRG G, although the key-size of the PRF increases since one needs a key for the hash function H (I have hid this in the notation above).

The problem is that this has problems due to collisions in G. To get around this the authors propose the following construction

H'(GGM(k,H(x)),x)

where H' is different a keyed hash function with key GGM(k,H(x)) and message x. I thought this was rather neat myself.

The short mini-session on PRFs was completed by a talk by Krawczyk (co-authors Dachman-Soled, Gennaro and Malkin) who looked at various theoretical aspects, but at the end concluded that the PRF used in the TLS implementation of Diffie-Hellman key exchange is secure. This was much to Hugo's "distress" as he did not think it should be morally secure at all, so it was a surprise when it was indeed shown to be secure. 

For the other talks I had seen many of the papers before, so I was not so surprised or interested (such is the effect of e-Print on conference attention spans). However, the "Verifiable Computation from ABE" paper is definitely worth a look for people interested in this area. The key contribution is that they produce a VC scheme without needing FHE or PCP's (both being rather inefficient). They do this by utilizing an ABE. However, the efficiency of their own solution is still not really useful, since the scheme is based on functions with single-bit outputs, to extend the technique to other bit-lengths one needs to keep repeating the technique. Given the underlying techniques are ABE, which themselves are not that (practically) efficient, there seemed a lot of room for further work in this area.