Fully Secure Functional Encryption for Inner
Products, from Standard Assumptions
Shweta Agrawal, Benoît Libert and Damien Stehlé
Abstract: Functional encryption is a modern public-key paradigm where
a master secret key can be used to derive sub-keys SKF 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 effient realizations
of the primitive for the computation of linear functions on encrypted
data: given an encryption of a vector y over some specific base ring,
a secret key SKx for the vector x allows computing hx;yi. 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 paper, 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 finally propose a
solution based on Paillier's composite residuosity assumption that
enables evaluation of inner products modulo an RSA integer N = p q.
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.
Download: pdf.
Homepage