Name
Abstract | ||
|---|---|---|
Suppose we are given a proof of knowledge P in which a prover demonstrates that he knows a solution to a given problem instance. Suppose also that we have a secret sharing scheme S on n participants. Then under certain assumptions on P and S, we show how to transform P into a witness indistinguishable protocol, in which the prover demonstrates knowledge of the solution to some subset of n problem instances out of a collection of subsets denned by S. For example, using a threshold scheme, the prover can show that he knows at least d out of n solutions without revealing which d instances are involved. If the instances axe independently generated, we get a witness hiding protocol, even if P did not have this property. Our results can be used to efficiently implement general forms of group oriented identification and signatures. Our transformation produces a protocol with the same number of rounds as P and communication complexity n times that of P. Our results use no unproven complexity assumptions. |
Year | Venue | Keywords |
|---|---|---|
1994 | International Crytology Conference | communication complexity,one way function,secret sharing,proof of knowledge |
DocType | ISBN | Citations |
Conference | 3-540-58333-5 | 538 |
PageRank | References | Authors |
36.87 | 11 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ronald Cramer | 1 | 2499 | 178.28 |
| Ivan Damgård | 2 | 5851 | 431.52 |
| Berry Schoenmakers | 3 | 1550 | 119.18 |