Skip to main content

1994 | OriginalPaper | Buchkapitel

Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols

verfasst von : Ronald Cramer, Ivan Damgård, Berry Schoenmakers

Erschienen in: Advances in Cryptology — CRYPTO ’94

Verlag: Springer Berlin Heidelberg

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Suppose we are given a proof of knowledge $$ \mathcal{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 $$ \mathcal{S} $$ on n participants. Then under certain assumptions on $$ \mathcal{P} $$ and $$ \mathcal{S} $$, we show how to transform $$ \mathcal{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 defined by $$ \mathcal{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 are independently generated, we get a witness hiding protocol, even if $$ \mathcal{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 $$ \mathcal{P} $$ and communication complexity n times that of $$ \mathcal{P} $$. Our results use no unproven complexity assumptions.

Metadaten
Titel
Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols
verfasst von
Ronald Cramer
Ivan Damgård
Berry Schoenmakers
Copyright-Jahr
1994
Verlag
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/3-540-48658-5_19