Hi, from what I understand. In the case I would like to homomorphically evaluate a bivariate function, tfhe-rs calls a generate_look_up_table function which returns a lookup_table to perform the (bivariate) pbs. That generate_look_up_table function, ultimately uses a fill_acc function (I guess acc stands for accumulator).
Is the fill_acc function purpose to create all the values of the look_up table?
If so, does it do it by computing all values of f(x,y) for (x,y) in [[0,modulus) X [[0,modulus) ?
I guess the size of the lookup table is important for speed consideration.
hello @Norrin_Radix
you have mostly the right idea, but the lookup table can only hold values for inputs in [0, modulus) so for the bivariate inputs we are limited to [0, modulus/2) for both inputs, the idea is mostly simple, for a ciphertext that can contain 2 bits we use 2 bits for the LHS and 2 bits for the RHS (we can multiply one input by 4 in that case and add the other and we get both inputs in the same ciphertext) then we interpret the concatenation of the inputs as a value and store the f(x, y) at this location in the lookup table.
In general lookup generation does not seem to cause much issue in terms of performance for the CPU given the cost of effectively applying it to an input.
Cheers
The concatenation part is a bit fuzzy to me I will think about it.
The idea behind the comment was that the cell size is determined by N/(modulus), where N is the size of the polynomial.
What about symmetrical functions such that f(x,y)=f(y,x)?
In the case of a multiplication for example, f(x,y)= xy = yx = f(y,x), so I was thinking, you might not want to store both f(x,y) and f(y,x).
So a loop for x going from 0 to modulus, then one for y from x to modulus. Maybe it doesn’t make sense, but I thought you could then make a fast pbs to determine which one is greater between x and y, and then apply the pbs to compute f(x,y). The number of values to store goes from n² to n(n+1)/2 . But maybe it’s useless, wouldn’t predetermined LUT dedicated for each operation be faster?
Thanks, have a great week.
I’m not sure I follow, we only store the result for f(x,y) it’s just that x and y are in [0, modulus / 2) and not [0, modulus)
I mean there is a single loop when the accumulator is filled but it parses all values for x and y. So, you store 0*1 and 1*0, 1*2 and 2*1, 1*3 and 3*1, 2*3 and 3*2 etc…
If you only store 0*1, 1*2, 1*3 and if there is a way to determine whether rhs>lhs or lhs>rhs (homomorphically), then you could just first determine which is the biggest between the rhs and the lhs, and after that apply a pbs for f_2(x,y) = x*y ( && x<y ) eventually swapping lhs and rhs in case lhs>rhs.
That function is f(x,y)=x*y but x is in [0,modulus) (or [0,modulus/2) if that’s what you do) and y is in [x,modulus) (or [x,modulus/2)) instead of [0,modulus/2)
If you have less values to store, I guess you can use a smaller polynomials and get the same security, but maybe I’m wrong on that (or create a higher upper bond for x).
In my mind, for clear values, you can easily tell if x>y or x<y by comparing the equality between x&10000… and (x-y)&10000… the subtraction can be done fast because it’s a wrapping one (in case the modulus is a power of 2), so I am not sure it’s costly homomorphically.
I hope it’s more clear.
Edit: escaping character
comparison is generally a non linear operation which should require a PBS, but if you see a way to compute that completely with linear operations then there may be something to do here to improve bivariate PBS in the case of symmetric bivariate functions 
I’m just not sure how it can be handled
I was also thinking about a pbs, but from the test I made, all operations don’t have the same cost. I will look at it.