Homomorphic Encryption: A Basic Idea

Homomorphic encryption has the same aim as other encryption-decryption mechanisms: maintaining confidentiality, security, privacy, etc. 
In this blog, we will see homomorphic encryption and its type. 

Homomorphic Encryption (HE): 

It is an encryption that computes operations over encrypted data without decrypting it (or without the need for a secret key). 

Mathematically speaking in a client-server architecture: client has message 'm' and function f. The task of client is to compute f(m). Due to computational expensiveness (maybe one of the reason) client sends encryption of message (say Enc(m)) and 'f' to the server. Server will compute function over encrypted message, that is, f(Enc(m)), and return the result to the client, that is, Enc(f(m)). Client will decrypt it Dec(Enc(f(m)), that is, f(m). Hence, client achieves f(m). 

Let's understand HE with our daily life (Tea making process):
Figure 1. Here m is message, Enc is encryption, f is function, and Eval indicates evaluation of function over encrypted data.

In India, the morning of mostly home starts with Tea. Hey!! There we are using homomorphic encryption 😓.
We have a cup of milk, which we pour into a pot. After that, we add tea leaves to the pot and place it on the burner. The burner gradually heats the pot with its flame, brewing the tea. Once the tea is ready, we remove the pot from the burner and pour its contents into the cup. Finally, our tea is ready to drink.
😂😂😂 Here, we see that all the things are done by the burner. 

Types of Homomorphic Encryption:

In my understanding, there are various types of HE. Here, we discuss the most commonly known types. HE was introduced by Rivest et al. in 1978 where we are applying operations (say addition and multiplication which are basic mathematics operations) over encrypted data having certain restrictions. 

1. Partial Homomorphic Encryption (PHE): We can only apply one HE operation either addition or multiplication but not both.

2. Somewhat Homomorphic Encryption (SHE): We can only apply a limited number of operations and support both additions as well as multiplication. 

3. Fully Homomorphic Encryption (FHE): It is a way to apply infinite number of operations. 

Why we are defining these types:
In HE based schemes we encrypt the message with some random noise and when we apply any operation over encrypted message then the level of noise increases. Unluckily, after a certain threshold, we cannot apply more operations over encrypted data because the noise crosses the threshold level which leads to incorrect decryption failure. 😭
Thus, when in 1978, Rivest et al. introduced the HE then it came up with some restrictions mainly we cannot achieve fully homomorphic encryption (an open problem those days). 

Figure 2: In 2009, C. Gentry (PhD student of Dan Boneh) solved the FHE problem by introducing the concept of Bootstrapping having restrictions that it is not practically implemented. 

Generations of FHE:

In my understanding, we divide the FHE into three generations. 

1. First Generation: In this generation, we reserve BGV/BFV schemes that deal with integer arithmetic. 

2. Second Generation: In this generation, we reserve CKKS scheme which deals with approximate data (real as well as complex).

3. Third Generation: In this generation, we reserve TFHE scheme which deals with Boolean circuits and programmable logic. 

Understanding the mathematics behind evaluation of function:

Sometime people may confuse f(Enc(m)) = Enc(f(m)). Let us understand this thing with some mathematics.
Client has 'a' and 'b' the task is to compute a+b.
First client will encrypt a and b as follows: c1 = (Q/t)a + e1 (mod Q), c2 = (Q/t)b + e2 (mod Q) (where (Q/t) is scaling factor (you can think Q as ciphertext modulus, and t as plaintext modulus (where Q>>t), e1, e2 are small random noise)).
Client will send c1 and c2 to server. Server applies c1+c2 (say C), that is, C = (Q/t)(a+b) + (e1 + e2) (mod Q). 
Server sends C to the client. Client will decrypt it such as (t/Q)C, that is, (a+b) + t/Q(e1+e2).
In a normal setting t/Q(e1+r2) approaches 0 (as Q>>t and e1 and e2 are also small). Thus, client achieves a+b.  


Comments

Post a Comment

Popular posts from this blog

Fast Base Conversion and Its Application

Image
Fast Base Conversion (FBC) is a technique used to convert a number from one modulus space to another. For example, if we have 14 m o d     77 14 \mod 77  and want to convert it to x m o d     390 x \mod 390 , FBC is widely used. Mathematically, it can be represented as follows: Here, the above equation represents an integer x x  in modulus q q , and FBC converts this integer into the modulus space t t . The modulus q q  is the product of small coprime moduli (i.e., q = q 1 q 2 … q k q = q_1 q_2 \dots q_k ​ ), and x x  is an integer such that x ∈ [ 0 , q ) x \in [0, q) . We also note that q q  and t t  are coprime numbers. Here, we remark that it is not necessary for the above equation to produce the exact result for x x . Instead of x m o d     t x \mod t , it will provide x ′ m o d     t x' \mod t . Thus, the output of the above equation is as follows: FBC ( x , q , t )  =  x  +  A q  mod  t , where A ∈ [ 0 , k − 1 ] A \in [0,...
Read more

Brakerski-Fan-Vercauteren (BFV) Homomorphic Encryption

Image
Homomorphic encryption means computation over encrypted data without secret key.  How this is possible  ?? 😴 In this blog, we will explore the types of Homomorphic Encryption and demonstrate how computations can be performed on encrypted data without the secret key. In 2009, Gentry proposed Fully Homomorphic Encryption. In 2012, Brakerski proposed a leveled homomorphic encryption scheme that works over integer arithmetic, which later became known as the BFV scheme. BFV is an encryption scheme. Thus, as an encryption scheme, it is expected to be secure. To date, under certain conditions, it is assumed that the scheme is safe, and its security is based on the Learning With Errors (LWE) assumption.. Learning-with-error (LWE): Given a pair of a, b and the task is to recover secret key (s), such that b = a.s  + e  Here e is error mostly picked from gaussian distribution, and a, s are selected from Rq (known as ring module R) The above problem is HARD. The proof is not si...
Read more