Abstract | ||
---|---|---|
Abstract. We define interactive and non-interactive statistical zero-knowledge proofs with (limited) help, as proofs that can be almost
perfectly simulated, where the prover and the verifier share a reference string that is computed by a probabilistic polynomial-time
trusted third party that receives as input the statement to be proven (i.e. the input to the protocol). We compare these models
with the standard interactive and non-interactive SZK models, trying to understand when this form of help can replace the
interaction between the prover and the verifier and vice versa. We show that every promise problem that has an SZK protocol
with help also has one without help. As for the opposite, we show non-interactive SZK proofs with help for natural languages
for which only interactive SZK proofs are known. In order to achieve that, we introduce a complete problem for the class of
promise problems that have non-interactive SZK proofs with help.
|
Year | DOI | Venue |
---|---|---|
2003 | 10.1007/s00145-002-0113-0 | J. Cryptology |
Keywords | Field | DocType |
non-interactive zero-knowledge,graph isomorphism.,zero-knowledge,zero knowledge,natural language,polynomial time,graph isomorphism,trusted third party | Discrete mathematics,Trusted third party,Promise problem,Graph isomorphism,Computer science,Theoretical computer science,Mathematical proof,Natural language,Probabilistic logic,Gas meter prover,Zero-knowledge proof | Journal |
Volume | Issue | ISSN |
16 | 2 | 0933-2790 |
Citations | PageRank | References |
7 | 0.47 | 6 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Michael Ben-Or | 1 | 2008 | 420.97 |
Danny Gutfreund | 2 | 11 | 0.89 |