[Resource Topic] 2023/203: A Different Base Approach for Better Efficiency on Range Proofs

Welcome to the resource topic for 2023/203

Title:
A Different Base Approach for Better Efficiency on Range Proofs

Authors: Esra Günsay, Cansu Betin Onur, Murat Cenk

Abstract:

Zero-knowledge range proofs (ZKRPs) are commonly used to prove the validation of a secret integer lies in an interval to some other party in a secret way. In many ZKRPs, the secret is represented in binary and then committed via a suitable commitment scheme or represented as an appropriate encryption scheme. This paper is an extended version of the conference paper presented in 14th IEEE International Conference on Security of Information and Networks. To this end, we first analyze the proof proposed by Mao in 1998 in both discrete logarithm-setting and elliptic-curve settings. Mao’s proof contains a bit commitment scheme with an OR construction as a sub-protocol. We have extended Mao’s range proof to base-u with a modified OR-proof. We investigate and compare the efficiency of different base approaches on Mao’s range proof. Later, we analyze the range poof proposed by Bootle et al. in both finite fields and elliptic-curve settings. This proof contains polynomial commitment with matrix row operations. We take the number of computations in modulo exponentiation and the cost of the number of exchanged integers between parties. Then, we generalize these costs for u-based construction. We show that compared with the base-2 representation, different base approach provides efficiency in communication cost or computation cost, or both.

ePrint: https://eprint.iacr.org/2023/203

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .