Paper 2025/1522

Constant-Size Inner Product Arguments for Group-Scalar Relations, Dynamic Threshold VRFs, and More

Abstract

Abstract. Linear algebraic relations, such as inner products ⟨a, b⟩, underlie a wide range of cryp- tographic constructions, including zero-knowledge proofs, SNARKs, polynomial commitment schemes, and more. In this work, we consider group-scalar relations, i.e., statements of the form ⟨A, b⟩, where A is a vector of group elements and b is a vector of field elements. In many crypto- graphic settings, it is necessary to prove relationships between group elements like public keys, or other cryptographic objects without access to the underlying discrete logarithms. Our results are as follows: – At the protocol level, we introduce the first Inner Product Argument (IPA) that specifically fo- cuses on group-scalar relations in bilinear groups. It achieves constant-size proofs and constant- time verification, maintaining commitments and arguments entirely in the source group. Our techniques enable new applications and significantly improve efficiency compared to state-of- the-art IPAs such as Dory (TCC ’21) and GIPA (Asiacrypt ’21), which rely on recursive folding techniques and thus have logarithmic proofs and verification time. We prove security in the Algebraic Group Model under the q-DHE and q-DL assumptions. – At the primitive level, we present a new class of functional commitments for linear functions over group-scalar elements. It enables even more applications such as polynomial commit- ments for values hidden inside group exponentiations. – To showcase our contributions, we demonstrate new applications—most notably, we introduce the notion of dynamic threshold verifiable random functions, which we believe to be a valuable tool for distributed randomness generation. We further present dynamic threshold signatures without random oracles, polynomial commitments over group-encoded inputs, and their ap- plications to oblivious proofs. Our results provide modular and efficient tools to build cryptographic protocols without typical SNARK frameworks, simplifying real-world deployments. To demonstrate the practicality of our contributions, we provide an implementation and related benchmarks.