How to prove that a ciphertext is encrypting multiplication of two values?

Question

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

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.,

• Proof of correctness of a homomorphic ElGamal sum

• Is there a public key semantically secure cryptosystem for which one can prove in zero knowledge the equivalence of two plaintexts?

• http://www.win.tue.nl/sedan/sedan2009/SchoenmakersSedan2009.pdf

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