# Decrypting without using the private key

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?

-
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. –  tylo Oct 10 '13 at 16:28
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. –  LRM Oct 11 '13 at 9:35

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

-
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). –  LRM Oct 11 '13 at 9:45
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). –  DrLecter Oct 11 '13 at 10:57
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.
(unless you consider the public key $h$ as variable. But that's a different ballgame).