Skip to main content

Section 3.8 Homomorphisms and the lunchtime attack

Let \(G\) and \(G'\) be groups. We're going to introduce the notion of a very special type of function that relates the two groups, a function that preserves the structure of the first group in the second.

Definition 3.8.1.
Let \(G, G'\) be groups with operations \(\star_G, \star_{G'}\) respectively (viewed in the multiplicative sense). A function \(f:G \to G'\) is called a homomorphism if for all \(a, b \in G\text{,}\)
\begin{equation*} f(a \star_G b) = f(a) \star_{G'} f(b). \end{equation*}

As an example of a homomorphism, consider the function \(f:\Z \to \Z\) given by \(f(n) = 2n\text{.}\) Let \(m, n \in \Z\text{.}\) Then

\begin{equation*} f(m+n) = 2(m+n) = 2m + 2n = f(m) + f(n), \end{equation*}

which shows that \(f\) is a homomorphism. That is, we can add before or after applying \(f\) and get the same result.

Homomorphisms are one of the most important tools for understanding the relationships between different groups and also studying the structure of groups. It turns out that certain cryptographic functions also have the property of acting like homomorphisms, a property that is both useful and potentially dangerous, as it leads directly to some mathematically founded attacks in certain contexts.

Elgamal encryption can be seen to have a homomorphic property, in the following sense. Let \(m_1, m_2\) be plaintext messages, and suppose that \(e_k(m)\) is the Elgamal encrpytion function on \(F_p\ad\) for some large prime \(p\) and base \(g\text{.}\) Then

\begin{gather*} e_{k_1}(m_1) = (g^{k_1}, m_1 A^{k_1}) \\ e_{k_2}(m_2) = (g^{k_2}, m_2 A^{k_2}) \end{gather*}

Now, define the product of the encryptions by coordinate-wise multiplication in \(\F_p\ad \times \F_p\ad\text{:}\)

\begin{equation*} e(m_1)\star e(m_2) = (g^{k_1}, m_1 A^{k_1}) \star (g^{k_2}, m_1 A^{k_2}) = (g^{k_1+ k_2}, m_1 m_2 A^{k_1 + k_2}) = e_{k_1 + k_2}(m_1 m_2). \end{equation*}

That is, the product of the encryptions of \(m_1, m_2\) is the encrpytion of the product \(m_1 m_2\text{.}\) In this sense, we say that Elgamal encrpytion has the homomorphic property. (In fact, this is also posessed by RSA).

The homomorphic property has potentially many interesting uses. For example, consider the construction of a secure, anonymous voting system. A vote counter program produces an encrpytion \(e(1)\) of the number one. Each voter runs a program that produces \(e(2)\) if they vote yes and \(e(1)\) of they vote no, and they send their vote to the vote counter. The vote counter multiplies all of the pairs together

\begin{equation*} e(v_1)e(v_2)\ldots(v_n) = e(v_1 v_2 \ldots v_n) = e(2^i). \end{equation*}

On decrypting the final pair, the vote counter recovers an expression of the form \(2^i\) where \(i\) is the number of yes votes.

The homomorphic property allows many such applications to be designed that allow inputs to be contributed to a total without allowing any of the contributors to see the data. For example, multiple companies may wish to adjust the price of a product (taxes, customs, exchange rates) but without having access to the actual price of the product being adjusted.

Here again we see one of the main tensions in cryptograpy. Almost always when we gain convenience, we sacrifice security. The tradeoff for the utility of the homomorphic property is that cryptosystems that possess it become vulnerable to what is known as a lunchtime or chosen ciphertext attack. (There are actually two forms of chosen ciphertext attack. The example we give here is a nonadapative chosen ciphertext attack and presumes a limited window (a lunchtime) for the attacker Eve.)

Suppose that Eve has access to an Elgamal decryption oracle (like Alice's unlocked computer, for example). Then Eve can decrypt any ciphertext \((c_1, c_2)\) sent to Alice (even if the messages are in a list of previously decrypted texts are so are rejected by the oracle) by exploiting the homomorphic property. What should Eve send the oracle? Eve selects a plaintext \(m_e\) and encrypts it using Alice's parameters \(p, g, A\) to get \(e(m_e)\text{.}\) Using the homomorphic property, she multiplies the pairs

\begin{equation*} e(m_e) e(m) = e(m_e m) \end{equation*}

and gets a valid encryption. She submits the encrpytion to the oracle and receives the output \(m' = m_e m\text{.}\) Finally, since she knows the value of \(m_e\text{,}\) she computes

\begin{equation*} m' \cdot m_e\inv = m_e \cdot m\cdot m_e\inv = m \end{equation*}

and recovers the message \(m\text{.}\)

Exercises Exercises

1.