Volume pp Proofs of Partial Knowledge and Simplied Design of Witness Hiding Protocols

email ivandaimiaaudk Suppose we are given a proof of knowledge 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 S on n participants Then under certain assumptions on P and S we show how to transform P into a witness indistinguishable protocol in which the prover demonstrates knowledge of the solution to a subset of n problem instances corresponding to a quali ed set of participants 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 this can lead to witness hiding protocols even if P did not have this property Our transformation produces a protocol with the same number of rounds as P and communication complexity n times that of P Our results use no unproven complexity assumption