## Interval Proofs Revisited

### Berry Schoenmakers (Technical University of Eindhoven)

There are two competing approaches to prove in (honest-verifier)
zero-knowledge that a committed (or encrypted) integer belongs to a given interval.
One approach, which is usually only considered for interval-lengths being
an integral power of 2, works best for small intervals--the extreme case
being an interval of length 2 solved by an OR proof.
The other approach, initiated by Boudot, works best for larger intervals.
In the context of voting schemes, it will be argued that small interval
proofs occur 'naturally' and also that there is a need for interval-lengths
which are not an integral power of 2. Interval proofs for arbitrary lengths
will be treated and solved efficiently.

The results for small interval will then be compared to techniques for large
intervals, focusing on performance of the various techniques (there are also
differences w.r.t. the particular intractability assumptions needed). An estimate
will be given of the break-even point for these two approaches.