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 .

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 .


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)

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 .

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 .


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 :

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 :

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


c is the ciphertext of m


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

Example with small parameters and proof of homomorphism

The public key is (143,144)

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

Homomorphic Properties

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

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)
        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')
        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
# decrypt the ciphertext note the position of the parenthesis
d = l(c**lda % n**2,n) * mu % n
# 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 .