ACE Seminar: Fully secure functional encryption for linear functions from standard assumptions

Speaker: Dr Benoit Libert

Date/Time: 29-Oct-2015, 16:00 UTC

Venue: Birkbeck B30



Functional encryption (FE) is a modern public-key paradigm where a
master secret key can be used to derive sub-keys associated with certain
functions F in such a way that the decryption operation reveals F(M), if
M is the encrypted message, and nothing else. Recently, Abdalla et al.
gave simple and efficient realizations of the primitive for the
computation of linear functions on encrypted data: given an encryption
of a vector y over some specified base ring, a secret key for the vector
x allows computing the inner product x^T y.

Their technique surprisingly allows for instantiations under standard
assumptions, like the hardness of the Decision Diffie-Hellman (DDH) and
Learning-with-Errors (LWE) problems. Their constructions, however, are
only proved secure against selective adversaries, which have to declare
the challenge messages M0 and M1 at the outset of the game.

In this work, we provide constructions that provably achieve security
against more realistic adaptive attacks (where the messages M0 and M1
may be chosen in the challenge phase, based on the previously collected
information) for the same inner product functionality. Our constructions
are obtained from hash proof systems endowed with homomorphic properties
over the key space. They are (almost) as efficient as those of Abdalla
et al. and rely on the same hardness assumptions.

In addition, we obtain a solution based on Paillier's composite
residuosity assumption, which was an open problem even in the case
of selective adversaries.  We also propose LWE-based schemes that
allow evaluation of inner products modulo a prime p, as opposed to
the schemes of Abdalla et al. that are restricted to evaluations of
integer inner products of short integer vectors. We also propose a
solution based on Paillier's composite residuosity assumption that
enables evaluation of inner products modulo an RSA integer N=pq.

We demonstrate that the functionality of inner products over a prime
field is very powerful and can be used to construct bounded collusion FE
for all circuits.

(joint work with Shweta Agrawal and Damien Stehle)


Benoit Libert is a researcher at ENS Lyon. He is interested in
public-key cryptography.His homepage can be found here.

Add to Calendar

This page was last modified on 27 Mar 2014.