Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols

Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols

1994 | Ronald Cramer, CWI; Ivan Damgård, Aarhus University, Denmark; Berry Schoenmakers, CWI
This paper presents a method to transform a proof of knowledge (P) into a witness indistinguishable protocol, which allows a prover to demonstrate knowledge of a subset of solutions to a collection of problem instances without revealing which subset. The transformation uses a secret sharing scheme (S) with an access structure (Γ) to ensure that the prover only reveals information about qualified subsets. The resulting protocol has the same number of rounds as P and communication complexity roughly n times that of P. The method is general and can be applied to various types of protocols, including group-oriented identification and signatures. The paper also shows that for certain access structures, the protocol is witness hiding (WH), meaning even a cheating verifier cannot learn enough to compute the prover's secret. The results use no unproven complexity assumptions and can be efficiently implemented. The paper also discusses related work, including previous results on secret sharing schemes and zero-knowledge proofs. The main result is a theorem that describes the construction of a proof of knowledge from a basic proof of knowledge P and a family of secret sharing schemes. The paper concludes with applications to identification and signatures, showing how the new protocol can be used to create secure group-based systems.This paper presents a method to transform a proof of knowledge (P) into a witness indistinguishable protocol, which allows a prover to demonstrate knowledge of a subset of solutions to a collection of problem instances without revealing which subset. The transformation uses a secret sharing scheme (S) with an access structure (Γ) to ensure that the prover only reveals information about qualified subsets. The resulting protocol has the same number of rounds as P and communication complexity roughly n times that of P. The method is general and can be applied to various types of protocols, including group-oriented identification and signatures. The paper also shows that for certain access structures, the protocol is witness hiding (WH), meaning even a cheating verifier cannot learn enough to compute the prover's secret. The results use no unproven complexity assumptions and can be efficiently implemented. The paper also discusses related work, including previous results on secret sharing schemes and zero-knowledge proofs. The main result is a theorem that describes the construction of a proof of knowledge from a basic proof of knowledge P and a family of secret sharing schemes. The paper concludes with applications to identification and signatures, showing how the new protocol can be used to create secure group-based systems.
Reach us at info@study.space
Understanding Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols