1
$\begingroup$

Suppose an encrypter separately produces three ElGamal ciphertexts $c_1 = E(m_1)$, $c_2 = E(m_2)$ and $c_3 = E(m_3)$, which encrypt the messages $m_1$, $m_2$ and $m_3$, respectively.

Is it possible for the encrypter to prove with a zero-knowledge proof that $m_1$ = $m_2 \mathbin\| m_3 = m_2 \times 2^{32} + m_3$, i.e., that $c_1$ encrypts the concatenation of the messages $m_2$ and $m_3$?


(added by moderator to summarize exchanges with the OP)

  • It is used a variant of ElGamal encryption, where for plaintext $m$ the group element $g^m$ is what gets encrypted using standard ElGamal.
  • In the expression $m_2\mathbin\|m_3$, plaintext integers $m_2$ and $m_3$ are bitstrings of fixed size (32-bit).
  • One option for the encrypter/prover is to make use of the ephemeral secret exponents generated at encryption.
$\endgroup$
3
  • $\begingroup$ Basically I want to use additive/exponential ElGamal with plaintexts of 64 bits. However, and because decryption requires solving the discrete log problem, I need to decompose the ciphertext of 64 bits in two ciphertexts of 32 bits, where the two 32 bits values concatenated correspond to the 64 bits value. $\endgroup$ – Fiono Mar 11 at 17:28
  • 1
    $\begingroup$ With additive/exponential ElGamal I mean encrypt $g^{m_i}$, instead of just the message $m_i$ (crypto.stackexchange.com/questions/9000/…), that's why you need to solve the discret log to decrypt. The message space of $m_2$ and $m_3$ is $2^{32}$ and $m_1$ is $2^{64}$, because it is the concatenation of $m_2$ and $m_3$ $\endgroup$ – Fiono Mar 12 at 15:23
  • 1
    $\begingroup$ This was initially transcribed without essential information, pointing to homework/assignment without showing effort towards a solution. Thus by our policy here are hints: exhibit a public function $f$ so that the desired proof is equivalent to proof that $c=f(c_1,c_2,c_3)$ would decrypt to zero; then make a zero-knowledge proof of that. This answer may help. $\endgroup$ – fgrieu Mar 12 at 16:41
1
$\begingroup$

We'll consider the additively homomorphic variant of ElGamal encryption, in a finite group with generator $g$ of prime order¹ $n$.

The private key is a random secret integer $d$ drawn uniformly randomly in $[0,n)$. The public key is $q\gets g^d$.

Encryption for integer $m$ goes:

  • Draw a random secret integer $k$ uniformly randomly in $[0,n)$
  • Compute $r\gets g^k$ and $s\gets g^m\cdot q^k$
  • Output ciphertext $(r,s)=c$ as the result of encryption of $m$, noted $E(m)$.

Decryption of ciphertext $(r,s)=c$ goes

  • Check that $r$ and $s$ are in the group
  • Compute $a\gets r^{n-d}\cdot s$
  • Find integer $m\in [0,n)$ with $g^m=a$. This requires tractable work for small $m$, using e.g baby-step/giant-step. For large $m$, we assume some oracle solves that problem when we write $D(c)$.
  • Output $m$ as the result of decryption of $c$, noted $D(c)$.

Note: Encryption $E$ is not a function. $D$ is one.

When $c=(r,s)$ and $c'=(r',s')$, we'll note $c\cdot c'$ for $(r\cdot r',s\cdot s')$; and $c^u$ for $(r^u,s^u)$.

