Efficient Proofs that a Committed Number Lies in an Interval.

Fabrice Boudot

Abstract

Alice wants to prove that she is young enough to borrow money from her bank, without revealing her age. She therefore needs a tool for proving that a committed number lies in a specific interval. Up to now, such tools were either inefficient (too many bits to compute and to transmit) or inexact (i.e. proved membership to a much larger interval). This paper presents a new proof, which is both efficient and exact. Here, "efficient" means that there are less than 20 exponentiations to perform and less than 2 kbytes to transmit. The potential areas of application of this proof are numerous (electronic cash, group signatures, publicly verifiable secret encryption, etc...).