Cougar: Cubic Root Verifier Inner Product Argument Under Discrete Logarithm Assumption
Open Access
- 14 January 2026
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Access
- Vol. 14, 10217-10244
Abstract
An inner product argument (IPA) is a cryptographic proof system that serves as a fundamental building block for various applications, such as zero knowledge proofs and verifiable computation. Bulletproofs (IEEE S&P 2018), a well-known IPA under the discrete logarithm (DL) assumption, features a short, logarithmically-sized proof, making it suitable for blockchain applications. However, its major drawback is the linear verifier cost ( $O(N)$ ), which presents a significant bottleneck in settings like verifiable computation. To address this, recent advancements have successfully reduced the verification complexity to square-root order ( $O(\sqrt {N})$ ) under the same assumption (e.g., Asiacrypt 2022, IEEE TIFS). In this work, we propose $\textsf {Cougar}$ , a novel IPA that breaks this square-root barrier to achieve an unprecedented cubic-root verifier complexity ( $O(\sqrt [{3}]{N})$ ), while strictly maintaining the compact logarithmic proof size ( $O(\log N)$ ) characteristic of Bulletproofs. To achieve this, $\textsf {Cougar}$ introduces a generalized two-tier commitment framework combined with a disjoint interpolation strategy for efficient consistency checks. We implemented $\textsf {Cougar}$ in Rust and performed a comprehensive benchmarking against Bulletproofs and $\textsf {Leopard}$ (IEEE TIFS). Our evaluation demonstrates that while $\textsf {Cougar}$ incurs a moderate increase in prover overhead, its verification time scales significantly better for large instances. Concretely, for a witness size of $N = 2^{20}$ , $\textsf {Cougar}$ achieves a $50\times $ verification speed-up over Bulletproofs and exhibits a superior asymptotic growth rate compared to existing sublinear IPAs.Keywords
Funding Information
- Institute of Information and Communications Technology Planning and Evaluation
- Korean Government [Ministry of Science and ICT (MSIT)] (RS-2021-II210727 (90%))
- Culture, Sports and Tourism Research and Development Program through Korea Creative Content Agency
- Ministry of Culture, Sports and Tourism (RS-2024-00332210 (10%))
This publication has 52 references indexed in Scilit:
- Transparent SNARKs from DARK Compilers2020
- Fractal: Post-quantum and Transparent Recursive Proofs from Holography2020
- Concretely-Efficient Zero-Knowledge Arguments for Arithmetic Circuits and Their Application to Lattice-Based Cryptography2020
- Updateable Inner Product Argument with Logarithmic Verifier and Applications2020
- Scalable Zero Knowledge with No Trusted Setup2019
- Aurora: Transparent Succinct Arguments for R1CS2019
- Arya: Nearly Linear-Time Zero-Knowledge Proofs for Correct Program Execution2018
- Efficient Identification and Signatures for Smart Cards2001
- Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing2001
- How To Prove Yourself: Practical Solutions to Identification and Signature Problems2000