Abstract
Inner product functional encryption (IPFE) is a primitive which produces, from a master secret key, decryption keys sk k associated to vectors k over some specified base ring. Decrypting an encryption of vector m with sk k only reveals <k, m>. Benhamouda et al. [BBL17] provided a generic construction for CCA-secure IPFE from projective hash functions (PHFs), unfortunately their security reduction suffers an exponential loss. Their only instantiation capable of decrypting inner products of large sizes, which relies on the decisional composite residuosity (DCR) assumption, is impractical due to the large size of ciphertexts, decryption keys, and the prohibitive speed of the scheme. Our core contribution is a new approach to proving CCA security. Our constructions maintain the genericity of [BBL17], while our security proof relaxes the requirements on the underlying PHFs and gains in reduction tightness. We instantiate these constructions from the DCR assumption, an assumption in class groups (HSM CL) and the decision Diffie Hellman (DDH) assumption. Our CCA-secure constructions from DCR and HSM CL are the first such schemes to efficiently decrypt inner products of large size, improving by multiple orders of magnitude upon the work of [BBL17]. A single-core C implementation of these schemes shows that, for a 112 bit security, and 100−dimensional vectors, their DCR-based scheme takes 1h20min to encrypt, and over 5min to decrypt, whereas our slowest scheme takes 5.2s to encrypt and 0.5s to decrypt. Similarly a ciphertext for their scheme is of 283MB; those of our HSM CL-based scheme are of 30kB.