3
$\begingroup$

Suppose Alice wants to convince Bob that ciphertext c = (a, b) = (gr, m*hr) is some properly encrypted plaintext (not just random numbers). Obviously she can use zk-proof of discrete logarithm knowledge for the first part of the ciphertext (a = gr). But what can she do with b-part?

One of my ideas: if m belongs to subgroup G (with a generator g) than we should prove that b belongs to G. But it's just a new problem.

Alice can also use exponential ElGamal (c = (gr, gm * hr)) if it makes things easier.

$\endgroup$
  • $\begingroup$ One can use the same response for $r$ (part of the proof) for two proofs about both parts of the ciphertext. "Some $r$ exists" seems somewhat general; practical cases may include something like "and $m$ is either $g$ or $1$" (0 or 1 for the second variant). Will you refine your "properly" condition? $\endgroup$ – Vadym Fedyukovych Nov 17 '18 at 16:13
3
$\begingroup$

Actually, an ElGamal ciphertext $(a,b)$ is "valid" iff $(a,b) \in G^2$, because for any message $m\in G$ and any $\mathsf{pk}\in G$, the encryption of $m$ will be in $G^2$, because for any $r$, $(g^r,\mathsf{pk}^r\cdot m)\in G^2$, and any $(a,b)$ chosen in $G^2$ can be correctly decrypted by any secret key by computing $m=\frac{b}{a^\mathsf{sk}}$. The proof of knowledge of the random coin $r$ is sufficient to show that you know how the ciphertext was produced.

I do not know if that answers your problem.

$\endgroup$

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.