Zero-knowledge proofs with soundness, completness and zero-knowledge enable a prover to convince a verifier that a witness validates successfully a predicate without giving any information about the witness and without the verifier being able to extract the witness from the commitment C. Such kind of functionalities are useful in ecash,evoting,anonymous credentials, etc. In an abstract way the sender wants to convince a set of parties that he knows how to open the commitment and also that the commitment entails a message with specific properties.

So a Zero-Knowledge proof can be seen as an extension of a commitment scheme but without giving the opportunity ever to the receiver to open the commitment and with allowing the receiver to verify a statement-predicate.

If we work in a public key setting with DLP as the hardness assumption such as ElGamal then the sender without giving the key to the untrusted verifier can provide proofs of zero-knowledge that the encrypted values does contain a value that follows some properties, using Schnnor or Pedersen protocols as a building block.

However i am not aware of any kind of proofs that the encrypted value under some stream cipher for instance:$E(m)=m \oplus k=c$ for some random key k can be used to convince the verifier that c is the encrypted value of $m=a*b$ for some $a,b \in [0,range]$. Or more generally how i can prove that i have encrypted some specific values by giving the receiver only the ciphertext. Because it might be trivial that in a protocol you can prove a zero-knowledge of a value that you hold and you can use (for obtaining access anonymously to some credentials) but in most of the times this value is sent encrypted so there must be an association between the ciphertext that truly contains what is supposed to be known in the ZK proof and the ZK proof itself


1 Answer 1


Yes, this is doable. You can verify that $m=a \times b$, given El Gamal encryptions of $m,a,b$, since El Gamal is multiplicatively homomorphic. You can also prove that the El Gamal decryption of some ciphertext is in a given range (using a combination of Schnorr proofs). Putting those two together will give your first desired primitive.

This requires you to use El Gamal encryption rather than a stream cipher. However, if this is a problem, it is also possible to do it for other encryption schemes as well. It is known that every statement in NP can be proven in zero knowledge using generic (but slow) schemes, so this can also be extended to work for any stream cipher. The advantage of ZK proofs based upon El Gamal or other public-key schemes is that they can be made more efficient.

See, e.g.,

There is tons written on this subject in the research literature. You'll need to do more research on your own to learn this subject. You should spend some days studying basic material on learning elementary zero knowledge proofs, first by reading textbooks, then by reading some of the classic papers. A good starting point would be to look at textbooks on theoretical cryptography, such as Rafael Pass and abhi shelat's lecture notes and Wenbo Mao's textbook. You could also read http://www.austinmohr.com/work/files/zkp.pdf

  • 1
    $\begingroup$ Yes but what if you don't want to use DLP based public key encryption schemes? $\endgroup$
    – curious
    Dec 26, 2013 at 9:23
  • 3
    $\begingroup$ Then you can use use a generic proof/argument system. $\;$ $\endgroup$
    – user991
    Dec 26, 2013 at 17:03
  • $\begingroup$ What do you mean by generic proof argument? How i can convince that the non-DLP encrypted value lies in predefined range?I just make a huge assumption that the encrypted values is the witness for a proof that is submitted independent from the ciphertext? $\endgroup$
    – curious
    Jan 10, 2014 at 12:05
  • $\begingroup$ @curious, about your question on generic proof argument: see the sentence in my answer "It is known that every statement in NP..." Generic proof argument refers to a ZK proof that uses that general result. $\endgroup$
    – D.W.
    Jan 10, 2014 at 15:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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