|
Published Articles >> Table of Contents >> Abstract
44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03)
p. 80
Zero-Knowledge Sets
Silvio Micali, Massachusetts Institute Technology
Michael Rabin, Harvard University
Joe Kilian, NEC Laboratories
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SFCS.2003.1238183
Send link to a friend
| Abstract |
|
We show how a polynomial-time prover can commit to an arbitrary finite set S of strings so that, later on, he can, for any string x, reveal with a proof whether x \in S or x \notin S, without revealing any knowledge beyond the verity of these membership assertions. Our method is non interactive. Given a public random string, the prover commits to a set by simply posting a short and easily computable message. After that, each time it wants to prove whether a given element is in the set, it simply posts another short and easily computable proof, whose correctness can be veri.ed by any one against the public random string. Our scheme is very ef.cient; no reasonable prior way to achieve our desiderata existed. Our new primitive immediately extends to providing zero-knowledge "databases."
|
 Additional Information
|
Citation:
Silvio Micali, Michael Rabin, Joe Kilian,
"Zero-Knowledge Sets,"
focs,
p. 80,
44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03),
2003
|
|
