Zero-knowledge proofs of knowledge are now used in many applications and permit to prove the knowledge of secrets with many (complex) properties. Among them, the proof that a secret lies in a given interval is very useful in the context of electronic voting, e-cash or for anonymous credentials. There currently exists several techniques to prove that one secret belongs to an interval [a, b] and it appears difficult to know exactly which method should be used in one particular situation. In practice, this might be critical if the proof is computed by e.g. a constraint device such as a smart card or a mobile phone.

In this paper, we give new contributions to the practical use of these so-called range proofs. We first provide several improvements to the solution of Lipmaa, Asokan and Niemi which is based on the multi-base decomposition of the secret. We also introduce a variant of the signature-based method due to Camenisch, Chaabouni and Shelat, which does not ask the prover to compute pairings. We finally make the first complete comparison between all existing range proofs. This underlines that our methods are useful in many practical cases. This also permits any designer of a new service to exactly know which method he should use, depending on the values a and b.

This is a joint work with Iwen Coisel, Amandine Jambert and Jacques Traoré.