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)))
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.
No comments:
Post a Comment