Paper 2021/046

Efficient Lattice-Based Inner-Product Functional Encryption

Jose Maria Bermudo Mera and Angshuman Karmakar and Tilen Marc and Azam Soleimanian

Abstract

In the recent years, many research lines on Functional Encryption (FE) have been suggested and studied regarding the functionality, security, or efficiency. These studies include quadratic FE, multi-client FE, function-hiding FE, dynamic FE and much more. Nevertheless, an open problem on a basic functionality, the single-input inner-product (IPFE), remains: can IPFE be instantiated based on the Ring Learning With Errors (RLWE) assumption? The RLWE assumption provides quantum-resistance security while in comparison with LWE assumption gives significant performance and compactness gains. In this paper we present the first IPFE scheme whose security is guaranteed relying on the RLWE assumption. The security proof requires developing two new results on ideal lattices. The first result is a variant of Ring-LWE, that we call multi-hint extended Ring-LWE, where some hints on the secret and the noise are given. We present a reduction from RLWE problem to this variant. The second tool is a special form of Leftover Hash Lemma (LHL) over rings, which we call Ring-LHL. To demonstrate the efficiency of our scheme we provide an optimized implementation of RLWE-based IPFE scheme and show its performance on a practical use case.