# ElGamal encryption of concatenated messages

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.
• 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. – Fiono Mar 11 at 17:28
• 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$ – Fiono Mar 12 at 15:23
• 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. – fgrieu Mar 12 at 16:41

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

• @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. – fgrieu Mar 16 at 22:04