University of Tartu - ©2011 Rafik Chaabouni - Last update: 05.10.2011 17:53
Date: 05/10/2011 Location: J. Liivi 2, room 317 (next to the coffee room)
Speaker: Rafik Chaabouni
Title: Set Membership and Range Proofs (Part 1)
Abstract:
Set membership is when we consider (zero-knowledge) protocols which allow a prover to convince a verifier that a digitally committed value is a member of a given public set. A special case of this problem, called range proofs, is when we want to show that the committed value lies in a specified integer range.
Set membership proofs occur for instance in the context of anonymous credentials. Let us take a user who is issued a credential containing a number of attributes such as the nationality. Furthermore assume the user needs to prove that she is from a European country. Thus, we are given the list of European countries and the user has to show that she possesses a credential containing one of those country as nationality (without of course, leaking the specific country the user comes from).
As for range proofs, they often occur in anonymous credential too and e-cash scenarios. For example, a user with passport credential might wish to prove that her age is within some range, e.g. greater than 18, or say between 13 and 18 in the case of a teen-community website. This problem is a special case of the set membership proof. Since the elements of the set occur in consecutive order, special techniques can be applied to improve on set membership proofs.