Paper 2026/156

Hachi: Efficient Lattice-Based Multilinear Polynomial Commitments over Extension Fields

Abstract

In this work, we present Hachi, a concretely efficient multilinear polynomial commitment scheme that offers succinct proof sizes of $\mathrm{poly}(\ell,\lambda)$ and achieves a “square-root” verifier time complexity of $\tilde{O}(\sqrt{2^\ell \lambda})$ for $\ell$-variate polynomials under the Module-SIS assumption. Compared to the current state-of-the-art scheme, Greyhound (CRYPTO~2024), Hachi provides an asymptotic improvement of $\tilde{O}(\lambda)$ in verification time, which translates into a practical 12.5-fold speedup, while maintaining compact proofs of approximately $55$ KB. To improve the verification time, we adopt the sumcheck protocol. Note that the standard sumcheck has efficiency bottlenecks for lattice-based constructions, since lattice operations are usually performed over power-of-two cyclotomic rings $\mathbf{R}_{q} := \mathbb{Z}_q[X]/(X^d + 1)$. To address this challenge, we provide a novel approach that integrates Greyhound with the ring-switching idea proposed by Huang, Mao and Zhang (ePrint 2025). Surprisingly, under this approach, the verifier does not need to perform any multiplication over $\mathbf{R}_{q}$, enabling a much faster verification time. This technique could be of independent interest for building lattice-based SNARKs, particularly for achieving faster verification. As a separate contribution, we introduce a generic reduction that converts polynomial evaluation proofs over extension fields $\mathbb{F}_{q^k}$ (under suitable parameter regimes) into equivalent statements over cyclotomic rings $\mathbf{R}_{q}$. This reduction is compatible with existing lattice-based polynomial commitment schemes and can be integrated as a modular enhancement to broaden applicability to statements over extension fields.