2
$\begingroup$

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) $$

$\endgroup$
  • 2
    $\begingroup$ Either way is fine. Both 'regular' division or multiplication with the multiplicative inverse would do if either can be achieved. $\endgroup$ – savva Dec 18 '18 at 11:12
  • 2
    $\begingroup$ 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). $\endgroup$ – Geoffroy Couteau Dec 18 '18 at 13:03
  • 2
    $\begingroup$ 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$? $\endgroup$ – mikeazo Dec 18 '18 at 13:52
1
$\begingroup$

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.

$\endgroup$

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.