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
The paper presents a method to transform a proof of knowledge $\mathcal{P}$ into a witness indistinguishable protocol $\mathcal{Q}$, where the prover demonstrates knowledge of solutions to a subset of problem instances defined by a secret sharing scheme $\mathcal{S}$. The transformation is based on a monotone access structure $\Gamma$ and a smooth secret sharing scheme $\mathcal{S}$ such that the access structure of $\mathcal{S}$ is the dual of $\Gamma$. The resulting protocol $\mathcal{Q}$ has the same number of rounds as $\mathcal{P}$ and communication complexity proportional to $n$ times that of $\mathcal{P}$. The paper also shows that for certain access structures, the protocol is witness hiding, meaning even a cheating verifier cannot compute the prover's secret. This method simplifies the design of witness hiding protocols and can be used to implement group-oriented identification and signatures efficiently. The results do not rely on unproven complexity assumptions.The paper presents a method to transform a proof of knowledge $\mathcal{P}$ into a witness indistinguishable protocol $\mathcal{Q}$, where the prover demonstrates knowledge of solutions to a subset of problem instances defined by a secret sharing scheme $\mathcal{S}$. The transformation is based on a monotone access structure $\Gamma$ and a smooth secret sharing scheme $\mathcal{S}$ such that the access structure of $\mathcal{S}$ is the dual of $\Gamma$. The resulting protocol $\mathcal{Q}$ has the same number of rounds as $\mathcal{P}$ and communication complexity proportional to $n$ times that of $\mathcal{P}$. The paper also shows that for certain access structures, the protocol is witness hiding, meaning even a cheating verifier cannot compute the prover's secret. This method simplifies the design of witness hiding protocols and can be used to implement group-oriented identification and signatures efficiently. The results do not rely on unproven complexity assumptions.
Reach us at info@study.space