Efficient Proofs that a Committed Number Lies in an Interval

By Fabrice Boudot. International Conference on the Theory and Application of Cryptographic Techniques, 2000

547 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/2a531c6f67c2dc3be1fcfe5a536d71de8851c5cc

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Computer Vision and Pattern Recognition

Citations in the corpus

Direct anonymous attestation (2004, background): “, is not provided the order of the group) this proof can be done efficiently [4] (it compares to about six ordinary PK{(α) : y = g}.”
Privacy-preserving smart metering (2011, methodology): “We use several existing results to prove statements about discrete logarithms: proof of knowledge of a discrete logarithm [35]; proof of knowledge of the equality of some element in different representations [10]; proof with interval checks [33], range proof [5] and proof of the disjunction or conju”
Fast Secure Multiparty ECDSA with Practical Distributed Key Generation and Applications to Cryptocurrency Custody (2018, background): “Then, for multiplication, each party proves the range proof of [2] (with necessary adaptations described in the full version of this paper), which requires sending 12 Paillier ciphertexts and 6 elements of ZN .”
Compact E-Cash (2005, methodology): “In the common parameters model, we use several previously known results for proving statements about discrete logarithms, such as (1) proof of knowledge of a discrete logarithm modulo a prime [39] or a composite [33, 29], (2) proof of knowledge of equality of representation modulo two (possibly diff”
Additive Combinatorics and Discrete Logarithm Based Range Protocols (2010, background): “As discussed in the introduction, some efficient range proofs were proposed in [4, 16, 15, 5].”
Efficient RSA Key Generation and Threshold Paillier in the Two-Party Setting (2012, background): “An alternative solution is to take a detour around integer commitments; this allows a solution requiring only O(1) exponentiations [7,24,49].”
Provisions: Privacy-preserving Proofs of Solvency for Bitcoin Exchanges (2015, methodology): “The protocol of [6] can be made to work without a trusted setup, but the resulting protocol is considerably less efficient.”
Differentially private data aggregation with optimal utility (2014, methodology): “For the second property, we introduce zero-knowledge (ZK) proofs such that a party can prove that a correct secret value is shared among the parties [27] and that shared secret values satisfy some mathematical conditions (e.g., they are in a pre-deﬁned range) [12].”
On Diophantine Complexity and Statistical Zero-Knowledge Arguments (2003, methodology): “This argument is conceptually much simpler than Boudot’s protocol for the same problem [Bou00], somewhat shorter, and offers perfect completeness.”
How to win the clonewars: efficient periodic n-times anonymous authentication (2006, methodology): “The proof in Step 4 is done as follows: U J r 1 g h , C s = g h , and sends them to . interval [0 , n − 1] using standard techniques [22, 19, 8].”
Anonymous Identification in Ad Hoc Groups (2004, background): “the tightness of the integer ranges can be increased by employing the range proofs of [10], nevertheless the tightness achieved above is sufficient for our purposes, and incurs a lower overhead.”
Privacy and accountability for location-based aggregate statistics (2011, methodology): “Such proof is done using the efficient interval zero-knowledge proof of [5]; the server makes such interval publicly available for each aggregate.”
A Statistically-Hiding Integer Commitment Scheme Based on Groups with Hidden Order (2002, methodology): “– Although related works such as [8, 3, 10, 4 ] do not suffer from the main problem we solve here, the reason for this is that they use “commitments” with a single base (i.e., of form c = gs mod n). Such commitments, however, cannot satisfy the standard hiding property for commitments, and hence pr”