Starting Words

This post covers homomorphic encryption with an introductory perspective then shows example of two schemes the math is kept to a minimum but some terms that are used a lot need to be explained at first , every paper is referenced at the end of the post . A Later blogpost will look at other schemes and discuss the idea of bootstraping circuits .

• Group : A Group in mathematics is the most basic algebraic structure , it’s simply a set (a bunch of numbers) and an operation (addition,multiplication…) that fits certain criterias or axioms .
• Modulo : Modulo is the operation (%) in programming languages it results in the remainder of the integer division .
• Cyclic Group : A Cyclic Group is a group that can be generated from one element we call the generator imagine the group of powers of 2 {2^k} that’s a cyclic group it’s generator is 2 .
• Congruence: a = b (mod n) this reads a is congruent to b modulo n and simply means that a-b is a multiple of n .
• Finite Groups : a finite group is a group with a limited set ( a fixed number of elements ).
• Integers Modulo n : this is the most used types of groups in cryptography and this groups contains the number {0,1,2…, n-1} and all operation are modular .
• Modular arithmetic : we speak about modular operation for example modular addition when we do addtion in an integer modulo group , for example a clock uses modulo 12 addition .
• Modular multiplicative inverse : a modular multiplicative inverse of a number x is another number y such as xy = 1 mod n (the product xy is congruent to 1 modulo n) in simpler terms xy - 1 can be evenly divided by n
• Order of a group : the order of a group is the number of elements in it’s set .

We won’t need this much math to get an idea and work some examples but having a concept or an idea of what these are will help on the long term, I recommend two books if you want to dive deeper in the mathematics .

Introduction

Homomorphic Encryption is based on the idea of homomorphisms in Group theory put it simply a homomorphism is a function that maps one group to another such that :

f(a.b) = f(a).f(b) (1)

consider the dot to be an operation (additon or multiplication for ex) .

Homomorphic encryption is thus a structure/operation preserving encryption/mapping it’s use cases span across different areas for example electronic voting and machine learning anonymous location queries , search engines , cloud computing…

the word homomorphism is constructed of homos which means same in Greek and morphe which stands for shape .

Homomorphic Encryption

Encryption is the science or art of transforming plain text messages to an “encrypted” form hidden , homomorphic encryption is a form of encryption in which the formula we stated above is correct in other words the “f” is an encryption algorithm and the encryption of the product of two numbers is equal to the product of the encryptions of the numbers :

E(a.b) = E(a).E(b)

• E is an encryption algorithm or in more proprietary terms a scheme .

Now as any kind of encryption we can describe two ways of doing it either by using Secret Key Encryption or Public Key Encryption the first uses one key to both encrypt and decrypt a message , the second uses a public key to encrypt and a private key to decrypt mathematically speaking they are both theoretically secure alas in the real world it’s hard to get it right and a scheme such as RSA can be easily broken if it’s not padded .

RSA is actually the first public-key homomorphic encryption scheme but to achieve semantic security RSA needs to pad a message with random bits before ebcryption The padding results in RSA losing it’s homomorphic property so if you hear the words “RSA and Homomorphic Encryption” we are talking about unpadded RSA .

An encryption algorithm is called homomorphic if it’s fills the property (1) for some kind of operation as we are going to see next some schemes are only homomorphic with respect to addtion , some to both addtion and multiplication and the messages are usually numbers . There are multiple schemes that separate into two what we call Somewhat Homomorphic and Fully Homomorphic .

• Somewhat Homomorphic : You are limited in the kind of operations you can do between to ciphertext , you can add two ciphertexts but you can’t multiply them or you can multiply a ciphertext with a plaintext .

• Fully Homomorphic : You can typically evaluate any kind of operations on ciphertexts the term was coined by Rivest in 1978 but Craig Gentry was the first to introduce a scheme that works on arbitrary functions in his Phd thesis “ Fully Homomorphic Encryption using Ideal Lattices” . Key Point : homomorphic encryption and in general is defined by the propert0y (1) , the dot operation can represent any operation as long as the formula holds correct for that operation it can be addition,multiplication or modular multiplication .

• N.B : Many Public Key based schemes are “probabilistic” meaning that if you encrypt the same message multiple times it will yield a different ciphertext thus they introduce randomness to hide the smallest partial information about the plain text what we call semantically secure .

Examples Of Schemes

In this section we introduce a few schemes and we show a few examples using small parameters and Python to describe this process . Note that the code is here is merely toy examples don’t use it in real life because as you will learn in cryptopals it’s hard to implement crypto .

Paillier

The Paillier scheme , was invented by Pascal Paillier in 1999 it’s a probabilistic scheme that is homomorphic with respect to addition ( the sum of two ciphertext is equal to the ciphertext of the sum of the two plaintext equivalents) and to multiplication by a constant .

Suppose E is the paillier encryption function then we have the following two properties :

• E(a)+E(b) = E(a+b)
• E(a)^b = E(a * b)

Paillier is composed of three algorithms in fact three algorithms are necessary to create an encryption scheme .

First you need a Key generation algorithm, second an encryption algorithm and last a decryption algorithm let’s see how Paillier implement those .

Key Generation

To generate a key you choose two large primes p and q such that :

• gcd(pq,(p-1)(q-1)) = 1 In otherwords the product of p and q and (p-1) and (q-1) are relatively prime ( their greatest common divisor is 1) .

Then you compute two parameters n & lambda such that : * n = pq and lambda = lcm(p-1,q-1) LCM is the least common multiple for example lcm(4.8) = 16

• Select a random integer g such as g belongs to the set of integers modulo n squared . in this case (p and q are primes of the same length) you can pick g as n+1

• Compute mu such as mu = lambda^-1 mod n (modular multiplicative inverse)

• The public key is (n,g) and the private key is (lambda,mu)

Encryption

• suppose m is your message and r a random number such as :

  m < n and r < n

• c = g^m * r^n mod n^²

c is the ciphertext of m

Decryption

• m = L(c^lambda mod n^²) * mu mod n
  

L(x) = (x-1) / n

Example with small parameters and proof of homomorphism

• let p = 11 and q = 13
• n = pq = 143
• g = n+1 = 144

The public key is (143,144)

Let’s encrypt the answer of the universe and send it to the Zorbs ( habitants of Zorbis planet )

• m = 42

• we pick r : r = 23

• c = g^m * r^n (mod n^2) = 144^42 * 23^143 (mod 143^2) = 9637

• m = L(c^lambda mod n^2) * mu mod n

  lambda = (p-1)*(q-1) = 10*12 = 120 mu = lambda^-1 mod n = 120^-1 mod 143

  m = L(9637^120 mod 143^2) * (120^-1 mod 143) mod 143

  m = 42

• note that you should use modular inverse to compute mu

Homomorphic Properties

Now that we defined the the procedure to generate a keypair, encrypt and decrypt let’s discuss the homomorphic properties of Paillier .

• Addition :

  • The product of two ciphertexts decrypts to their sum , if I want to do addition on ciphertexts relatively to my plaintexts I have to calculate the product of the ciphers
  • Proof suppose E is the encryption algorithm and m1 and m2 the plaintexts : E(m1) * E(m2) = (g^m1*r1^n)(g^m2*r2^n) mod n^2 = g^(m1+m2) (r1r2)^n mod n^2 = E(m1+m2)

• Multiplication:

  • If I have a plaintext m and a constant k then the encryption of their product evaluates to the cipher of m raised to the power k .
  • Proof same suppositions about E,m1,m2 as before : E(m1)^m2 = (g^m1+r1^n)^m2 mod n^2 = g^(m1m2) (r1^m2)^n mod n^2 = E(m1m2)
    

Python Example Implementation

The following code can be used to run the example we made above using the same parameters

# we need the inverse modulo operation 
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

# we also define the l function
def l(u,n):
    return (u-1)/n

# pick two primes
p = 11
q = 13
# compute n
n = p*q
# pick g and since p and q are of the same length we can use n+1 
g = n+1
# compute lambda
lda = (p-1)*(q-1)
# compute mu
mu = modinv(lda,n)
# declare a message
m = 42
# pick r such as r<n
r = 23
# compute the cipher text
c = g**m * (r ** n % n ** 2)
# let see the ciphertext
print(c)
# decrypt the ciphertext note the position of the parenthesis
d = l(c**lda % n**2,n) * mu % n
print(d)
# let's make an addition
k = 10
# encrypt k
ck = g**k * (r**n % n**2)
# decrypt and save k
dk = l(ck**lda % n**2,n) * mu % n
# verify E(m) * E(k) == E(m+k)
cres = ck * c
# decrypt result 
dres = l(cres**lda % n**2,n) * mu % n

Ending Notes : I don’t think I treated every bit of the subject in this blogpost but the aim was to present and explain the ideas as clearly as possible for a more in depth treatment you can read the references below . Other schemes that are partially homomorphic are Elgamal ( yes the same one used by GNUPGP ), Goldwasser-Micali, and the Boneh-Goh-Nissim that operates on elliptic curves .

I would like to thank Andrew Trask for his suggestions and taking time to read an early draft .

References

• Abstract Algebra : A book of abstract algebra by Charles C.Pinter
• Number Theory : Summing it up by Avner Ash and Robert Gross
• Paillier Paper : PDF
• Gentry 2009 FHE using Ideal Lattices : Link
• Goldwasser-Mical : Wiki
• Boneh-Goh-Nissim : PDF