We present a new primitive called {\em Statistically Hiding Sets} (SHS), similar to zero-knowledge sets, but providing an information theoretic hiding guarantee, rather than one based on efficient simulation. 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 that has been used for {\em all} zero-knowledge set constructions so far. This not only provides efficiency gains compared to the best schemes in that paradigm, but also lets us provide {\em statistical} hiding; previous approaches required the prover to maintain growing amounts of state with each new proof for this.
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. We prove this assumption in the generic group model.
Category / Keywords: cryptographic protocols / Statistically Hiding Set, Zero-Knowledge Set, Trapdoor DDH group, Statistical Zero-Knowledge, Accumulator, Knowledge-of-Exponent Assumption Date: received 5 Sep 2007, last revised 20 Oct 2008 Contact author: mmp at cs uiuc edu Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Note: updated discussion, references Version: 20081020:144744 (All versions of this report) Discussion forum: Show discussion | Start new discussion