Score:2

Why AND gate is * on Fully Homomorphic Encryption, BFV scheme?

ru flag

According to Representing a function as FHE circuit, the AND gate for FHE encrypted data is just A*B, in the case that the plaintext has only 0 or 1 coefficients.

Remember that on the BFV FHE scheme, it encrypts polynomials, and we can set the maximum value of the coefficients of the polynomial. So, if we set the max value to 1, then we can do binary gates easily. For example:

  1 + 0x^1 + 1x^2 + 0x^3
+ 0 + 1x^1 + 1x^2 + 0x^3
  ______________________
  1 + 1x^1 + 0x^2 + 0x^3

So + is essentially the OR gate for the polynomials. But I'm strugling to understand * as being the AND, specially because the multiplication of these polynomials are mod x^n +1, where n is the degree of the polynomials. So it's not a simple multiplication.

Why AND = *?

kelalaka avatar
in flag
It really depends on the FHE scheme. If you use constant polynomials, then it will be equal. Who claimed that it is a multiplication? The answer you linked talks about specific ones that are a single bit encrypted.
ru flag
@kelalaka what would be a constant polynomial? And the scheme should be BFV. If not a multiplication, what is it?
cn flag
Multiplying numbers which can only be 0 and 1 results in 1, if all of them are 1. Which sounds awfully like `and`.
ru flag
@CodesInChaos but it needs to be coefficient-wise and on the polynomial, not and for the polynomials itself
Score:0
ru flag

The AND gate represents multiplication in the field of coefficients, which in this case is the binary field of two elements 0 and 1. Similarly for this field addition acts the same as the XOR gate.

If we know how to do addition and multiplication with coefficients, we can extend this to addition and multiplication of polynomials using the properties of arithmetic. In the case of addition, this just involves matching coefficients and adding. In the case of multiplication, we need to use the distributive law. In your example, writing # for XOR and & for AND we have to pair up coefficients whose monomials whose powers add up to the same value

(1 + 0x^1 + 1x^2 + 0x^3)*(0 + 1x^1 + 1x^2 +0 x^3)

= (1&0) + (1&1 # 0&0)x^1 + (1&1 # 0&1 # 1&0)x^2 + (1&0 # 0&1 # 1&1 # 0&0)x^3 +

+ (0&0 # 1&1 # 0&1)x^4 + (1&0 # 0&1)x^5 + (0&0)x^6

= 0 + 1x^1 + 1x^2 + 1x^3 + 1x^4 + 0x^5 + 0x^6

Score:0
ng flag

First, note that BFV is traditionally phrased in terms of arithmetic circuits, not boolean ones. For example, the initial paper has a message space of the form $R_t := \mathbb{Z}_t[x] / (\Phi_n(x))$, where $\Phi_n$ is the $n$th cyclotomic polynomial (when $n$ is a power of two this is simply $x^n+1$). This is relatively important as the fundamental building blocks of arithmetic circuits is not OR and AND, but (the mod $p$ version of) XOR and AND, which is slightly different.

As for your issues with BFV multiplication, I think that you are misreading the specification of BFV slightly. Typically (say in the initial paper) the message space is specified as being $R_t$, which as mentioned before is a polynomial ring (when $n$ is a power of 2) $\bmod x^n+1$. So for our encryption scheme to be fully homomorphic, we need that we can perform the addition and multiplication of the message space on ciphertexts. This multiplication of the message space is $\bmod x^n+1$ (and $\bmod t$, but whatever), as you have pointed out. This is to say that arithmetic being $\bmod x^n+1$ is what is mathematically required for the scheme to be fully homomorphic, so the product being of that form is expected, and not a concern.

Of course, application designers may not want to use this "funny arithmetic". This is something for library designers to solve later though. For example, one way to "fix" this (which is quite naive --- I am guessing there are better solutions) is to only encode messages into the constant terms of polynomials. It should be relatively straightforward to see that this "funny multiplication" becomes standard multiplication when restricted to constant polynomials.

There are other things one could do, for example one could allow polynomials of the form $m(x) = m_0+m_1x$ if you know the multiplicative depth of the circuit you're evaluating is at most $\log_2 n$, or more generally $m(x) = \sum_{i =0}^p m_i x^i$ if the multiplicative depth is at most $\log_{1+p} n$. This is simply because with this depth bound, one cannot produce a polynomial of degree $\geq n$, so the fact that multiplication might "wrap around" doesn't matter. Of course, I'm sure that there are smarter ideas of what one can do to emulate "standard" arithmetic with the "funny" arithmetic one gets, but that is really orthogonal to understanding BFV.


It's also worth mentioning that your comment

but it needs to be coefficient-wise and on the polynomial, not and for the polynomials itself

sounds like you might be looking for the idea of the canonical embedding. Specifically, it was noticed roughly a decade ago that if we want an array-like datatype $[a_0,\dots,a_n]$ that one can perform (slot-wise) arithmetic on, then coefficients of polynomials are really a quite bad choice. This is because (among other things) the natural multiplication operation on polynomials does not lead to multiplication of the underlying coefficients, but convolution of them. In particular, one has that

$$(a_0+a_1x+a_2x^2)(b_0+b_1x+b_2x^2) = a_0b_0+(a_0b_1+b_0a_1)x + (a_0b_2+a_1b_1+a_2b_0)x^2+(a_1b_2+a_2b_1) x^3+a_2b_2x^4$$

In particular, one doesn't recover the product $a_1b_1$. One can fix this by (essentially) appealing to a version of the Fourier transform, as a Fourier transform typically can be written as an isomorphism

$$\mathcal{F} : (R, +,\times)\to (R, +,\ast)$$

e.g. it "swaps" convolution with (coefficinent-wise) multiplication. This is to say that if we instead encode a message in the "canonical embedding" (or equivalently, we encode the "Fourier transform" of the message), then the convolutions will become element-wise multiplication (in our message space).

I don't believe the initial BFV paper does this though, which depending on what you are reading for a specification of BFV may lead to confusion. But I believe its a relatively common optimization, and should be able to be seen as "just" a different message encoding (there are other benefits to using the canonical embedding such that you would want to reanalyze the protocol in terms of it though).

ru flag
can you point me to a paper with information about this canonical embedding on BFV?
Mark avatar
ng flag
@GuerlandoOCs It looks like [this paper](https://eprint.iacr.org/2015/889.pdf) includes analysis of BFV (which they simply call FV) in terms of the canonical embedding, but it is perhaps not as comprehensive as one might hope. BFV is quite similar to BGV, which has much clearer exposition available via Halevi and Shoup's [The Design and Implementation of Helib](https://eprint.iacr.org/2020/1481.pdf), which makes the "SIMD-like" structure quite obvious (including information on more than just how one gets component-wise operations, but how to "swap" data between different "slots")
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.