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
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.