Function-Hiding Inner Product Encryption is Practical

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



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 ciphertexts 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 ybeyond their inner product.

Recently, Bishop, Jain, and Kowalczyk (Asiacrypt 2015) and Datta, Dutta, and Mukhopadhyay (PKC 2016) showed how to construct function-hiding inner product encryption using asymmetric bilinear maps with security in the standard model. In this work, we reduce the parameter sizes and the run-time complexity of the Asiacrypt 2015 and the PKC 2016 constructions by more than a factor of 2 and 4, respectively. We achieve this efficiency by proving security in the generic group model. We then show how function-hiding inner product encryption directly yields single-key two-input functional encryption for general functions over a small message space, which greatly improves upon the parameter sizes of existing constructions from standard assumptions. We validate the practicality of our encryption scheme by implementing both function-hiding inner product encryption and single-key two-input functional encryption. For example, using our construction, encryption and decryption operations for vectors of length 50 complete in a tenth of a second in a standard desktop environment.

  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},
  misc   = {Full version available at \url{}},
  year   = {2016}