Difference between sparse/full packing

FHE Questions
1

Hello, I have a question about the types of packing in CKKS.
There are two examples: sparse and full. I got that full packing uses all the slots of the ciphertext, while sparse does not.
My question is: what is the threshold that divides sparse and full packing? I mean, if I have 8 slots and use 7 of them, it is considered a sparse packing? Will it benefit of faster bootstrapping and so on?

1 Like
2

Full packing in (classical) CKKS means the number of slots = N/2, where N is the ring dimension. The actual number of slots is rounded up to the next power of two. So, when the number of slots is N/4+1 or higher (up to N/2), this is considered full packing. All other scenarios, i.e., the number of slots is N/4 or lower, correspond to sparse packing.

3 Likes
3

Thank you so much!
I have another two questions for sparse packing:

  • Does a sparse ciphertext only benefits of a fast bootstrap or in general all operations are faster?

  • Is it possible to go from full packing to sparse packing during the circuit evaluation? For instance, I need all the 8192 slots at the beginning of the algorithm, then, after a while, I just need 2048 of them. Is is possible to change the packing of an existent ciphertext and to take the speed advantage?

Thank you.

4

The biggest benefit of sparse packing is in bootstrapping. But it can be beneficial for other operations, too. For instance, the encoding is faster.

At a high level, the sparse packing works with subrings. If you have a vector with 16 slots, the way this sparse vector is packed in the ciphertext is by cloning the vector as many times as needed to fill all N/2 slots. Yes, you can change the packing on the fly using a combination of masking, rotations, and additions.

1 Like
5

Hi @ypolyakov,

Based on your answer that we can on-the-fly the packing method. Is this the reason we need to utilize the “partial sum” algorithm to get correct ring dimension?

Since if we only need to use 16 slots throughout whole computation, we can pick smaller parameters to fit our need instead of picking large parameters then make it faster.

image
image1275Ă—487 139 KB

Thanks for reading the question and wish you a wonderful day.

6

Yes, it is related to this as we embed a subring in the full ring.

1 Like
7

Got it and thank you!