TY - GEN

T1 - Proofs of partial knowledge and simplified design of witness hiding protocols

AU - Cramer, R.

AU - Damgard, Ivan

AU - Schoenmakers, B.

PY - 1994

Y1 - 1994

N2 - 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 some subset of n problem instances out of a collection of subsets defined by 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 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 P and communication complexity n times that of P . Our results use no unproven complexity assumptions.

AB - 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 some subset of n problem instances out of a collection of subsets defined by 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 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 P and communication complexity n times that of P . Our results use no unproven complexity assumptions.

U2 - 10.1007/3-540-48658-5_19

DO - 10.1007/3-540-48658-5_19

M3 - Conference contribution

SN - 3-540-58333-5

T3 - Lecture Notes in Computer Science

SP - 174

EP - 187

BT - Advances in Cryptography - Eurocrypt'94 (Santa Barbara CA, USA, August 21-25, 1994)

A2 - Desmedt, Y.

PB - Springer

CY - Berlin

ER -