# Can I perform a division of two integers homomorphically using ElGamal?

How can I perform a division of two integers homomorphically? (Simplifying assumptions can be made if needed, that is, I am fine with dividing numbers that are whole and the result will be whole as well, e.g., simple divisions such as 4 divided by 2 are fine)

Given two ElGamal ciphertexts: $$C_1 = (C^{1}_{1}, C^2_1)$$ $$C_2 = (C^{1}_{2}, C^2_2)$$

I can multiply them homomorphically as follows: $$C_r = (C^{1}_{1} \cdot C^{1}_{2} ,C^2_1 \cdot C^2_2)$$

The following does not seem to work to achieve division though: $$C_r = (C^{1}_{1} \div C^{1}_{2} ,C^2_1 \div C^2_2)$$

• Either way is fine. Both 'regular' division or multiplication with the multiplicative inverse would do if either can be achieved. – sava Dec 18 '18 at 11:12
• Why does the term by term division fail, then? Can you provide details? It seems to me that it works perfectly fine (for multiplication with the inverse). – Geoffroy Couteau Dec 18 '18 at 13:03
• Given an ElGamal ciphertext, can you compute the multiplicative inverse of that plaintext? Think about this, given an ElGamal ciphertext, can you raise it to a power? Does it matter if the power is $-1$? – mikeazo Dec 18 '18 at 13:52

Let $$G$$ is a cyclic group with order $$q$$ and generator $$g$$.

Let $$x$$ be Alice's private key. The two messages $$c_1$$ and $$c_2$$ are encrypted with the public key of Alice;

$$c_1 = (g^{y_1}, m_1 \cdot g^{x y_1})$$

$$c_2 = (g^{y_2}, m_2 \cdot g^{x y_2})$$

Now to calculate $$m_1/m_2$$ in the encrypted values, calculate the inverse of $$g^{y_2}$$ and $$m_2 \cdot g^{x y_2}$$ in the group

$$c_2'=\Big((g^{y_2})^{-1},(m_2 \cdot g^{x y_2} )^{-1}\Big) = (g^{-y_2},m_2^{-1} \cdot g^{-x y_2})$$

then multiply,

$$c_1 c_2' = (g^{y_1} g^{-y_2}, \;\; m_1 m_2^{-1} \cdot g^{x y_1} g^{- x y_2})$$

Now, check the decryption.

$$s = (g^{y_1} g^{-y_2})^x = g^{x y_1 } g^{-x y_2 }$$

$$s^{-1} = g^{-x y_1 } \cdot g^{x y_2 }$$

$$s^{-1} \cdot m_1 m_2^{-1} \cdot g^{x y_1} g^{- x y_2} = m_1 m_2^{-1} \cdot g^{-x y_1 }g^{x y_1}\cdot g^{x y_2 } g^{- x y_2} = m_1 m_2^{-1}$$

Note: based on comments of Geoffroy and Mikeazo.