1994 | OriginalPaper | Chapter
Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols
Authors : Ronald Cramer, Ivan Damgård, Berry Schoenmakers
Published in: Advances in Cryptology — CRYPTO ’94
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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.