Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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.
