Paper 2016/440

Function-Hiding Inner Product Encryption is Practical

Sam Kim, Kevin Lewi, Avradip Mandal, Hart Montgomery, 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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Major revision. SCN 2018
Keywords
functional encryptioninner product encryptionbilinear maps
Contact author(s)
klewi @ cs stanford edu
History
2018-06-13: last of 2 revisions
2016-05-04: received
See all versions
Short URL
https://ia.cr/2016/440
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/440,
      author = {Sam Kim and Kevin Lewi and Avradip Mandal and Hart Montgomery and Arnab Roy and David J.  Wu},
      title = {Function-Hiding Inner Product Encryption is Practical},
      howpublished = {Cryptology ePrint Archive, Paper 2016/440},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/440}},
      url = {https://eprint.iacr.org/2016/440}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.