April 18, 2018

Crypto Journal Part III : Fully Homomorphic Encryption Part I : Secret Key Homomorphic Encryption Over Integers

EP

In the previous post we discussed homomorphic encryption in it’s most abstract terms we presented Paillier as a partially homomorphic encryption . Thank you @mortendahlcs for making a clarification about the terms described :

  • Somewhat Homomorphic means you can do both addition and multiplication but only a limited number times ( I will explain why below)
  • Paillier doesn’t allow multiplication between two ciphers this is called a Partially Homomorphic scheme .

Alrighty then in this post I will try to explain an analogy between FHE and mathematics , and I will explain Gentry’s breakthrough by using a scheme published after his first papers where instead of using ideal lattices the scheme uses integers it will be easier to explain that way and also provide examples without much math .

In the next post we discuss Public Key HE and explain bootstrapping


We will start with some math this way we can have an abstraction of the subject and help us understand a bit more about homomorphic encryption in general .

Pre definitions

  • We will start by introducing mathematical concepts like in the last time as usual this part was made to help the reader gain a vocabulary to sound smart at parties everyone is amazed by the person that can say the 8 axioms that define rings as algebraic structures:

  • Ring : A Ring is the savant son of the group , more precisely an abelian group , abelian here means that the group’s operation is commutative meaning :

    • If * (star) is an operation in a group G and X & Y are two elements of G then we have this equality : X * Y = Y * X

    • A Ring is then an abelian group but with more rules or axioms more importantly a ring has two operations mainly addition and multiplication

    • It’s closed under multiplication and addition , the product or sum of two elemnts of a Ring is an element of the ring .

    • Multiplication is associative in other words if we have X,Y,Z then X * (Y * Z) = (X * Y) * Z

    • Left and Right distributivity : X * (Y+Z) = X * Y + X * Z and (X + Y) * Z = X * Z + Y * Z

  • Circuits : This term is present in many papers you will often face the term arbitrary circuits this stands for boolean circuits you studied sometime in your life

  • It’s important to understand that until this point we discuss operations in term of circuits and bits and not generic algorithms (more on this later)

  • Ring Homomorphism : We explained what homomorphism was in the last post, a ring homomorphism is a function between two rings such that :

    • f(a+b) = f(a)+f(b) and f(a * b) = f(a) * f(b)
  • Residue mod p : This term may sound complex but it actually means the remainder of the integer division whenever you here r is a residue mod p of a think a = r (mod p) . ( even modular forms sounds complex but it’s simple

  • What scheme means , when we discuss a scheme or a cryptosystem we generally mean to describe a three component system to do cryptography this system is composed of three algorithms .

    • We need a Key Generation algorithm
    • An Encryption Algorithm
    • A Decryption Algorithm

Gentry’s Fully Homomorphic Scheme

Craig Gentry released the first fully homomorphic encryption scheme that is based on ideal lattices ( no need to know what it is for now ) on June 25st 2009 . His scheme was constructed from a SHE scheme ( add & mul for limited number of times ) or in math words limited to evaluating low degree polynomials , limited here means that each ciphertext has some noise S in it and as you add and multiply ciphers the noise makes the end result indecipherable . He introduced bootstrapping which means that the scheme can evaluate it’s own decryption circuit and this property can make the scheme fully homomorphic bootstrapping refreshes the ciphertext by reducing the noise in each operation .

The scheme was considered secure but impractical because the bigger the security parameter the more computationally intensive was to compute the ciphers and their sizes were getting bigger .

Later on , Gentry, Marten van Dijk,Shai Halevi et al released a scheme based on the ideas that Gentry introduced ( bootstrapping ) but this time the scheme used integers instead of ideal lattices . The lattice scheme is incredibly complex , the integer one is simpler to explain especially the bootstrapping part so we will only discuss the latter .

SHE over Integers

Let’s restate that Gentry’s breaktrough was taking a somewhat fully homomorphic scheme and making fully homomorphic using bootstrapping so the scheme we are going to discuss now is somewhat homomorphic and we will use it to explain bootstrapping in more details.

Secret Key Scheme

In cryptography we generally ( I think ) talk about two different ways to do encyption either using a secret key , i.e same key is used to encrypt and decrypto , or public key where on key remains private (private key) used to decrypt and a key is public (public key) used to encrypt .

RSA for example is a public key scheme each user gets two keys let’s take Alice and Bob for a ride :

  • Alice generates two keys PrivK (her private key that only she knows and should keep safe) and a Public Key (she makes it public to anyone )
  • Bob does the same process

  • When Alice wants to send a secret message to Bob she uses Bob’s public ky to encrypt the message , and only Bob can decrypt the message using his Private Key

** You get the point **

Let’s describe the secret-key homomorphic scheme now .

** As we discussed above a scheme needs three algorithms KeyGen, Encrypt, Decrypt :

  • KeyGen : Secret Key means we only need to create one key ; In this scheme the key is an odd integer , choose from some interval [2^n-1,2^n] . Here n is what we call a security parameter .
  • Encrypt(p,m) : m here is a bit {0,1} , to encrypt a bit set the ciphertext as an integer whose residue modulo p has the same parity of the plaintext (m) :
    • c = p*q + 2*r + m
    • c is odd if m = 1 c is even if m = 0 ( Yes 0 is even ).
    • p is the private key we generated before, q and r are just random integers choose from a different interval than the private key one .
  • Decrypt(p,c) :

    • m = (c(mod p)) (mod 2)
    • correctness : (c(mod p)) (mod 2) = (p * q + 2 * r + m (mod p)) (mod 2) = 2r + m (mod 2) = m
  • Example :

    • Suppose p = 19
    • c = 19 * 2 + 1 (q = 2,r = 0)
    • c = 39 | 39 mod 17 = 5 | 5 mod 2 = 1
  • two bit ( + , * ) example :

    • Suppose p = 17 , q1 = 1 , r = 1 , q2 = 2, r2= 2
    • bit 1 = 0
    • bit 2 = 1
    • c1 = p * 1 + 2 * 1 + 0 = 19
    • c2 = p * 2 + 2 * 2 + 0 = 39
    • c1 + c2 = 58 | 58 mod 17 mod 2 = 1
    • c1 * c2 = 741 | 741 mod 17 mod 2 = 0

SCHEME HOMOMORPHISM

Let’s verify the scheme’s homomorphism :

  • We have two cipher texts c1 and c2 :

    • c1 + c2 = (pq1 + 2r1 + m1) + (pq2 + 2r2 + m2)
    • c1 + c2 = p(q1+q2) + 2(r1+r2) + (m1 + m2) = c3
  • Decrypt(p,c3) :

    • m3 = (c1 + c2 (mod p)) mod 2
    • m3 = m1 + m2
    • Because we have pq mod p = 0 and 2r mod 2 = 0 ,hence m3 = m1 + m2
  • Exerice to the reader to verify c1 * c2 ( same steps as before )

Intuitive Application and Code

As you may have noticed the algorithm is designed to encrypt bits {0,1} so you may ask how do I sum 2 numbers ? Well as you may remember we discussed circuits before and here we can see them in action .

Adding binary numbers or just digits is done using an adder . An adder sums two binary digits and outputs their sum and the carry

  • 0 + 1 = 1 and the carry = 0
  • 1 + 1 = 0 and the carry = 1

half_adder

From the gif above we can see that to construct a Half Adder we need a XOR Gate and an AND Gate , the XOR Gate outputs the sum of two bits and the AND Gate outputs the carryout .

There’s also what we call a full adder :

full_adder

A Full Adder can be constructed using two Half Adders and an OR Gate .

Now we have our circuits let’s move on two a practical example :

The following example builds functions to add two 4 Bit numbers from {0000,1111}


import sys
from random import randint

def tobits(val):
    l = [0]*(8)

    l[0]=val & 0x1
    l[1]=(val & 0x2)>>1
    l[2]=(val & 0x4)>>2
    l[3]=(val & 0x8)>>3
    return l

def XOR(a,b):
    return ( (NOT(a)*b) + (a*NOT(b)))

def NOT(val):
    return(val ^ 1)

def AND(a,b):
    return(a*b)

def OR(a,b):
    return(a+b)

def HA(bit1,bit2):
    sum=XOR(bit1,bit2)
    carryout=AND(bit1,bit2)
    return sum,carryout

def FA(bit1,bit2,cin):
    sum1,c1=HA(bit1,bit2)
    sum,c2=HA(sum1,cin)
    carryout=OR(c1,c2)
    return sum,carryout



def encrypt(bit,p):
    #q=randint(50000, 90000)    
    #r=randint(1,200)
    q = 2
    r = 0
    return(  q * p + 2*r +int(bit)),q,r

def decrypt(cipher,p):
    return (cipher % p) % 2

## values to test using same example as before

val1=10
val2=13

v1=[]
v2=[]

v1=tobits(val1)
v2=tobits(val2)

cin=0

#p =randint(3e23, 6e23)*2+1
p = 17
c_carryin,q,r=encrypt(cin,p)

print(v1)
print(v2)

#Cval(i)b(j) means Cipher i Bit j
cval1b0,q,r=encrypt(v1[0],p)
cval2b0,q,r=encrypt(v2[0],p)

cval1b1,q,r=encrypt(v1[1],p)
cval2b1,q,r=encrypt(v2[1],p)

cval1b2,q,r=encrypt(v1[2],p)
cval2b2,q,r=encrypt(v2[2],p)

cval1b3,q,r=encrypt(v1[3],p)
cval2b3,q,r=encrypt(v2[3],p)

"""At this point we have two ciphertext cval1,cval2 to do the sum we use a FA"""


## Addition between two bit arrays 
print("1 ",c_carryin)
c_sum1,c_carryout=FA(cval1b0,cval2b0,c_carryin )
c_sum2,c_carryout=FA(cval1b1,cval2b1,c_carryout )
c_sum3,c_carryout=FA(cval1b2,cval2b2,c_carryout )
c_sum4,c_carryout=FA(cval1b3,cval2b3,c_carryout )



sum1 = decrypt(c_sum1,p)
sum2 = decrypt(c_sum2,p)
sum3 = decrypt(c_sum3,p)
sum4 = decrypt(c_sum4,p)

carry = decrypt(c_carryout,p)


print("Val1:",val1)
print("Val2:",val2)

print("\nResults")

print("encrypted : \n")
print("Csum1 = {}".format(c_sum1))
print("Csum2 = {}".format(c_sum2))
print("c_sum3 = {}".format(c_sum3))
print("c_sum4 = {}".format(c_sum4))
print("carry out = {}".format(carry))
print("Sum:\t\t",carry,sum4,sum3,sum2,sum1)

Conclusion & Notes

  • In this example I tried to keep things as simple and intuitive as possible , the reader should wrap his head around dealing with bits and circuits because that’s what we do here , an exercice to the reader would be to extend the above python code to 8-bit , 16-bit , 32-bit integers it’s quite simple I choose 4 bit numbers because the sum of two 4 bit numbers will give us a 5 bit number this way I can show you how the carry moves around .

I hope this post cleared things a bit more for you , now off you go to explore other unknown places .

Powered by Hugo & Kiss.