Welcome to the resource topic for 2025/1903
Title:
HyperWolf*: Lattice Polynomial Commitments with Standard Soundness
Authors: Lizhen Zhang, Shang Gao, Sherman S. M. Chow, Kurt Pan, Bin Xiao
Abstract:We present \mathsf{HyperWolf}^*, a lattice-based, fully transparent polynomial commitment scheme (PCS) for univariate and multilinear polynomials.
To the best of our knowledge, it is the first lattice PCS to simultaneously achieve logarithmic proof size and verification time with standard soundness under standard lattice assumptions over polynomial~rings.
Building on sublinear schemes such as \mathsf{Greyhound} (CRYPTO’24) and \mathsf{BrakeDown} (CRYPTO’23), we generalize the two-dimensional approach to a k-dimensional witness-folding recursion, yielding a k-round hyperdimensional proof.
Each round folds the witness along one axis, reducing the tensor arity by one, giving overall cost O(k N^{1/k}); choosing k = \log N yields O(\log N) verification time and proof size.
For standard \ell_2 soundness,
we give an exact Euclidean-norm proof tailored to lattice relations:
we prove \langle \vec{f}, \vec{f}\rangle \bmod q via an inner-product argument and enforce a small-coefficient bound on \|\vec{f}\|_\infty so that \langle \vec{f}, \vec{f}\rangle \bmod q = \langle \vec{f}, \vec{f}\rangle over \mathbb{Z}.
Both sub-proofs admit the same structure for O(\log N) complexity.
We further compact the proof using a proof-of-proof IPA `{a}~la LaBRADOR (CRYPTO’23), attaining O(\log\log\log{N}) while preserving logarithmic verification and linear proving.
We also describe a candidate optimization that achieves O(\log\log N) proofs without LaBRADOR.
For N = 2^{30}, \mathsf{HyperWolf} features a {\sim}53 KB proof size and, compared to \mathsf{Greyhound}, reduces verifier work from \Theta(\sqrt{N}) to \Theta(\log N), yielding 2 to 3 orders of magnitude improvement for large N while maintaining comparable size.
ePrint: https://eprint.iacr.org/2025/1903
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .