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 [here]:

import sys
import math
import sympy

import random



def generate_keys(key_size: int, s:int):


        private = {}
        public = {}

        # picking a prime modulus p
        p = sympy.randprime(200, 2 ** int(key_size / 2) - 1)

        # picking a prime modulus q
        q = sympy.randprime(200, 2 ** int(key_size / 2) - 1)

        n = p * q
        phi = (p - 1) * (q - 1)
        g = 1 + n

        private["phi"] = phi
        public["g"] = g
        public["n"] = n
        public["s"] = s

        return public,private

def generate_random_key(public) -> int:

        n = public["n"]
        while True:
            r = random.randint(0, n)
            if math.gcd(r, n) == 1:
                break
        return r

def encrypt(plaintext: int, public) -> int:

        g = public["g"]
        n = public["n"]
        s = public["s"]
        r = generate_random_key(public)
        modulo = pow(n, s + 1)

        # assert math.gcd(r, n) == 1
        c = (pow(g, plaintext, modulo) * pow(r, n, modulo)) % modulo
        # c = (pow(g, plaintext, modulo) * pow(r, pow(n, s), modulo)) % modulo
        if math.gcd(c, modulo) != 1:
            print(f"WARNING! gcd({c=}, {modulo=}) != 1")
        return c

def decrypt(ciphertext: int,private,public):

        phi = private["phi"]
        n = public["n"]
        s = public["s"]
        mu = pow(phi, -1, n)
        modulo = pow(n, s + 1)
        return (lx(pow(ciphertext, phi, modulo),public) * mu) % (n)


def lx(x: int,public) -> int:

        n = public["n"]
        y = (x - 1) // n
        assert y - int(y) == 0
        return int(y)

def add(ciphertext1: int, ciphertext2: int) -> int:

        n = public["n"]
        s = public["s"]
        modulo = pow(n, s + 1)
        return (ciphertext1 * ciphertext2) % modulo
m=17
size=512
s=2

if (len(sys.argv)>1):
        m=int(sys.argv[1])
if (len(sys.argv)>2):
        size=int(sys.argv[2])
if (len(sys.argv)>3):
        s=int(sys.argv[3])

public,private=generate_keys(size,s)
print(f"Private key: {private}")
print(f"Public key: {public}")

c=encrypt(m,public)
dec=decrypt(c,private,public)


print(f"\nMessage: {m}")
print(f"\nCipher: {c}")
print(f"Decrypted: {dec}")

A sample run for a 256-bit key, and s=1 is [here]:

Private key: {'phi': 24001407654956119264721128387458981691220785025776976305747529296534434921096}
Public key: {'g': 24001407654956119264721128387458981691535418673875384690055859658797341718148, 
'n': 24001407654956119264721128387458981691535418673875384690055859658797341718147, 
's': 1}

Message: 17
Cipher: 384415440803606946384620962713753118937944833141614876023924448758702168125558444152634347525009513185366019685082817987474249492612237098447322494219673
Decrypted: 17

A sample run for a 256-bit key, and s=2 is [here]:

Private key: {'phi': 6091240706358163024705845011452310049528827638673364300996233701574105419056}
Public key: {'g': 6091240706358163024705845011452310049692888519273154963509416918349853868578, 
'n': 6091240706358163024705845011452310049692888519273154963509416918349853868577, 
's': 2}
Message: 17
Cipher: 118430786705261162890889105913722772229994929188193916717150526128048013954786153540173587843413022773633685287213680976978369843541736487268018811200393968429888136006503630689583854083211391712961105839946602470439713048899672
Decrypted: 17

and where we double the cipher range.

We can now implement homomorphic addition with:

Damgard-Jurik Public Key Encryption Public Key Encryption for Addition homomorphic

The work on “A Generalisation, a Simplification and Some Applications of Paillier’s Probabilistic Public-Key System” received the Test of Time Award at PKC 2001.

References

[1] Damgård, I., Jurik, M., & Nielsen, J. B. (2010). A generalization of Paillier’s public-key system with applications to electronic voting. International Journal of Information Security, 9(6), 371–385.