Paper 2024/281

Polynomial Commitments from Lattices: Post-Quantum Security, Fast Verification and Transparent Setup

Valerio Cini, NTT Research
Giulio Malavolta, Bocconi University and MPI Security and Privacy
Ngoc Khanh Nguyen, King's College London
Hoeteck Wee, NTT Research

Polynomial commitment scheme allows a prover to commit to a polynomial $f \in \mathcal{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 \in\mathcal{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^{20}$ our scheme yields proofs of size $2$X smaller than the hash-based \textsf{FRI} commitment (Block et al., Asiacrypt 2023), and $70$X smaller than the very recent lattice-based construction by Albrecht et al. (Eurocrypt 2024).

Available format(s)
Cryptographic protocols
Publication info
polynomial commitmentLattice-Based Cryptography
Contact author(s)
cini valerio @ gmail com
giulio malavolta @ hotmail it
ngoc_khanh nguyen @ kcl ac uk
wee @ di ens fr
2024-02-23: approved
2024-02-19: received
See all versions
Short URL
Creative Commons Attribution


      author = {Valerio Cini and Giulio Malavolta and Ngoc Khanh Nguyen and Hoeteck Wee},
      title = {Polynomial Commitments from Lattices: Post-Quantum Security, Fast Verification and Transparent Setup},
      howpublished = {Cryptology ePrint Archive, Paper 2024/281},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.