Abstract:

Lattice-based polynomial commitment schemes (PCSs) promise post-quantum succinct arguments (SNARKs) with two properties that hash-based schemes, today’s deployed post-quantum default, do not provide: concretely small proofs and efficient commitments to sparse or low-norm polynomials. The second property is essential to Twist and Shout (CRYPTO 2026), a core component of the Jolt zero-knowledge virtual machine (zkVM): their prover commits to enormous polynomials that are almost entirely zero. Yet despite a wave of recent work, existing lattice-based PCSs achieve at most two of the three properties that deployment demands: small proof size, fast verification, and soundness from standard assumptions such as Module-SIS.

We present Akita, a lattice-based PCS that achieves all three. We improve on the square-root-time verifier of Hachi (ePrint 2026), our direct predecessor, through a new setup offloading technique: the public setup matrices are committed ahead of time, and the verifier’s work in processing them is deferred and proved against these commitments. For a polynomial with N coefficient and any constant K >= 2, this reduces verification time to O(N^{1/K}) while preserving O(log N) proof size, O(N) prover time, and security from standard Module-SIS. Akita consists of a number of folding steps, which we heavily optimize using a suite of techniques. This includes an optimized digit range check, relation-specific ring dimensions and subring challenges, complementary methods for embedding field evaluations and checking ring relations, commitments compressed to 128 bytes each, and exact Euclidean norm checks for tighter Module-SIS parameters.

We implement Akita in Rust and benchmark it against existing lattice-based and hash-based PCSs. Across these benchmarks, Akita produces proofs of only 61-70 KB, matching Greyhound’s, the prior record holder, when both schemes are calibrated to the same lattice security target, while verifying 20x to 90x faster. Akita’s prover uses the least memory: beyond storing the polynomial itself, its memory overhead grows sublinearly in the polynomial size. We also integrate Akita into Jolt. For every program size we evaluate, Jolt-with-Akita achieves a 1.3x to 2.2x prover speedup and 2.2x to 7.4x verifier speedup over Jolt-with-Dory, while producing comparable proof sizes, with every proof below 100 KB.

This is joint work with Omid Bodaghi, Giuseppe Vitto, Amirhossein Khajehpour, Taghi Badakhshan, Andrii Baranov, and Ari Biswas (LayerZero), Freya Liu (CMU), Jiapeng Zhang (USC), Markos Georghiades, and Justin Thaler (a16z crypto).