Less levels after first bootstrapping

FHE Questions
1

Hello there,

I am trying to understand how to optimize the use of bootstrapping and its parameters. After playing with different values, I noticed that after the first bootstrap, the ciphertext levels will always be limited. For instance, I usually find this situation:

  • Fresh ciphertext: 20 available multiplications
  • 1st bootstrap: 8 available multiplications
  • 2nd bootstrap: 8 available multiplications

and so on.
Can you confirm me that this is the “normal” behavior? Is there any way to “close” this gap between the starting 20 and the next 8?

Thank you so much!

2

A few things:

  1. Can you share your script? Just so we can take a look at the parameters?

  2. You’re supposed to bootstrap only in scenarios where it would increase your number of available multiplications :slight_smile:

Just so you’re in the loop, we (OpenFHE team) have talked about this before and I myself have run into this myself.

Can you confirm me that this is the “normal” behavior?

Yes, it is normal, even if it is unexpected for the end-user.

Is there any way to “close” this gap between the starting 20 and the next 8?

Depends on your parameters, hence my asking for your script :slight_smile:

3

Well I noticed this thing in the simple ckks bootstrapping example!

I leave it here for convenience

std::vector<uint32_t> levelBudget = {4, 4};
uint32_t approxBootstrapDepth     = 8;

uint32_t levelsUsedBeforeBootstrap = 10;
usint depth =
            levelsUsedBeforeBootstrap + FHECKKSRNS::GetBootstrapDepth(approxBootstrapDepth, levelBudget, UNIFORM_TERNARY);`

I was wondering what approxBootstrapDepth is, too. I mean, it looks like an arbitrary value, but what is the way-to-go when setting it?

4

Here’s something that will help advanced-ckks-bootstrapping.cpp.

5

Has your Q been answered?

6

Oh, sorry!

I’d say partially; I got that that value is the approximate number of levels bootstrapping will consume. But how would I know that? Is that a function of some other parameters?

Thank you again, @iquah !

7

The approximate bootstrap depth is set experimentally by observing how many levels bootstrapping consumes. The total bootstrap depth is given by this function:

image
image1023×204 11.8 KB

where R, the number of double-angle iterations, is set to 6.

For example, if you use a level budget of {4, 4} with the UNIFORM_TERNARY secret key distribution, and you experimentally observe that bootstrapping consumes 21 levels, then you would set approxBootstrapDepth to 21 - 4 - 4 - (6 - 1) = 8.

1 Like