Attribute-Based Encryption for Circuits and Inner-Product Predicate Encryption from Middle-Product LWE

The Middle-Product Learning with Errors ( \(\textsf{MPLWE}\) ) assumption is a variant of the Learning with Errors ( \(\textsf{LWE}\) ) assumption. \(\textsf{MPLWE}\) reduces the key size of corresponding \(\textsf{LWE}\) -based schemes by representing keys as sets of polynomials. Moreover, \(\textsf{MPLWE}\) has more robust security than other \(\textsf{LWE}\) variants such as Ring- \(\textsf{LWE}\) and Module- \(\textsf{LWE}\) . Since Boneh et al. introduced homomorphic evaluation algorithms for circuits, many \(\textsf{LWE}\) -based attribute-based encryption ( \(\textsf{ABE}\) ) schemes have been constructed based on their techniques. However, no \(\textsf{MPLWE}\) -based \(\textsf{ABE}\) schemes have been proposed so far. In this paper, we propose the first \(\textsf{MPLWE}\) -based \(\textsf{ABE}\) scheme. A natural approach is to modify Boneh et al.’s algorithms to obtain a variant compatible with \(\textsf{MPLWE}\) . However, we observe that designing such homomorphic evaluation algorithms for circuits in the \(\textsf{MPLWE}\) setting is non-trivial. Instead, we directly employ Boneh et al.’s algorithms while adapting the setup and encryption algorithms to \(\textsf{MPLWE}\) . As a result, although the secret key size remains asymptotically the same as in Boneh et al.’s scheme, our scheme achieves smaller master public keys. Furthermore, we propose an efficient \(\textsf{MPLWE}\) -based inner-product predicate encryption ( \(\textsf{IPE}\) ) scheme. Our key observation is that, while designing homomorphic evaluation algorithms for circuits is non-trivial in the \(\textsf{MPLWE}\) setting, homomorphic weighted addition can be realized. As a result, our \(\textsf{IPE}\) scheme reduces not only the master public key size but also the secret key size. In particular, it has a smaller secret key size than existing \(\textsf{LWE}\) -based schemes.