# How does the Efficient Fully Homomorphic Encryption from (Standard) LWE work?

I am interesting to learn the low level implementation of Efficient Fully Homomorphic Encryption from (Standard) LWE and I am wondering if anyone can answer the following questions:

1. Does the BV scheme work on binary numbers (0,1) or not?

2. Does the BV scheme encrypt and decrypt each bit separately?

3. Is there any difference between the original paper of BV andthe updated version in terms of encryption and decryption processes?

• What do you mean by "work on binary numbers" ? Do you want to know if this scheme is able to encrypt and decrypt these numbers? – Hilder Vítor Lima Pereira Sep 28 '15 at 12:25
• I want to know whether is integers converted to binary numbers and then encrypted separately or not! – Abady Sep 28 '15 at 18:51
• The scheme is described regarding only encryption, decryption and operations over the bits 1 and 0. Anyone that wants to use it to work over integers have to find his or her own way to do so (which is typically by encrypting each bit). – Hilder Vítor Lima Pereira Sep 29 '15 at 13:12
• BGV is definitely better than BV. A good paper for BGV-beginners is the updated version of the paper "Homomorphic Evaluation of the AES Circuit" by Gentry, Halevi, Smart from the iacr e-print server (see ia.cr/2012/099 - the outdated appendix C should be replaced by ia.cr/2015/889). – j.p. Sep 29 '15 at 13:52

## 1 Answer

The BV scheme presented in the article works for plaintext messages in $GF(2)$ (that is $m$ $\in$ $\{0,1\}$) but can be extended to support encrypting messages that are in $GF(t)$ where $t$ is prime with the modulus $Z_q$.

This means that if you want to encrypt a message in $\{0,1\}^n$ you have to do it for each bit separately in $GF(2)$ (or in $GF(t)$ and the message $m$ $\in \{0,1,...t-1\}^n$)

The BGV scheme instantiated with the LWE problem is the same as in BV. The main difference in BGV is that the scheme supports a more general context, namely it could be also instantiated with the Ring-LWE problem providing a more efficient circuit (inner operations are done inside a ring $R$ instead from $Z_q$ as in LWE).

• Now, it is clear that I can use Binary representation for encrypted data which means that I can encrypt and decrypt bit by bit. While I am going though the code of BVG, I could not find the functions that convert the integer to binary representation of each bit. The encrypt data is represented as a matrix that all what I got. However, I do not know how many bits are represented in each matrix. It might seems silly question for some of you! Looking for your help guys :-) – Abady Oct 1 '15 at 18:58
• Maybe there is some Chinese Remainder Theorem happening there. Could you point to me where is the BGV code you are going through? – Dragos Oct 2 '15 at 6:47
• This is a part of BV "Encryption. The algorithm c←HE.Encpk(μ) takes the public key pk and a single bit message μ ∈ {0, 1} and outputs a ciphertext c". Does this mean BV and BVG are using a stream cipher which encrypt each bit separately? – Abady Oct 9 '15 at 3:04
• No. The HE scheme is just a general definition of what a homomorphic scheme should do. In the BV article the authors show their construction (SHE) and how the ciphertext is computed by using linear algebra and not a stream cipher. For more details see the section 4.1. – Dragos Oct 9 '15 at 7:46
• In section 4.1 is mentioned that" Encryption SH.Encpk(μ): Recall that pk = (A,b). To encrypt a message μ ∈ GF(2), sample a vector r ←\$ {0, 1}m and set (just like in Regev’s scheme) v:=ATr (mod q) and w:=bTr+μ (mod q) . The output ciphertext contains the pair (v, w),". Does this mean each integer converted to binary representation and then encrypt each {0 or 1} as a single value or encrypt the integer in different scenario? I concluded this scenario from this line "To encrypt a message μ ∈ GF(2)". – Abady Oct 11 '15 at 10:31