Summary: 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. The results can be used to efficiently implement general forms of group oriented identification and signatures. The transformation produces a protocol with the same number of rounds as \(\mathcal P\) and communication complexity \(n\) times that of \(\mathcal P\). The results use no unproven complexity assumptions.
For the entire collection see [Zbl 0856.00052].