Approximate Modular Reduction during Bootstrapping

FHE Questions
1

Hi everyone, I am trying to understand the approximate modular reduction step during bootstrapping.

I suppose OpenFHE implements the scaled cosine technique by Han & Ki. By assuming K = 512 and r = 3, I tried approximating the scaled cosine using the formula in Table I, here. I tried to print out the coefficients (by adding print statements to EvalChebyshevSeries), but saw a discrepancy between when I manually approximate the scaled cosine versus when I call bootstrapping. Could you help me understand what function the bootstrapping modular reduction approximates?

Here is a small working example. Thank you so much for your help.

#include <iostream>
#include <vector>
#include <chrono>
#include "openfhe.h"

using namespace std;
using namespace lbcrypto;

int main() {
    CCParams<CryptoContextCKKSRNS> parameters;

    int batchsize = 1 << 14;
    parameters.SetSecurityLevel(HEStd_NotSet);
    parameters.SetRingDim(1 << 15);
    parameters.SetBatchSize(batchsize);
    usint scalingModSize = 59;
    parameters.SetScalingModSize(scalingModSize);

    std::vector<uint32_t> levelBudget = {3, 3};
    std::vector<uint32_t> bsgsDim = {16, 16};
    SecretKeyDist secretKeyDist = UNIFORM_TERNARY;

    uint32_t levelsAvailableAfterBootstrap = 7;
    usint depth = levelsAvailableAfterBootstrap + FHECKKSRNS::GetBootstrapDepth(levelBudget, secretKeyDist);
    parameters.SetMultiplicativeDepth(depth);

    CryptoContext<DCRTPoly> cc = GenCryptoContext(parameters);
    cc->Enable(PKE);
    cc->Enable(KEYSWITCH);
    cc->Enable(LEVELEDSHE);
    cc->Enable(ADVANCEDSHE);
    cc->Enable(FHE);

    auto keyPair = cc->KeyGen();
    cc->EvalMultKeyGen(keyPair.secretKey);

    cc->EvalBootstrapSetup({3, 3}, {16, 16}, batchsize);
    cc->EvalBootstrapKeyGen(keyPair.secretKey, batchsize);

    vector<double> input = {1};
    Plaintext plaintext = cc->MakeCKKSPackedPlaintext(input);
    auto ciphertext      = cc->Encrypt(keyPair.publicKey, plaintext);

    // Assuming K = 512 and r = 3
    ciphertext = cc->EvalChebyshevFunction([](double x) -> double { return std::cos((double)M_PI * ((double)x - 0.25) / (double)4.0); }, ciphertext, -64, 64, 89);

    ciphertext = cc->EvalBootstrap(ciphertext);

    return 0;
}

Output:

Chebyshev coefficients: 
0.155704, -0.0308194, 0.161869, ...
Chebyshev coefficients: 
0.154214, -0.003767, 0.160320, ...
2

The approximated function is indeed a scaled cosine, as described in eprint 2020/1203 page 21. But we also have to account for the K factor. So the approximated function is:

x\mapsto \frac{1}{\sqrt[2^r]{2\pi}}\cos\left(\frac{2\pi}{2^r}(Kx-0.25)\right)

In the uniform case, K=512, r=6 and the degree is d=88, so using your modified EvalChebyshevSeries, you shouldn’t see a discrepancy in the coefficients with the following code:

int K = 512;
int r = 6;
double powR = pow(2, r);
ciphertext = cc->EvalChebyshevFunction([powR, K](double x) -> double { return 1/pow((2 * M_PI), 1./powR) * std::cos(2 * M_PI / powR * (K * x - 0.25)); }, ciphertext, -1, 1, 88);
ciphertext = cc->EvalBootstrap(ciphertext);
1 Like