Brakerski-Fan-Vercauteren (BFV) Homomorphic Encryption

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 simple (as the reduction proof comes from lattice based cryptography, we need to skip the proof. The reduction of LWE is done with the help of shortest vector problem (SVP)). 

By skipping some mathematical proof. Let us come to the encryption and decryption. 

In BFV encryption of message (m) is always encrypted with noise v. Thus,

ct(s) = Δm + v (mod q)

Here Δ= ⌊q/t」, where m \in Rt (where t is plaintext modulus, q is ciphertext modulus (q >t)), and v is noise. 

Note that BFV is scale invariant scheme. Thus message is always store in the MSB whereas error is store at LSB (as shown in Figure 1).

Figure 1: BFV Ciphertext
If you want to perform decryption then
m' = 「t/q (ct(s))」

Here we should note that for correct decryption 
|v| < Q/2t - 1/2

Evaluation example: 
Let us perform addition. 
Given (m1,v1), and (m2,v2)
Thus, c1+c2 = Δ(m1+m2) + (v1+v2)
Decryption m' = 「t/q (Δ(m1+m2) + (v1+v2))」= (m1+m2) + t/q(v1+v2)
Thus we know q>t and v1,v2 are also small so t/q(v1+v2) -> 0
Hence, m' = m1+m2 (Yes, this exactly we want ✊)
Below Figure shows the evaluation process of scale invariant scheme.
Figure 2: BFV homomorphic evaluation 

Key Facts:
1. It is assumed that BFV and BGV are essentially the same, except for the distribution of values. In the case of BGV, the message is stored in the LSB, while the noise is stored in the MSB.
2. To date, it is not entirely clear when to use BGV and when to use BFV, as both have similar bootstrapping mechanisms. Some researchers believe that noise growth in BFV is somewhat better than in BGV, especially with large plaintext moduli.

%3CmxGraphModel%3E%3Croot%3E%3CmxCell%20id%3D%220%22%2F%3E%3CmxCell%20id%3D%221%22%20parent%3D%220%22%2F%3E%3CmxCell%20id%3D%222%22%20value%3D%22%22%20style%3D%22shape%3Dtable%3BstartSize%3D0%3Bcontainer%3D1%3Bcollapsible%3D0%3BchildLayout%3DtableLayout%3B%22%20vertex%3D%221%22%20parent%3D%221%22%3E%3CmxGeometry%20x%3D%22200%22%20y%3D%22120%22%20width%3D%22270%22%20height%3D%2240%22%20as%3D%22geometry%22%2F%3E%3C%2FmxCell%3E%3CmxCell%20id%3D%223%22%20value%3D%22%22%20style%3D%22shape%3DtableRow%3Bhorizontal%3D0%3BstartSize%3D0%3BswimlaneHead%3D0%3BswimlaneBody%3D0%3BstrokeColor%3Dinherit%3Btop%3D0%3Bleft%3D0%3Bbottom%3D0%3Bright%3D0%3Bcollapsible%3D0%3BdropTarget%3D0%3BfillColor%3Dnone%3Bpoints%3D%5B%5B0%2C0.5%5D%2C%5B1%2C0.5%5D%5D%3BportConstraint%3Deastwest%3B%22%20vertex%3D%221%22%20parent%3D%222%22%3E%3CmxGeometry%20width%3D%22270%22%20height%3D%2240%22%20as%3D%22geometry%22%2F%3E%3C%2FmxCell%3E%3CmxCell%20id%3D%224%22%20value%3D%22%26lt%3Bfont%20style%3D%26quot%3Bfont-size%3A%2015px%3B%26quot%3B%26gt%3Bm%26lt%3B%2Ffont%26gt%3B%22%20style%3D%22shape%3DpartialRectangle%3Bhtml%3D1%3BwhiteSpace%3Dwrap%3Bconnectable%3D0%3BstrokeColor%3D%2382b366%3Boverflow%3Dhidden%3BfillColor%3D%23d5e8d4%3Btop%3D0%3Bleft%3D0%3Bbottom%3D0%3Bright%3D0%3BpointerEvents%3D1%3B%22%20vertex%3D%221%22%20parent%3D%223%22%3E%3CmxGeometry%20width%3D%22220%22%20height%3D%2240%22%20as%3D%22geometry%22%3E%3CmxRectangle%20width%3D%22220%22%20height%3D%2240%22%20as%3D%22alternateBounds%22%2F%3E%3C%2FmxGeometry%3E%3C%2FmxCell%3E%3CmxCell%20id%3D%225%22%20value%3D%22%26lt%3Bfont%20style%3D%26quot%3Bfont-size%3A%2015px%3B%26quot%3B%26gt%3Bv%26lt%3B%2Ffont%26gt%3B%22%20style%3D%22shape%3DpartialRectangle%3Bhtml%3D1%3BwhiteSpace%3Dwrap%3Bconnectable%3D0%3BstrokeColor%3D%23b85450%3Boverflow%3Dhidden%3BfillColor%3D%23f8cecc%3Btop%3D0%3Bleft%3D0%3Bbottom%3D0%3Bright%3D0%3BpointerEvents%3D1%3B%22%20vertex%3D%221%22%20parent%3D%223%22%3E%3CmxGeometry%20x%3D%22220%22%20width%3D%2250%22%20height%3D%2240%22%20as%3D%22geometry%22%3E%3CmxRectangle%20width%3D%2250%22%20height%3D%2240%22%20as%3D%22alternateBounds%22%2F%3E%3C%2FmxGeometry%3E%3C%2FmxCell%3E%3C%2Froot%3E%3C%2FmxGraphModel%3E

