CryptoDB
Greyhound: Fast Polynomial Commitments from Lattices
| Authors: |
|
|---|---|
| Download: |
|
| Conference: | CRYPTO 2024 |
| 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 three-round 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 Greyhound, 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 53KB, which is more than 10^4 times smaller than the recent lattice-based framework, called SLAP (EUROCRYPT 2024), and around three orders of magnitude smaller than Ligero (CCS 2017) and Brakedown (CRYPTO 2023). |
BibTeX
@inproceedings{crypto-2024-34387,
title={Greyhound: Fast Polynomial Commitments from Lattices},
publisher={Springer-Verlag},
doi={10.1007/978-3-031-68403-6_8},
author={Ngoc Khanh Nguyen and Gregor Seiler},
year=2024
}