Valeria Nikolaenko (Theory Seminar W14)

nikolaenko.jpg"Fully Key Homomorphic Encryption and Applications: Compressed Garbled Circuits and Arithmetic ABE with Short Keys"
Valeria Nikolaenko
Monday, January 13th, 2014, 2:00 pm
EBU3B, Room 4140
We will present a new notion of key homomorphic public-key encryption and show how to use it to build arithmetic Attribute Based Encryption (ABE) with short keys and how to compress (reusable) garbled circuits. All of these constructions are based on the subexponential hardness of the learning with errors problem on integer lattices.

In the ABE system the access policies are expressed as polynomial size arithmetic circuits. We prove security against arbitrary collusions of users. The system has two additional useful properties: first, it naturally handles arithmetic circuits with arbitrary fan-in (and fan-out) gates. Second, secret keys are much shorter than in previous schemes: secret key size is proportional to the depth of the circuit where as in previous constructions the key size was proportional to the number of gates or wires in the circuit. The system also provides complete key delegation capabilities.

The reusable garbling scheme produces garbled circuit that are of the same size as the original circuit plus an additive poly(secp) bits, where secp is the security parameter. In contrast, all previous constructions of even single-use garbled circuits incurred a multiplicative poly(secp) blowup.

Joint work with D. Boneh, G. Segev, C. Gentry, S. Gorbunov, S. Halevi, V. Vaikuntanathan, D. Vinayagamurthy