Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.