Zero-Knowledge Sets

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 /spl isin/ S or x /spl 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 verified by any one against the public random string. Our scheme is very efficient; no reasonable prior way to achieve our desiderata existed. Our new primitive immediately extends to providing zero-knowledge databases.

Authors

• Silvio Micali
• Michael O. Rabin
• Joe Kilian

Keywords

• Laboratories
• Upper bound
• Security
• Polynomials
• Mathematics
• Computer science
• National electric code
• Modular construction
• Finite Set
• Random String
• Siblings
• Cardinality
• Loss Of Generality
• Efficient Algorithm
• Hash Function
• Secret Key
• Binary String
• Probability Space
• Public Key
• Number Theory
• Security Parameter
• Turing Machine
• Left Child
• Verification Phase
• Random Oracle
• Bottom-up Fashion
• Discrete Logarithm
• Probabilistic Polynomial Time
• Merkle Tree
• Zero-knowledge Proof
• Subtree
• Random Element
• Binary Tree