Paper 2026/1977

Lattice-based Secret-Key Functional Encryption for Constant-Degree Polynomials

Abstract

We present a lattice-based construction of secret-key functional encryption (FE) for low-norm polynomials of any constant degree $d$, hence also for $\mathsf{NC}^{0}$ circuits. We rely on two core ingredients: 1. New trapdoor and preimage sampling algorithms for certain degree-$d$ tensor-structured matrices, used to generate functional secret keys. 2. A new $k$-LWE-style assumption where short preimages of non-zero images with respect to the above tensor-structured matrix are given as hints, under which we prove that our secret-key FE scheme is selectively secure (under unbounded collusion). To gain confidence in the new assumption, we prove that the standard LWE assumption implies the degree-$1$ case and cryptanalyse the $d > 1$ case. As a corollary, we obtain a new pathway to post-quantum secure indistinguishability obfuscation (iO), conditioned on the above new assumption, standard LWE, and the existence of polynomial-stretch pseudorandom generators in $\mathsf{NC}^{0}$. Along the way, we give a new, simple (public-key) FE scheme for linear functions with selective security under the standard LWE assumption.