#### Crypto Journal Part II : Homomorphic Encryption

##### An introduction to homomorphic encryption

### 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

homoswhich means same in Greek andmorphewhich 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 .