Greyhound: Fast Polynomial Commitments from Lattices

Abstract

In this paper, we propose Greyhound, the first concretely efficient polynomial commitment scheme from standard lattice assumptions. At the core of our construction lies a simple sigma protocol for proving evaluations for polynomials of bounded degree N with verifier time complexity $O(\sqrt{N})$. By composing it with the LaBRADOR proof system (CRYPTO 2023), we obtain a succinct proof of polynomial evaluation (i.e. polylogarithmic in N) that admits a sublinear verifier runtime. To highlight practicality of Geyhound, we provide implementation details including concrete sizes and runtimes. Notably, for large polynomials of degree at most $N=2^{30}$, the scheme produces evaluation proofs of size 93KB, which is 8000X smaller than the recent lattice-based construction by Albrecht et al. (EUROCRYPT 2024), and three orders of magnitude smaller than Ligero (CCS 2017) and Brakedown (CRYPTO 2023).