CryptoDB
Statistically Hiding Sets
Authors: | |
---|---|
Download: | |
Abstract: | Abstract: Zero-knowledge set, a primitive introduced by Micali, Rabin, and Kilian (FOCS 2003), enables a prover to commit a set to a verifier, without revealing even the size of the set. Later the prover can give zero-knowledge proofs to convince the verifier of membership/non-membership of elements in/not in the committed set. We present a new primitive called {\em Statistically Hiding Sets} (SHS), similar to zero-knowledge sets, but providing an information theoretic hiding guarantee. This is comparable to relaxing zero-knowledge proofs to {\em witness independent proofs}. More precisely, we continue to use the simulation paradigm for our definition, but do not require the simulator (nor the distinguisher) to be efficient. We present a new scheme for statistically hiding sets, which does not fit into the ``Merkle-tree/mercurial-commitment'' paradigm used for {\em all} zero-knowledge set constructions so far. This not only provides some efficiency gains compared to the best possible schemes in that paradigm, but also lets us provide {\em statistical} hiding, without the prover having to maintain growing amounts of state with each new proof; this is not known to be possible with the previous approach. Our construction is based on an algebraic tool called {\em trapdoor DDH groups} (TDG), introduced recently by Dent and Galbraith (ANTS 2006). Ours is perhaps the first non-trivial application of this tool. However the specific hardness assumptions we associate with TDG are different, and of a strong nature --- strong RSA and a knowledge-of-exponent assumption. Our new knowledge-of-exponent assumption may be of independent interest. |
BibTeX
@misc{eprint-2007-13629, title={Statistically Hiding Sets}, booktitle={IACR Eprint archive}, keywords={cryptographic protocols / Statistically Hiding Set, Zero-Knowledge Set, Trapdoor DDH group, Statistical Zero-Knowledge, Accumulator, Knowledge-of-Exponent Assumption}, url={http://eprint.iacr.org/2007/349}, note={ mmp@cs.uiuc.edu 13765 received 5 Sep 2007, last revised 9 Sep 2007}, author={Manoj Prabhakaran and Rui Xue}, year=2007 }