Valerio Cini
NTT Research, Inc.

Giulio Malavolta
Bocconi University and MPI Security and Privacy

Ngoc Khanh Nguyen
King's College London

Hoeteck Wee
NTT Research, Inc.

Keywords: Polynomial Commitment, Lattice-Based Cryptography

Abstract

Polynomial commitment scheme allows a prover to commit to a polynomial f ∈ R[X] of degree L, and later prove that the committed function was correctly evaluated at a specified point x; in other words f(x) = u for public x, u ∈ R. Most applications of polynomial commitments, e.g. succinct non-interactive arguments of knowledge (SNARKs), require that (i) both the commitment and evaluation proof are succinct (i.e., polylogarithmic in the degree L) - with the latter being efficiently verifiable, and (ii) no pre-processing step is allowed.

Surprisingly, as far as plausibly quantum-safe polynomial commitments are concerned, the currently most efficient constructions only rely on weak cryptographic assumptions, such as security of hash functions. Indeed, despite making use of the underlying algebraic structure, prior lattice-based polynomial commitments still seem to be much behind the hash-based ones. Moreover, security of the aforementioned lattice constructions against quantum adversaries was never formally discussed.

In this work, we bridge the gap and propose the first (asymptotically and concretely) efficient lattice-based polynomial commitment with transparent setup and post-quantum security. Our interactive variant relies on the standard (Module-)SIS problem, and can be made non-interactive in the random oracle model using Fiat-Shamir transformation. In addition, we equip the scheme with a knowledge soundness proof against quantum adversaries which can be of independent interest. In terms of concrete efficiency, for L = 2²⁰ our scheme yields proofs of size 2x smaller than the hash-based FRI commitment (Block et al., Asiacrypt 2023), and 70x smaller than the very recent lattice-based construction by Albrecht et al. (Eurocrypt 2024).