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.