Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols.pdfVIP

Proofs of Partial Knowledge and Simpli edDesign of Witness Hiding ProtocolsRonald Cramer, CWIIvan Damgard, Aarhus University, DenmarkBerry Schoenmakers, CWIAbstract. Suppose we are given a proof of knowledge P in which aprover demonstrates that he knows a solution to a given problem in-stance. Suppose also that we have a secret sharing scheme S on n par-ticipants. Then under certain assumptions on P and S, we show howto transform P into a witness indistinguishable protocol, in which theprover demonstrates knowledge of the solution to some subset of n prob-lem instances out of a collection of subsets de ned by S. For example,using a threshold scheme, the prover can show that he knows at least dout of n solutions without revealing which d instances are involved. If theinstances are independently generated, we get a witness hiding protocol,even if P did not have this property. Our results can be used to ecientlyimplement general forms of group oriented identi cation and signatures.Our transformation produces a protocol with the same number of roundsas P and communication complexity n times that of P. Our results useno unproven complexity assumptions.1 IntroductionIn this work1, we assume that we are given an interactive proof where the proverP convinces the veri er V that P knows some secret. Typically, the secret is thepreimage under some one-way function of a publicly known piece of information.Thus the secret could be for example a discrete log or an RSA root. Such aproof is called a proof of knowledge [5], and can be used in practice to designidenti cation schemes or signature systems.We assume in the following that the proof of knowledge has a special formin that the veri er only sends uniformly chosen bits. This is also known as apublic coin protocol. For simplicity, we restrict ourselves to 3-round protocols,where the prover speaks rst (generalization of our results to any number ofrounds is possible). We also assume that the protocol is honest veri er zero-k