2
$\begingroup$

I'm reading "Fully Homomorphic Encryption over the Integers"——the first generation of FHE. However, this paper seems to detail a scheme to encrypt each bit in a message. I'm very confused about how to implement homomorphic encryption of the whole k-bits message. More specifically,

if I want to achieve homomorphic addition of ciphertexts, such as encryption(3)+encrpytion(3)=encrpytion(6), just using the one-bit FHE scheme seems insufficient.

My question is there any approach to implement that likes the function of carry bits. Or homomorphic encryption of boolean functions, which is capable of extending one-bit homomorphic arithmetic operations to k-bit homomorphic arithmetic operations.

Any references or answers will be much appreciated!

Improve this question
$\endgroup$
4
  • $\begingroup$ I'm on my phone now so I can't provide more than a simple comment, but these schemes usually support a plaintext space of (in principle) any modulus, not necessarily $2$. Check for example the BGV12 paper (Brakerski, Gentry and Vaikuntanatan) $\endgroup$
    – Daniel
    Dec 1, 2019 at 3:09
  • $\begingroup$ Thanks a lot. I will go to read that paper. I'm curious whether they design that scheme beginning with any modulus, or they lift the scheme on modulo 2 to any modulus via some technicals. If the later, is their method also works for the case of “FHE over the Integers”? Actually, it seems like the paper "FHE on over the Integers" also claim that their scheme works for massage more than 1 bit. However, I can't understand how to keep homomorphic property using the scheme designed for one bit. $\endgroup$
    – louis5544
    Dec 1, 2019 at 3:58
  • $\begingroup$ As far as I remember, the basic LWE/LWR Encryption is general on its own as to allow for larger moduli by default. $\endgroup$
    – Daniel
    Dec 1, 2019 at 11:50
  • $\begingroup$ You might also look at Representing a function as FHE circuit and How to compute the inner product on encrypted vector by using a third party? $\endgroup$
    – kelalaka
    Dec 1, 2019 at 19:22

1 Answer 1

Reset to default
2
$\begingroup$

One-bit FHE schemes, as you call them, are actually sufficient to implement a full adder.

You just have to encrypt each bit of the messages, then use the homomorphic logic gates to execute the circuit that you want.

For instance, if you have 2-bit messages $a = (a_0, a_1)$ and $b = (b_0, b_1)$, just encrypt the four bits, obtaining $c_{a, i}$ and $c_{b, i}$ (for $i = 1, 2$), use the homomorphic logic xor gate to add two bits and logical and gate to obtain the carry, that is, representing XOR by + and AND by $\cdot$, we have

First bit of the result: $r_0 := c_{a,0} + c_{b,0}$ (thus, $r_0 $ encrypts $a_0$ XOR $b_0$)

First carry: $c_0 := c_{a,0} \cdot c_{b,0}$

Then, second bit of the result: $r_1 := c_{a,1} + c_{b,1} + c_0$.

Second carry: $c_1 := (c_{a,1} \cdot c_{b,1}) + (c_{a,1} \cdot c_0) + (c_{b,1} \cdot c_0)$

Third bit of the result: $r_2 := c_1$ (just use the last carry as the most-significant bit)

Therefore, the resulting message is $(r_0, r_1, r_2)$.

You may want to check the TFHE project. They implement several circuits homomorphically (in particular, in the tutorial that link, you can run a circuit that computes the maximum of two values).

Improve this answer
$\endgroup$
5
  • $\begingroup$ Vítor, what about plaintext spaces that are mod $p$ directly? For example, BGV $\endgroup$
    – Daniel
    Dec 1, 2019 at 19:20
  • $\begingroup$ @Daniel To perform only additions and products on $\mathbb{Z}_p$, we can really proceed was you suggested, that is, just represent the messages as elements of $\mathbb{Z}_p$ and encrypt them "as a whole" instead of bit per bit. However, I do not know how we can do more general operations using this representation. For instance, how would we add $c_1$ with $c_2$ then test homomorphically if the resulting ciphertext encrypts a zero? If we have encryptions of each bit $b_i$ of $b$, then we can do NOT($b_0 \lor b_1 \lor ... b_{\ell-1}$), which is one if $b$ is zero and zero if $b \not = 0$... $\endgroup$
    – Hilder Vitor Lima Pereira
    Dec 1, 2019 at 22:22
  • $\begingroup$ I think I get it. So, can I understand that this paper ‘Fully Homomorphic Encryption with k-bit Arithmetic Operations’ (eprint.iacr.org/2019/521.pdf) doesn’t emphasize the realization of k-bit arithmetic, since both homomorphic logic gates and direct K modulo can be used to achieve k-bit arithmetic, but it emphasizes the efficiency of realizing arithmetic operations? $\endgroup$
    – louis5544
    Dec 2, 2019 at 2:55
  • $\begingroup$ I think the emphasis of that paper is on the efficiency of performing bootstrap on ciphertexts that encrypt $k$ bits instead of 1, which seems implies efficiency of general homomorphic operations on $\{0, 1, ..., 2^k-1}$. But I just gave the paper a quick glance. And yes, one can perform additions and multiplications of $k$-bit integers both ways. $\endgroup$
    – Hilder Vitor Lima Pereira
    Dec 2, 2019 at 7:51
  • $\begingroup$ @HilderVítorLimaPereira Thanks. I guess one could proceed as in MPC: bit-decompose the shared/encrypted value and compute on these bits. Not the most efficient but it would surprise me if no one had tried this already. $\endgroup$
    – Daniel
    Dec 2, 2019 at 9:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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