4
$\begingroup$

Let $g$ be a generator of a multiplicative group $G$ of order $q$, $x$ be a private key, and $h=g^x$ be a public key of an exponential ElGamal cryptosystem.

Given a ciphertext $c$ produced as the ElGamal encryption of a given plaintext $m$, that is $Enc(m,h,r)=(g^r, g^m h^r)=(R,S)=c$, it is obvious that this ciphertext can be decrypted by using the private key $x$. So $Dec(c,x)=\log_g \frac{S}{R^x}=m.$

However, it seems also quite clear to me that another way of decrypting it without being in possession of the private key is by knowing the random value $r$, so $\log_g \frac{S}{h^r}=m$.

Let's assume we have a protocol in which Alice first publishes some encrypted message, and after a while, she wants to reveal it by just revealing what the random value $r$ was. This may remind a Pedersen commitment scheme, with the difference that when opening the encryption, I would like Alice to reveal only $r$, and not both $r$ and $m$.

Does this make any sense? How certain can Bob be that the value $r$ that Alice just revealed, is the one she actually used to generate $c$, and she didn't make it up?

$\endgroup$
2
  • $\begingroup$ I am wondering why you actually use the additive homomorphic variant of ElGamal, where decryption requires computation of a discrete log. This limits your message space a lot and I cannot see any benefit right now. $\endgroup$
    – tylo
    Oct 10, 2013 at 16:28
  • $\begingroup$ You're right. I was using exponential ElGamal because the plaintext in this protocol is within a restricted set of allowed values. But for this question I thought it wasn't relevant to mention. It could have perfectly worked with the non-additive homomorphic variant. $\endgroup$
    – LRM
    Oct 11, 2013 at 9:35

2 Answers 2

3
$\begingroup$

If $(G,q)$ are public authentic parameters and Alice publishes $(h,R,S)$, then if Alice later publishes $r$, Bob needs to check if $g^r=R$, which fixes $r$. Consequently, when computing $\log_g S/h^r$ also fixes $h$ and the exponent of $S$ is fixed. Changing $m$ to $m'$ would require to solve $m+rx\equiv m'+r'x \pmod{q}$ for $r'$. However, since $r$ is fixed in $R$, this does not work out without changing $R$ to $R'\neq R$ and same argument for $x$ which would change $h$ to $h'\neq h$ (but this can be detected).

But why should Alice not give $(r,m)$ to Bob and Bob runs $Enc(m,h,r)$ again and checking whether the computed result matches $(R,S)$ previously published by Alice? This would also be more efficient as you avoid computing $\log_g S/h^r$.

$\endgroup$
2
  • $\begingroup$ So computing the encryption again, given the claimed plaintext $m$, the public key $h$ and the randomness used $r$ would be more efficient than letting Bob know the plaintext $m$ by computing $\log_g \frac{S}{h^r}$? Why is it that? (assuming that, as I commented, the plaintext is within a restricted set of allowed values, and thus the $\log_g$ is kind of feasible and efficient to compute). $\endgroup$
    – LRM
    Oct 11, 2013 at 9:45
  • $\begingroup$ Recomputing the ciphertext costs 3 exp + 1 mult. Your version costs at least 1 exp + 1 mult + dlog computation, where the dlog computation will cost more than 2 exp (when compared to the recomputation of the ciphertext). $\endgroup$
    – DrLecter
    Oct 11, 2013 at 10:57
2
$\begingroup$

The published ciphertext is $(R,S) = (g^r,h^r g^m)$.

Now Alice publishes $r$. But since Bob can check if $g^r=R$ holds, she cannot cheat at this point. If the public key $h$ is fixed and known, the message can be decrypted: $m=log (S/h^r)$.

So concerning your questions: Yes, it's enough if Alice publishes $r$ and she can not cheat.

The difference to Petersen commitments is simple: There you have 2 variables and your commitment is just a single value. If you know the trapdoor you just have a single equation with 2 variables and 1 constant(the commitment) and can choose one of the inputs arbitrarily. In ElGamal the ciphertext consists of 2 values and 2 variables

(unless you consider the public key $h$ as variable. But that's a different ballgame).

$\endgroup$

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.