Advanced-ckks-bootstrapping related questions

Library Questions
1

Hi,

My questions are based on the following link,

  1. line 80: Does reducing complexity means increase the space in the context of spacetime continuum. As a result reduce time?

  2. line 105: parameters.SetFirstModSize(firstMod); - What does it corresponds to in the CKKS paper?

  3. How does std::vector<uint32_t> levelBudget = {3, 3}; plays a role in deciding FHECKKSRNS::GetBootstrapDepth(levelBudget, secretKeyDist); – I was taking look at the function definition as follows,

uint32_t FHECKKSRNS::GetBootstrapDepth(uint32_t approxModDepth, const std::vector<uint32_t>& levelBudget,
                                       SecretKeyDist secretKeyDist) {
    if (secretKeyDist == UNIFORM_TERNARY) {
        approxModDepth += R_UNIFORM - 1;
    }

    return approxModDepth + levelBudget[0] + levelBudget[1];
}

uint32_t FHECKKSRNS::GetBootstrapDepth(const std::vector<uint32_t>& levelBudget, SecretKeyDist secretKeyDist) {
    uint32_t approxModDepth = GetModDepthInternal(secretKeyDist);

    return approxModDepth + levelBudget[0] + levelBudget[1];
}

I was wondering, we could have written levelBudget = 6 intead. What is the reason we pass it as a vector and then sum it in the function definition than giving it as a sum beforehand?

Thank you very much.
Bhavin.

2
  1. Yes, it reduces the complexity in number of operations, but increases the memory complexity.
  2. FirstModSize is the size of the lowest level modulus, q_0.
  3. The vector of levelBudget is not only used here, but also when doing precomputations for the homomorphic encoding and decoding, where you need to know how many levels each consumes, not just the sum. For simplicity, instead of passing the sum of the levels for one function and the vector of levels for another function, we pass the vector directly.
1 Like
3

Thank you very much Andreea!