Paper 2026/044

Jindo: Practical Lattice-Based Polynomial Commitments for Client-Side Proving

Abstract

We present $\textsf{Jindo}$, a new lattice-based polynomial commitment scheme (PCS) optimized for client-side proving, which requires fast prover performance while supporting evaluation hiding and flexible parameter regimes. To achieve this, we build $\textsf{Jindo}$ on the previous lattice-based PCSs $\textsf{CELPC}$ (CRYPTO'24) and $\textsf{Greyhound}$ (CRYPTO'24), which exhibit fast proving performance but have several limitations for client-side proving. We resolve these limitations by developing a new polynomial evaluation protocol that supports multilinear polynomials, diverse field choices, sublinear masking overhead for evaluation hiding, and cube-root verification and communication complexity. Our implementation shows that $\textsf{Jindo}$ improves upon $\textsf{CELPC}$ by about an order of magnitude across all metrics, including proof generation, verification, and proof size. Compared with the recent evaluation hiding code-based PCS $\textsf{PIP-FRI}$ (USENIX'26), $\textsf{Jindo}$ provides an order of magnitude faster proof generation while yielding similar verification and communication costs. Furthermore, when compiling the PIOP of $\textsf{Buckler}$ (CCS'25) to prove the validity of an RLWE sample, $\textsf{Jindo}$ outperforms $\textsf{CELPC}$ by an order of magnitude across all metrics. Compared with $\textsf{Lazer}$ (CCS'24) for proving the same lattice relation, $\textsf{Jindo}$ achieves an order of magnitude faster proof generation and two orders of magnitude faster verification.