Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / Functional Encryption, Inner-Product, Lattice-Based Cryptography, Learning with Errors over Ring

Date: received 12 Jan 2021

Contact author: tilen marc at xlab si

Available format(s): PDF | BibTeX Citation

Version: 20210118:081124 (All versions of this report)

Short URL: ia.cr/2021/046


[ Cryptology ePrint archive ]