%3CmxGraphModel%3E%3Croot%3E%3CmxCell%20id%3D%220%22%2F%3E%3CmxCell%20id%3D%221%22%20parent%3D%220%22%2F%3E%3CmxCell%20id%3D%222%22%20value%3D%22%22%20style%3D%22shape%3Dtable%3BstartSize%3D0%3Bcontainer%3D1%3Bcollapsible%3D0%3BchildLayout%3DtableLayout%3B%22%20vertex%3D%221%22%20parent%3D%221%22%3E%3CmxGeometry%20x%3D%22200%22%20y%3D%22120%22%20width%3D%22270%22%20height%3D%2240%22%20as%3D%22geometry%22%2F%3E%3C%2FmxCell%3E%3CmxCell%20id%3D%223%22%20value%3D%22%22%20style%3D%22shape%3DtableRow%3Bhorizontal%3D0%3BstartSize%3D0%3BswimlaneHead%3D0%3BswimlaneBody%3D0%3BstrokeColor%3Dinherit%3Btop%3D0%3Bleft%3D0%3Bbottom%3D0%3Bright%3D0%3Bcollapsible%3D0%3BdropTarget%3D0%3BfillColor%3Dnone%3Bpoints%3D%5B%5B0%2C0.5%5D%2C%5B1%2C0.5%5D%5D%3BportConstraint%3Deastwest%3B%22%20vertex%3D%221%22%20parent%3D%222%22%3E%3CmxGeometry%20width%3D%22270%22%20height%3D%2240%22%20as%3D%22geometry%22%2F%3E%3C%2FmxCell%3E%3CmxCell%20id%3D%224%22%20value%3D%22%26lt%3Bfont%20style%3D%26quot%3Bfont-size%3A%2015px%3B%26quot%3B%26gt%3Bm%26lt%3B%2Ffont%26gt%3B%22%20style%3D%22shape%3DpartialRectangle%3Bhtml%3D1%3BwhiteSpace%3Dwrap%3Bconnectable%3D0%3BstrokeColor%3D%2382b366%3Boverflow%3Dhidden%3BfillColor%3D%23d5e8d4%3Btop%3D0%3Bleft%3D0%3Bbottom%3D0%3Bright%3D0%3BpointerEvents%3D1%3B%22%20vertex%3D%221%22%20parent%3D%223%22%3E%3CmxGeometry%20width%3D%22220%22%20height%3D%2240%22%20as%3D%22geometry%22%3E%3CmxRectangle%20width%3D%22220%22%20height%3D%2240%22%20as%3D%22alternateBounds%22%2F%3E%3C%2FmxGeometry%3E%3C%2FmxCell%3E%3CmxCell%20id%3D%225%22%20value%3D%22%26lt%3Bfont%20style%3D%26quot%3Bfont-size%3A%2015px%3B%26quot%3B%26gt%3Bv%26lt%3B%2Ffont%26gt%3B%22%20style%3D%22shape%3DpartialRectangle%3Bhtml%3D1%3BwhiteSpace%3Dwrap%3Bconnectable%3D0%3BstrokeColor%3D%23b85450%3Boverflow%3Dhidden%3BfillColor%3D%23f8cecc%3Btop%3D0%3Bleft%3D0%3Bbottom%3D0%3Bright%3D0%3BpointerEvents%3D1%3B%22%20vertex%3D%221%22%20parent%3D%223%22%3E%3CmxGeometry%20x%3D%22220%22%20width%3D%2250%22%20height%3D%2240%22%20as%3D%22geometry%22%3E%3CmxRectangle%20width%3D%2250%22%20height%3D%2240%22%20as%3D%22alternateBounds%22%2F%3E%3C%2FmxGeometry%3E%3C%2FmxCell%3E%3C%2Froot%3E%3C%2FmxGraphMode

Comments

Post a Comment

Popular posts from this blog

Homomorphic Encryption: A Basic Idea

Image
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 in...
Read more

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