If Alice sends an encrypted message to Bob, how can Bob prove to Charlie that the message he received from Alice is part of a set of predefined messages, without disclosing the encryption key or the message itself.

Let's say we use El Gammal encryption scheme and let's say the predefined messages are M = {1,2}. Bob's pair of keys are x and y = gx.

Alice encrypts message m $\in$ M and sends the tuple (c,e), where c = gr, e = yr * m and r = random.

How can Bob prove that the decryption of (c,e) $\in$ M, without revealing the value of m ? Maybe some sort of zero-knowledge proof ?

  • 1
    $\begingroup$ Does it have to be Elgamal? $\endgroup$ – deviantfan Nov 3 '16 at 15:19
  • $\begingroup$ No. El Gamal would be preferred but maybe I can adapt to other schemes. $\endgroup$ – Hulub Nov 3 '16 at 15:26
  • $\begingroup$ With a non-probabilistic scheme like RSA, stupid but simple: Ask Alice to a) encrypt all elements of M, b) shuffle them in a (crypt. secure) random order, and c) make them public. Then let Charlie search Bobs c in the set. $\endgroup$ – deviantfan Nov 3 '16 at 15:30

Yes, this can be done. For your simple example, what you want amounts to an "OR proof", a proofs that shows that one of two statements is true. Let $(c, c')$ be your ciphertext; to show that it encrypts either 1 or 2, you just have to prove that "$(g,h,c,c')$ is a DDH tuple OR $(g,hc,c'/2)$ is a DDH tuple".

Proving that a tuple $(g,h,g',h')$ is a DDH tuple is the classical "proof of same discrete logarithm in different bases" (you prove that $\log_g(g') = \log_h(h')$) (see e.g. this answer). To perform an OR proof, the idea is simply to perform two proofs for the two statements in the clause in parallel, but sending a challenge that binds only the prover to, say, the sum of the challenges. This gives him the freedom to choose one of the challenges before the execution of the protocol, and therefore to forge the corresponding proof, but not both; therefore, the prover will be able to forge at most one proof, and the verifier cannot know which one. See for example this article.

This generalizes to OR with arbitrarily many clauses, and so to "sets of messages" of arbitrary size, but the size of this proof is linear in the size of the set of messages. I know that if you use the additive ElGamal instead (a ciphertext is of the form $(g^r, h^rg^m)$), there are way more efficient methods: this article, for example, provides a zero knowledge proof of membership of an (additive) Elgamal plaintext to a known set of size $n$ in communication $O(\log n)$. The same holds for other cryptosystems with additive properties; for the standard ElGamal scheme, there might also be efficient proofs (in fact, there are necessarily such proofs, as we have ZK arguments for any statement in communication polylog, but the constants involved in these generic construction would be highly impractical here), but I do not know much about this specific case.

  • $\begingroup$ Thank you very much for your answer, Geoffroy ! I have read the last article but it is beyond my understanding :) $\endgroup$ – Hulub Nov 8 '16 at 8:42
  • $\begingroup$ I have realized that, it is actually Alice who needs to prove that the message she encrypted is part of the predefined messages. So I need to prove set membership in elgamal style. I have came over this answer of yours (crypto.stackexchange.com/a/40982/40796), that I think might suit me in this case, but I don't understand why the homomorphic sum of the encryptions of x, x^2, ... ,x^n would result in an encryption of 0. $\endgroup$ – Hulub Nov 8 '16 at 8:52
  • $\begingroup$ Let $(d_1, \cdots, d_n)$ be a database. Let $P(X) = \prod_{i=1}^n (X-d_i) = \sum_{i=0}^n a_i X^i$ be a degree $n$ polynomial, whose $n$ roots are exactly the elements of the database. Then $P(x) = 0$ is equivalent to the statement "$x$ is in the database". Given encryptions of $(x, x^2, \cdots, x^n)$ and the coefficients $a_i$ of $P$, one can compute an encryption of $r\cdot\sum_{i=0}^n a_i x^i = r\cdot P(x)$, if the encryption scheme supports linear operations (as for the additive variant of ElGamal), for a random $r$. From the view of the other player, this is either $0$ or random. $\endgroup$ – Geoffroy Couteau Nov 8 '16 at 14:19

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.