I've decided to remove a previous unanswered question of mine and break it down into smaller pieces so it's not such a loaded question.

For this question I need to prove that I've committed to a number, and that same number is the plaintext of some ElGamal ciphertext, without opening the commitment or decrypting the ciphertext. I have a start, as in I know a proof that is supposed to work, but I need some help.


I have standard ElGamal encryption wherein plaintext $v$ is encrypted as $u$ as follows: $$E(v)=u=(y_{1},y_{2})=(\alpha^{r},v\beta^{r}) \mod p$$ where $p$ is a safe prime $p=2q+1$, $q$ is also a large prime, and $r \in _{R}\mathbb{Z}_{p}$.

I also have a commitment scheme that is very similar to Pedersen commitment, called Fujisaki-Okamoto commitment. Given large safe primes $p^{\prime}$ and $q$, $N=p^{\prime}q$; public elements $g$ and $h$ are both generators in $G$, a large cyclic subgroup of $\mathbb{Z}^{*}_{N}$ (such that $\log_{g}h$ and $\log_{h}g$ are intractable). I commit to $v$ with $$C=g^{v}h^{r^{\prime}}\mod N$$ where $r^{\prime} \in _{R}\mathbb{Z}_{N}$.


I need to prove that $v$ is encrypted in $u$ and committed in $C$. My understanding based on what I'm trying to implement is that I need to prove knowledge of $v$, $r$, and $r^{\prime}$ such that $$y_{1}=\alpha^{r} \mod p$$ $$y_{2}=v\beta^{r} \mod p$$ $$ C=g^{v}h^{r^{\prime}} \mod N$$

I know that Markus Stadler has a proof of verifiable encryption of discrete logarithms in Publicly Verifiable Secret Sharing §3.3. This uses a double discrete logarithm proof to show that a ciphertext $u=(y_{1},y_{2})$ encrypts the discrete logarithm of a public element $V=g^v$. The protocol I am trying to implement says this proof will work, but it does not tell me how to use it in this context, just that I can. It seems straightforward to me except for two things, which I've listed in order of importance:

  1. I don't just have some public element $V=g^v$. I have a public element $C=g^{v}h^{r^{\prime}}=Vh^{r^{\prime}}$. This product, obviously vital to the commitment scheme, seems to make it so that I can't use Stadler's PVSS scheme. But the paper insists that it works, so I'm obviously just missing something.
  2. In Stadler's paper he defines ElGamal encryption as $(\alpha^{r},v^{-1}\beta^{r})$ rather than $(\alpha^{r},v\beta^{r})$. I've never seen it done this way and the protocol I'm implementing does it the normal way. But Stadler's proof seems to depend on that modular inverse. Can I use this proof without changing the encryption scheme?
  • $\begingroup$ did you ever figure this out? $\endgroup$ – hlz2103 May 19 '19 at 15:39
  • $\begingroup$ Sorry, no, I did not. $\endgroup$ – Mike Carpenter May 23 '19 at 17:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.