Paper 2019/817

Non-zero Inner Product Encryptions: Strong Security under Standard Assumptions

Tapas Pal and Ratna Dutta

Abstract

Non-zero inner product encryption (NIPE) allows a user to encrypt a message with its attribute vector and decryption is possible using a secret-key associated with a predicate vector if the inner product of the vectors is non-zero. The concept of NIPE was put forth by Katz, Sahai and Waters (EUROCRYPT 2008). Following that many NIPE constructions were proposed along with interesting applications. The security of all these works is based on hardness assumptions in pairing-friendly groups. Recently, Katsumata and Yamada (PKC 2019) built a NIPE relying on the Learning-with-Errors (LWE) problems, however, their system practically lags behind for providing only selective security with significantly large sizes of master public-key, secret-keys and ciphertexts. Despite its cryptographic importance, past history of NIPE is not convincing in terms of both security and practical efficiency as the schemes are either selectively secure or depend on bilinear maps. In this paper, our goal is to construct adaptively secure efficient NIPEs. Firstly, we provide adaptively secure public-key NIPE under the standard Decision Diffie-Hellman (DDH) assumption that enables one to encrypt messages of sufficiently small length. To overcome this limitation we rely on the Decision Diffie-Hellman-f (DDH-f) and the Hard Subgroup Membership (HSM) assumptions proposed by Castagnos et al. in ASIACRYPT 2018. Consequently, we construct two pNIPEs, adaptively secure under the DDH-f and HSM assumptions respectively, both are capable of encrypting large messages with inner products over integers. We upgrade these two pNIPEs so that it can encrypt messages with unbounded inner products modulo an arbitrary large prime p. In addition, utilizing inner product functional encryptions we provide attribute-hiding public-key NIPEs depending on the DDH, DDH-f, HSM, LWE, Decision Composite Reciprocity assumptions and establish full-hiding private-key NIPEs based on the Decision linear and Symmetric External Diffie-Hellman assumptions.