Efficient Protocols for Set Membership and Range Proofs

We consider the following problem: Given a commitment to
a value σ, prove in zero-knowledge that σ belongs to some discrete set
Φ. The set Φ can perhaps be a list of cities or clubs; often Φ can be a
numerical range such as [1, 220 ]. This problem arises in e-cash systems,
anonymous credential systems, and various other practical uses of zero-
knowledge protocols.

When using commitment schemes relying on RSA-like assumptions, there
are solutions to this problem which require only a constant number
of RSA-group elements to be exchanged between the prover and verifier
[Bou00,Lip03,Gro05]. However, for many commitment schemes based
on bilinear group assumptions, these techniques do not work, and the
best known protocols require O(k) group elements to be exchanged.
In this paper, we present two new approaches to building set-membership
proofs. The first is based on bilinear group assumptions. When ap-
plied to the case where Φ is a range of integers, our protocols require
O( k / log k - log log k ) group elements to be exchanged. Not only is this result
asymptotically better, but the constants are small enough to provide
significant improvements even for small ranges. Indeed, in a pure discrete
logarithm based setting, our new protocol is by an order of magnitude
more efficient than previously known ones. We also discuss alternative
implementations of our membership proof based on the strong RSA
assumption. Depending on the application, e.g., when Φ is a published set
of values such a frequent flyer clubs, cities, or other adhoc collections,
these alternative also outperform prior solutions.