I’ve been going through the bootstrapping paper and I just can’t seem to understand how they are doing the embedding in part 4.4. Does anyone have insight into what exact function they use to do this? The decoding part is clear as always but I’ve been trying to understand how they do encoding for 10 hours now with no progress. Can anyone explain this to me, or does anyone have any sources explaining it? Thank you.
Here is the part in question:
Can you clarify what is your confusion? The use of the subring?
Please read these posts and see if they help with understanding: Difference between sparse/full packing - #5 by xuann6 and CKKS RNS Sparse encoding.
I’ve taken a look at those links but they seem to only show what is ought to happen, not how that thing happens. What I mean is that I am looking for the exact algorithm that takes a vector from \mathbb{C}^{n/2} and puts it in \mathbb{Z}[x^{N/n}]/(x^N+1). I can’t seem to find this information anywhere.
CKKS encoding and decoding are expressed well in this paper (pp 4 and 5 all you need). You can adapt any FFT datapath to compute the linear transforms described on page (5).
For an implementation of that functionality, you can check CKKS packed-encoding in OpenFHE here.
To add to Caesar’s response, the short story is that you follow the same logic as in full encoding, i.e., IFFT and rounding, but use a smaller transformation corresponding to the smaller number of slots, as described in page 5 of https://eprint.iacr.org/2018/1043.pdf. The extra step you make in the sparse encoding is that you separate the entries obtained from the IFFT by a gap = N/n, which can be seen in the OpenFHE implementation (with FitToNativeVector) mentioned above, and in one of the posts referenced before.
So just to make sure I understand correctly: If I forget about the subring business and encode as usual for the subring \mathbb{Z}[Y]/(Y^n+1) and then do the seperation/viewing as a subring (Y \mapsto X^{N/n}) part I will get the correct result? And I think in the paper I linked they are using the 2l-th (in the notation of the other paper) cyclotomic polynomial are they not? The choice of primitive root confuses me and I can’t see how one would get the decoding mentioned in the original paper, i.e. the one that is just w concatenated N/n times.
Edit: I suppose 2l in the other paper is just n in the original paper.
I have written a quick-and-dirty Python implementation (for reals, without any rounding) to test my understanding. Does it seem correct?
import numpy as np
class SparseEncoder:
def __init__(self, N: int, n: int, scale: int):
self.N = N
self.n = n
self.scale = scale
root = np.exp((1j * np.pi) / self.n)
self.roots_of_unity = [(root)**(5**j) for j in range(0, self.n//2)]
self.fakeroots = [np.exp(2j * np.pi / (2* self.N))**(5**j) for j in range(0, self.N)]
self.vandermonde = np.vander(self.roots_of_unity, self.n, increasing=True)
def decode(self, polynomial):
empty = (self.N) * [0]
for i in range(self.n):
empty[i] = polynomial.coef[(self.N//self.n) * i]
polynomial = np.polynomial.Polynomial(empty)
ev = polynomial(self.roots_of_unity)
scaled_ev = ev / self.scale
return scaled_ev
def encode(self, vector):
scaled = self.scale * np.array(vector)
coefficients = (np.real( np.dot(self.vandermonde.conj().T, scaled) + np.dot(self.vandermonde.T, scaled.conj()) ) * 1/self.n)
empty = (self.N) * [0]
for i in range(self.n):
empty[self.N//self.n * i] = coefficients[i]
return np.polynomial.Polynomial(empty)
For testing I have checked:
s = SparseEncoder(N=8, n=4, scale=64)
p = s.encode([3+4j,2-1j])
print(p)
print(s.decode(p))
assert list(np.rint(s.decode(p))) == [3+4j, 2-1j]
The encoding looks correct, I cannot run the decoding because of internal python error caused by polynomial.
Again, I suggest you look at the OpenFHE implementation and print intermediate values to clarify your understanding.
Well encoding is the hard part so that sounds great! I don’t know much C but the implementation seems to be well commented so I will definitely try to understand it. Thank you!