2
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ 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? $\endgroup$
    – Hilder Vitor Lima Pereira
    Sep 28, 2015 at 12:25
  • $\begingroup$ I want to know whether is integers converted to binary numbers and then encrypted separately or not! $\endgroup$
    – Abady
    Sep 28, 2015 at 18:51
  • 1
    $\begingroup$ 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). $\endgroup$
    – Hilder Vitor Lima Pereira
    Sep 29, 2015 at 13:12
  • $\begingroup$ 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). $\endgroup$
    – j.p.
    Sep 29, 2015 at 13:52

1 Answer 1

Reset to default
3
$\begingroup$

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).

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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 :-) $\endgroup$
    – Abady
    Oct 1, 2015 at 18:58
  • 1
    $\begingroup$ Maybe there is some Chinese Remainder Theorem happening there. Could you point to me where is the BGV code you are going through? $\endgroup$
    – Dragos
    Oct 2, 2015 at 6:47
  • $\begingroup$ 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? $\endgroup$
    – Abady
    Oct 9, 2015 at 3:04
  • $\begingroup$ 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. $\endgroup$
    – Dragos
    Oct 9, 2015 at 7:46
  • $\begingroup$ 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)". $\endgroup$
    – Abady
    Oct 11, 2015 at 10:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.