Efficient inner product arguments and their applications in range proofs

Abstract

Abstract Inner product arguments allow a prover to prove that the inner product of two committed vectors equals a public scalar. They are used to reduce the complexity of many cryptographic primitives, such as range proofs. Range proofs are deployed in numerous applications to prove that a committed value lies in a certain range. As core building blocks, their complexity largely determines the performance of corresponding applications. In this paper, we have optimised the inner product argument with statement including two vector commitments (IPAtvc) and range proof of Daza et al. (PKC’20), the inner product argument with statement including only one vector commitment (IPAovc) of Bünz et al. (S&P′18). For IPAtvc, we reduce the concrete communication complexity by 2 log2n field elements, where n is the vector dimension. For range proofs, we reduce the concrete communication and prover complexities by about 2 log2m field elements and 11m field multiplications, respectively, where m is the bit length of range. For IPAovc, we exponentially reduce the asymptotic verifier complexity from linear to logarithmic. Due to the asymptotic characteristics, our protocols are highly competitive when the vector dimension or bit length of range is large.

Keywords

• communication complexity
• computational complexity
• cryptographic protocols
• cryptography