It's easy to show that

  • if $0\le m<n$, then $D(E(m))\,=\,m$ [whatever $k$ was drawn by $E$]
  • $D(E(m)\cdot E(m'))\,=\,(m+m')\bmod n$
  • For any integer $u$ it holds that $D(E(m)^u)\,=\,(m\times u)\bmod n$ [where $\times$ is integer multiplication].

In the following, we assume the $c_i$ have been independently computed as $E(m_i)$ for $i\in\{1,2,3\}$; $m_2$ and $m_3$ are in $[0,2^{32})$; definition of $m_2\mathbin\|m_3$ as $m_2\times2^{32}+m_3$; and $n>m_1$, $n\ge2^{64}$.


(Given the value of such $c_i$) is it possible for the encrypter to prove with a zero-knowledge proof that $m_1\,=\,m_2 \mathbin\| m_3$?

Yes, if the encrypter/prover holds the private key $d$: define $c\gets{c_1}^{n-1}\cdot{c_2}^{(2^{32})}\cdot c_3$, and present any skeptical with a Zero-Knowledge Proof that $D(c)=0$ [see next paragraph]. Argue $D(c)=0$ proves $-m_1+m_2\times2^{32}+m_3\bmod n\,=\,0$, thus $m_1\,=\,m_2\times2^{32}+m_3$. The computation of $c$ won't be too tedious, for computing ${c_2}^{(2^{32})}$ requires computing a mere $62$ squares in the group, while ${c_1}^{n-1}$ requires at most $2\left\lfloor\log_2n\right\rfloor$ squares and less multiplications, using a standard method of exponentiation.

There remains to make a Zero-Knowledge Proof (ZKP) that $D(c)=0$; that is, with $c=(r,s)$, that it holds $r^{n-d}\cdot s\,=\,g^0$; equivalently, that $r^d=s$. The prover is assumed to know $d$, an can check this directly. The ZKP aims to convince the verifier knowing group elements $g,q,r,s$ that the prover knows $d$ such that $g^d\,=\,q$ and $r^d\,=\,s$. This the Chaum-Pedersen proof of equivalent discrete logarithms, explained there and there.

That should convince a rational verifier well versed in math. Good luck with that line of argument facing a random citizen fearing there was fraud in an election.


If the encrypter/prover does not hold the private key, but controls or keeps the $k_i$, there ares ways too.

A simple way is that the encrypter/prover generates $k_1$ as $k_1\gets k_2\times2^{32}+k_3$, rather than randomly. This ensures $c_1\,=\,{c_2}^{(2^{32})}\cdot c_3$, which is trivial for anyone to verify. That relation itself allows to prove this choice of $k_1$ [on top of the assumed $m_1=m_2 \mathbin\| m_3$] does not weaken anything. Even simpler, $c_1$ can be computed directly as $c_1\gets{c_2}^{(2^{32})}\cdot c_3$.

Computing and revealing $k\gets k_2\times2^{32}+k_3-k_1$ also does the job: it allows to check $c_1\cdot(g^k,q^k)={c_2}^{(2^{32})}\cdot c_3$, which conclusively proves $D(c_1)\,=\,D(c_2)\mathbin\|D(c_3)$. But I pass at proving my intuition there's nothing useful revealed, and I would not say it's a true ZKP.

But that can be turned to a true ZKP thru the Chaum-Pedersen proof of equivalent discrete logarithms: with $c=(r,s)$ defined as ${c_1}^{n-1}\cdot{c_2}^{(2^{32})}\cdot c_3$, the ZKP aims to convince the verifier knowing group element $g,q,r,s$ that the prover knows $k$ such that $g^k\,=\,r$ and $q^k\,=\,s$.


¹ That is: the group has $n$ elements $g^m=\underbrace{g\cdot g\ldots g}_{m\text{ terms}}$ for $m$ in $[1,n]$, with $g^n$ the group neutral $1$. For security, $n$ is usually a large prime. A simple example would be a Schnorr group.

$\endgroup$
1
  • 1
    $\begingroup$ @Fiono: I think I now outline valid Zero Knowledge Proofs both for a prover knowing the private key, and for a prover only knowing how the encryption was made. I still refer to another answer or reference for the Chaum-Pedersen proof of equivalent discrete logarithms. I hope I'll be able to put how it works in the answer. But don't hold your breath, that's all I have for you today. For good. Thanks for the question, I learned while answering it. $\endgroup$ – fgrieu Mar 16 at 22:04

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.