Abstract | ||
---|---|---|
We present two efficient identification schemes based on the difficulty of solving the subset sum problem and the circuit satisfiability problem. Both schemes use the two prover model introduced by [BGKW], where the verifier (e.g the Bank) interacts with two untrusted provers (e.g two bank identification cards) who have jointly agreed on a strategy to convince the verifier of their identity. To believe the validity of their identity proving procedure, the verifier must make sure that the two provers can not communicate with each other during the course of the proof process. In addition to the simplicity and efficiency of the schemes, the resulting two prover interactive proofs can be shown to be perfect zero knowledge, making no intractability assumptions. |
Year | DOI | Venue |
---|---|---|
1989 | 10.1007/0-387-34805-0_44 | CRYPTO |
Keywords | Field | DocType |
intractability assumption,zero knowledge,prover interactive proof,prover model,untrusted provers,bank identification card,efficient identification,prover interactive proofs,circuit satisfiability problem,subset sum problem,proof process,efficient identification scheme,authentication,digital signatures,cryptography,electronic funds transfer,electronic signatures | Discrete mathematics,Subset sum problem,Authentication,Interactive proof system,Computer science,Cryptography,Circuit satisfiability problem,Theoretical computer science,Mathematical proof,Zero-knowledge proof,Gas meter prover | Conference |
ISBN | Citations | PageRank |
0-387-97317-6 | 8 | 1.66 |
References | Authors | |
9 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Michael Ben-Or | 1 | 2008 | 420.97 |
Shafi Goldwasser | 2 | 9935 | 2069.05 |
Joe Kilian | 3 | 707 | 88.92 |
Avi Wigderson | 4 | 8205 | 1064.31 |