Paper 2024/616

$\mathsf{Cougar}$: Cubic Root Verifier Inner Product Argument under Discrete Logarithm Assumption

Abstract

An inner product argument (IPA) is a cryptographic primitive used to construct a zero-knowledge proof system, which is a notable privacy-enhancing technology. We propose a novel efficient IPA called $\mathsf{Cougar}$. $\mathsf{Cougar}$ features cubic root verifier and logarithmic communication under the discrete logarithm (DL) assumption. At Asiacrypt2022, Kim et al. proposed two square root verifier IPAs under the DL assumption. Our main objective is to overcome the limitation of square root complexity in the DL setting. To achieve this, we combine two distinct square root IPAs from Kim et al.: one with pairing ($\mathsf{Protocol3}$; one was later named $\mathsf{Leopard}$) and one without pairing ($\mathsf{Protocol4}$). To construct $\mathsf{Cougar}$, we first revisit $\mathsf{Protocol4}$ and reconstruct it to make it compatible with the proof system for the homomorphic commitment scheme. Next, we utilize $\mathsf{Protocol3}$ as the proof system for the reconstructed $\mathsf{Protocol4}$. Finally, to facilitate proving the relation between elliptic curve points appearing in $\mathsf{Protocol4}$, we introduce a novel $\mathsf{Plonkish}$-based proof system equipped with custom gates for mixed elliptic curve addition. We show that $\mathsf{Cougar}$ indeed satisfies all the claimed features, along with providing a soundness proof under the DL assumption. In addition, we implemented $\mathsf{Cougar}$ in Rust, demonstrating that the verification time of $\mathsf{Cougar}$ increases much slowly as the length of the witness $N$ grows, compared to other IPAs under the DL assumption and transparatent setup: BulletProofs and $\mathsf{Leopard}$. Concretely, $\mathsf{Cougar}$ takes 0.346s for verification in our setting when $N = 2^{20}$, which is a $50\times$ speed-up from BulletProofs.

Note: Revise Abstract, Add constraint systems and implementation results