References for LUT implementation

[lilBuffaloEric]

Hi, contributors
I am currently finding ways to evaluate non-poly algorithms with CKKS, and notice that Lattigo 4.0.0 provides a method converting CKKS ciphertext into LWE ones, using LUT to evaluate the non-poly algorithms and repacking them back into CKKS (examples/ckks/advanced/lut/main.go). I want to have a deeper understanding of this LUT-way implementation for non-poly algorithms, would you mind providing me some references(papers)?
BR

[Pro7ech]

Hi @lilBuffaloEric, the implementation in Lattigo of the blind rotation was inspired by this paper , which proposes blind rotations with ternary keys. For the rest, the implementation of LUT evaluation has no reference, as it was designed and optimized on the fly.

If you have questions about specific pieces of code, I can answer them here.

[lilBuffaloEric]

Thanks for your reply!
Now I think what I need to figure out is how to do a homomorphic LUT evaluation in a general way, since you mention that this implementiantion can be done on the fly. I mean I do know how LUT on plaintext works, but when it comes to the ciphertext space, I am still not clear about it, e.g. how to do the index operation homomorphically...

By the way, when I run the examples/ckks/advanced/lut/main.go, it takes about 6min to finish the "Evaluating LUT..." part on my computer. Is the time required for today's common homomorphic LUT evaluation similar to this example? Or is there a solution(paper) that can have a faster performance?

[Pro7ech]

6min seems quite large, the example takes ~30 sec on my home compute.

Evaluating an LUT is to homomorphically decrypt a LWE sample (b, a) where b = -as + m + e at the exponent of the monomial X, i.e. X^{dec(lwe)} = X^{m + e}. This returns the encryption RLWE(X^{m+e}), and you multiply RLWE(X^{m+e}) with the plaintext polynomial that encodes your LUT, moving to it's first coefficient the value that corresponds to the entry m+e. You then extract this first coefficient and generates a new RLWE ciphertext that encrypts this value in it's first coefficient.

The homomorphic computateion of X^{dec(LWE)} is done by computing the dec(lwe) = b + <a, enc(s)> = -as + e + m + sum a_i * enc(s_i) = m + e, where enc(s) = {RGSW(s_0), RGSW(s_1), ... } is the encryption of each coefficient of the key.

So you start with acc = LUT * X^{b} and then iteratively updates acc = acc * ((X^{a} - 1) * Enc(s_i) + 1) for each coefficient of the key. If s_i = 1, then acc is updated to acc = acc * X^{a}, else it stays acc. It's a bit more convoluted for ternary keys, but this is the idea.

acc * ((X^{a} - 1) * RGSW(s_i) + 1) is computed with the external product RLWE(acc) x RGSW((X^{a} - 1) x s_i + 1) = RLWE(acc * X^{a * s_i}).

So the complexity of evaluating an LUT is determined by:

• The ring degree of the input (i.e. the number of RGSW(s_i)), gives the number of external products RLWE x RGSW -> RLWE per LUT. This scales linearly with the log of the input domain (double the log of the input domain, expect to have to double the input ring degree).
• The ring degree and the number of moduli of the output (i.e. the parameters of your LUT) determine the cost of each external product RLWE x RGSW -> RLWE. The ring degree being directly proportional to the output domain of the LUT (double the output domain = double the ring degree), and the number of primes giving the level of the output.

In the example, the ring degree of the input domain is 2^11, and the output domain ring degree is 2^12 with 2 moduli. So for each LUT, you will have to evaluate 2^11 external products in a ring degree of dimension 2^12 with 2 moduli. Note that the complexity of an external product is equivalent to two key switches.

I can achieve around 45ms per LUT with a input ring degree of 2^9 and and output ring degree of 2^10 with 1 prime, but these do not allow you to do much when using CKKS, the input, output domains are too small and precision are too restricted.

From my experience, LUT can be worth considering to compose CKKS is if the output domain is small (for example the sign which is either -1, 0, 1) and if you do not need to evaluate many of them (a handful at most).

Else, if you plan to evaluate a non-linear function on many slots in parallel, it will be more efficient to not use LUT, but directly a high precision/iterative approximation of this function, composed with bootstrapping. You will get a much better precision and amortized time per slot.

[lilBuffaloEric]

Thanks a lot for your reply! It is very helpful. Now I have a deeper understanding how LUTs are performed homomorphicly.

By the way, I ran the example again in a different envrironment and got the same time consumption as yours.