Can I prove that a message is part of a set of known messages without disclosing the message?

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 ?

• Does it have to be Elgamal? – deviantfan Nov 3 '16 at 15:19
• No. El Gamal would be preferred but maybe I can adapt to other schemes. – Hulub Nov 3 '16 at 15:26
• 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. – 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.
• 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. – Geoffroy Couteau Nov 8 '16 at 14:19