Cryptology ePrint Archive: Report 2015/608

Fully Secure Functional Encryption for Inner Products, from Standard Assumptions

Benoit Libert and Damien Stehle

Abstract: Functional encryption is a modern public-key paradigm where a master private key can be used to derive sub-keys $SK_F$ 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 {\it 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 $\vec{y} \in \Z_q^\ell$, a private key $SK_{\vec{x}}$ for the vector $\vec{x} \in \Z_q^\ell$ allows computing $\langle \vec{x} ,\vec{y} \rangle$. 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 {\it selective} adversaries, which have to declare the challenge messages $M_0$ and $M_1$ at the outset of the game. In this paper, we provide constructions that provably achieve security against more realistic {\it adaptive} attacks (where the messages $M_0$ and $M_1$ 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 as efficient as those of Abdalla {\it et al.} and rely on the same assumptions. As a result of independent interest, we prove the security of our $\LWE$-based system via a new result on the hardness of the extended $\LWE$ problem, where the distinguisher receives hints about the noise distribution.

Category / Keywords: public-key cryptography / Functional encryption, adaptive security, standard assumptions, DDH, LWE, extended LWE

Date: received 20 Jun 2015, last revised 29 Jun 2015, withdrawn 5 Aug 2015

Contact author: benoit libert at gmail com

Available format(s): (-- withdrawn --)

Note: Found a bug, will re-post the paper when bug is fixed.

Version: 20150805:093052 (All versions of this report)

Short URL: ia.cr/2015/608

Discussion forum: Show discussion | Start new discussion