2
$\begingroup$

Recently I'm studying learning with errors crypto systems and I'm running into a problem. I try to prove that the plaintext is in some specific range(for example 0~10) using zero knowledge proof.

However, almost all the papers I find in Google are talking about constructing "zero knowledge proof of knowledge" schemes, but what I want is zero knowledge proof, can these two primitives transfer to each other?

$\endgroup$
3
$\begingroup$

A zero-knowledge proof $\rho$ demonstrates that an instance $\phi$ is in a relation $R$, i.e. there exists $w$ such that $(\phi, w) \in R$.

A zero-knowledge proof of knowledge $\pi$ for an instance $\phi$ demonstrates that the random tape of the PPT algorithm that calculated $\pi$ can be used as the input to a PPT extractor to output $w$ such that $(\phi,w) \in R$.

If $w$ does not exist, then there can be no such extractor. Thus any zero-knowledge proof of knowledge is also a zero-knowledge proof. However, not every zero-knowledge proof is a zero-knowledge proof of knowledge. In particular, Groth-Sahai proofs do not have knowledge extraction.

$\endgroup$
2
$\begingroup$

Proof of knowledge property is existence of extractor algorithm, informally making sure prover has (knows) the witness to relation he is proving. Zero knowledge is another property, indistinguishability of recorded proof session (session transcript) from output of simulator algorithm. Despite coming together often, "of knowledge" and "zero knowledge" are completely different.

$\endgroup$
  • $\begingroup$ Adding to this, in terms of examples, we have libsnark (and all (?) other zk-snarks) as examples of zero-knowledge proofs, and Schnorr signatures (and all other sigma protocols) as examples of proofs of knowledge. $\endgroup$ – bekah Apr 9 '17 at 17:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.