Abstract:

Despite the centrality of sets in Mathematics, no general
zero-knowledge treatment of sets existed to date. 

We fill this gap by showing that a polynomial-time Prover
can commit to an arbitrary set S and then, 
for any sequence of potential elements X prove "X is in S"
or "X is not in S", whichever the case may be, 
without revealing any more than implied by these mere assertions. 

Our implementation, based on the discrete logarithm problem,
is non-interactive and extremely efficient.

Joint Work with Michael Rabin and Joe Kilian