Experimenting With Non-Interactive Range Proofs Based on the Strong RSA Assumption

Abstract

Range proofs are proofs that a committed number m belongs to a range [a, b] for public constants a, b, without leaking any information about the value m. In this work, we evaluate and analyze the performance of existing techniques for range proofs based on the strong RSA assumption while varying the range sizes. We first group the techniques into two classes. Our experiments show that the first class, being built on finding sums of squares (e.g., Groth's range proof), has sharply decreasing performance trends as the range size increases. Thus, solutions in this class seem to be useful primarily for small ranges. The second class, which relies on a direct proof (e.g., Boudot's range proof), exposes that the performance degradation slopes are not as steep as the range size grows, compared to solutions in the first group. However, this class's main drawback is that these methods require considerably more modular arithmetic than the first class. Concretely, the Groth and Boudot protocols achieve the best performance when the range sizes are less than and greater than 1410 bits, respectively. As part of this work, we consider an extension by combining the strong points of existing solutions and examine the result efficiency. Interestingly, however, our experimental results report that this extension outperforms either Groth's or Boudot's protocol for certain ranges, but there is no range for which the extension outperforms both.

Keywords

• Non-interactive zero-knowledge proof
• range proof
• strong RSA assumption