Damgard-Jurik Homomorphic Addition

I spent a happy hour with Ivan Damgård last week discussing a range of things:

One of his core advancements is the implementation of the Damgård-Jurik method [1]:

First, we select two large prime numbers (p and q) and compute:

and where lcm is the least common multiple. We then select random integer g for:

To encrypt a message (M), we select a random r value and compute the ciphertext of:

and then to decrypt:

and where L() is defined as:

If we take two ciphers (C1 and C2), we get:

If we now multiply them, we get:

And adding two values requires a multiplication of the ciphers. If we now divide them, we get:

Thus, a subtraction is equivalent to a divide operation. For this, we perform a modular divide operation. The coding is…