Cryptology ePrint Archive: Report 2016/440

Function-Hiding Inner Product Encryption is Practical

Sam Kim and Kevin Lewi and Avradip Mandal and Hart Montgomery and Arnab Roy and David J. Wu

Abstract: In a functional encryption scheme, secret keys are associated with functions and ciphertexts are associated with messages. Given a secret key for a function f, and a ciphertext for a message x, a decryptor learns f(x) and nothing else about x. Inner product encryption is a special case of functional encryption where both secret keys and ciphertext are associated with vectors. The combination of a secret key for a vector x and a ciphertext for a vector y reveal <x, y> and nothing more about y. An inner product encryption scheme is function- hiding if the keys and ciphertexts reveal no additional information about both x and y beyond their inner product.

In the last few years, there has been a flurry of works on the construction of function-hiding inner product encryption, starting with the work of Bishop, Jain, and Kowalczyk (Asiacrypt 2015) to the more recent work of Tomida, Abe, and Okamoto (ISC 2016). In this work, we focus on the practical applications of this primitive. First, we show that the parameter sizes and the run-time complexity of the state-of-the-art construction can be further reduced by another factor of 2, though we compromise by proving security in the generic group model. We then show that function privacy enables a number of applications in biometric authentication, nearest-neighbor search on encrypted data, and single-key two-input functional encryption for functions over small message spaces. Finally, we evaluate the practicality of our encryption scheme by implementing our function-hiding inner product encryption scheme. Using our construction, encryption and decryption operations for vectors of length 50 complete in a tenth of a second in a standard desktop environment.

Category / Keywords: secret-key cryptography / functional encryption, inner product encryption, bilinear maps

Original Publication (with major differences): SCN 2018

Date: received 3 May 2016, last revised 13 Jun 2018

Contact author: klewi at cs stanford edu

Available format(s): PDF | BibTeX Citation

Version: 20180613:204744 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]