Vinod Vaikuntanathan: Fully Key Homomorphic Encryption and Applications

We introduce the notion of a fully *key*-homomorphic encryption
scheme, construct such a scheme based on the learning with errors
assumption, and show a number of applications, including:

* attribute-based and functional encryption schemes with
super-compact keys;

* a reusable garbled circuits construction where the garbling
of a circuit C has size |C| + poly(k), k being a security
parameter; and

* a reusable garbled Turing machine construction where the
garbling of a TM M has size |M| + poly(k), *independent* of M's
running time.

In contrast, all previous constructions of (even single-use)
garbled circuits suffered from a multiplicative poly(k) blowup,
and there were no constructions of (even single-use) garbled
Turing machines from falsifiable cryptographic assumptions.