Paper 2007/349

Statistically Hiding Sets

Manoj Prabhakaran and Rui Xue

Abstract

Zero-knowledge set is a primitive introduced by Micali, Rabin, and Kilian (FOCS 2003) which 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, 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.

Note: updated discussion, references

Metadata
Available format(s)
PDF PS
Category
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Keywords
Statistically Hiding SetZero-Knowledge SetTrapdoor DDH groupStatistical Zero-KnowledgeAccumulatorKnowledge-of-Exponent Assumption
Contact author(s)
mmp @ cs uiuc edu
History
2008-10-20: last of 2 revisions
2007-09-06: received
See all versions
Short URL
https://ia.cr/2007/349
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2007/349,
      author = {Manoj Prabhakaran and Rui Xue},
      title = {Statistically Hiding Sets},
      howpublished = {Cryptology {ePrint} Archive, Paper 2007/349},
      year = {2007},
      url = {https://eprint.iacr.org/2007/349}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.