Question about general FBT

Library Questions
1

Hi, all

In the functional-bootstrapping-ckks, the ArbitraryLUT example begins with a BFV ciphertext, and use `SchemeletRLWEMP::convert` to convert ciphertext type into CKKS, then perform FBT on the CKKS ciphertext.

I’m trying to perform levelled computation on the CKKS (mult and rot) before and after FBT. I can perform levelled computation after FBT through an FBT w/o EvalHomDecoding and bit reverse. However, I’m still in trouble with the levelled computation before FBT, because I can’t find a method to transform the slot encoding to the coefficient encoding. Is there any function in OpenFHE that can do this, or can you provide a procedure to achieve levelled computation before FBT?

Thanks!

How to use MultiPrecisionSignCipher？
2

The RLWE->CKKS->RLWE hybrid scheme was designed to function similarly to FHEW/TFHE, i.e., every non-linear operation is embedded in the functional bootstrapping.

The simplest way (in terms of available implementation) that you can achieve what you want is to start with an FBT for the identity function, and then perform the leveled operations you want, followed by the subsequent FBT.

You can also start with a slot CKKS ciphertext (but you need to find the correct scaling and start at the minimum number of levels), perform the leveled computations, and then run the slots-to-coefficient transformation, corresponding to homomorphic decoding, and do the rounding to get to RLWE. This is possible but hasn’t been tested in the current implementation.

3

Thank you for your detailed explanation! I tried the first solution you mentioned, which starts with a Functional Bootstrapping (FBT) for the identity function. However, I encountered another issue: after applying the identity function (using EvalFBTNoDecoding), the ciphertext can be decrypted correctly. But when I perform multiplication, the results fall into two categories:

  1. If I multiply the ciphertext by a fresh CKKS ciphertext, the decryption result is correct.
  2. If I square the result obtained from the identity function (using EvalFBTNoDecoding), the decryption results are all 0.

I suspect this might be related to the scaling factor of the ciphertext after the identity function. Could you provide some insights into why this happens and how to resolve it? Specifically, I’m wondering if the scaling factor is being modified or lost during the identity function process, leading to incorrect results during subsequent operations.

Here is my code for the square after FBT, and the result are all 0.

image
image1532×871 168 KB

But if I use the following code, the multiplication result is correct.

image
image1381×849 154 KB

4

Yes, you have to keep track of the scaling of the message in CKKS. Try cc->EvalHomDecoding(cmul, scaleTHI*scaleTHI, 0).

By the way, in the second image, you are not using c_1, but still computing the square. I assume this didn’t work either. For future, please give copyable code as a minimum running example instead of a screenshot.

5

Thank you very much for your prompt reply! I have tried cc->EvalHomDecoding(cmul, scaleTHI*scaleTHI, 0), but the result still seems incorrect. Here is my code.

int main() {
    FBTtest(QBFVINIT, BigInteger(256), BigInteger(16), (BigInteger(1) << 47), (BigInteger(1) << 47), 32, 1, 8, 4096);

    return 0;
}

void FBTtest(BigInteger QBFVInit, BigInteger PInput, BigInteger POutput, BigInteger Q, BigInteger Bigq,
             uint32_t scaleTHI, size_t order, uint32_t numSlots, uint32_t ringDim) {
    auto numSlotsCKKS      = ringDim / 2;
    std::vector<int64_t> x = {1, 2, 3, 4, 5, 6, 7, 8};
    std::cerr << "First 8 elements of the input x :" << std::endl;
    std::cerr << x << std::endl;

    std::vector<int64_t> y = {1, 3, 1, 3, 1, 3, 1, 3};
    std::cerr << "First 8 elements of the input y :" << std::endl;
    std::cerr << y << std::endl;
 
    std::vector<std::complex<double>>  coeffcompidentity;

    auto funcidentity = [](int64_t x) -> int64_t {
        return x;
    };
    coeffcompidentity = GetHermiteTrigCoefficients(funcidentity, PInput.ConvertToInt(), order,
                                                   scaleTHI);  // divided by 2

    uint32_t dcrtBits                       = Bigq.GetMSB() - 1;
    uint32_t firstMod                       = Bigq.GetMSB() - 1;
    uint32_t levelsAvailableAfterBootstrap  = 0;
    uint32_t levelsAvailableBeforeBootstrap = 0;
    uint32_t dnum                           = 3;
    SecretKeyDist secretKeyDist             = SPARSE_ENCAPSULATED;
    std::vector<uint32_t> lvlb              = {3, 3};
    auto levelsComputation                  = 1;
    CCParams<CryptoContextCKKSRNS> parameters;
    parameters.SetSecretKeyDist(secretKeyDist);
    parameters.SetSecurityLevel(HEStd_NotSet);
    parameters.SetScalingModSize(dcrtBits);
    parameters.SetScalingTechnique(FIXEDMANUAL);
    parameters.SetFirstModSize(firstMod);
    parameters.SetNumLargeDigits(dnum);
    parameters.SetRingDim(ringDim);
    parameters.SetBatchSize(numSlotsCKKS);
    uint32_t depth = levelsAvailableAfterBootstrap + lvlb[0] + lvlb[1] + 2 + levelsComputation;
    bool flagBR    = true;

    depth += FHECKKSRNS::AdjustDepthFBT(coeffcompidentity, PInput, order, secretKeyDist);

    parameters.SetMultiplicativeDepth(depth);

    auto cc = GenCryptoContext(parameters);
    cc->Enable(PKE);
    cc->Enable(KEYSWITCH);
    cc->Enable(LEVELEDSHE);
    cc->Enable(ADVANCEDSHE);
    cc->Enable(FHE);

    std::cout << "CKKS scheme is using ring dimension " << cc->GetRingDimension() << " and a multiplicative depth of "
              << depth << std::endl
              << std::endl;

    auto keyPair = cc->KeyGen();
    auto ep      = SchemeletRLWEMP::GetElementParams(keyPair.secretKey, depth - (levelsAvailableBeforeBootstrap > 0));

    auto cx_bfv = SchemeletRLWEMP::EncryptCoeff(x, QBFVInit, PInput, keyPair.secretKey, ep, flagBR);
    auto cy_bfv = SchemeletRLWEMP::EncryptCoeff(y, QBFVInit, PInput, keyPair.secretKey, ep, flagBR);
    cc->EvalFBTSetup(coeffcompidentity, numSlotsCKKS, PInput, POutput, Bigq, keyPair.publicKey, {0, 0}, lvlb,
                     levelsAvailableAfterBootstrap, levelsComputation, order);
    cc->EvalBootstrapKeyGen(keyPair.secretKey, numSlotsCKKS);
    cc->EvalMultKeyGen(keyPair.secretKey);
    SchemeletRLWEMP::ModSwitch(cx_bfv, Q, QBFVInit);
    SchemeletRLWEMP::ModSwitch(cy_bfv, Q, QBFVInit);
    auto cx    = SchemeletRLWEMP::convert(*cc, cx_bfv, keyPair.publicKey, Bigq, numSlotsCKKS,
                                          depth - (levelsAvailableBeforeBootstrap > 0));
    auto cy    = SchemeletRLWEMP::convert(*cc, cy_bfv, keyPair.publicKey, Bigq, numSlotsCKKS,
                                          depth - (levelsAvailableBeforeBootstrap > 0));
    auto c_sub = cc->EvalSub(cx, cy);
    Ciphertext<DCRTPoly> ctxtAfterFBT_id;
    ctxtAfterFBT_id = cc->EvalFBTNoDecoding(c_sub, coeffcompidentity, PInput.GetMSB() - 1, ep->GetModulus(), order);

    auto csquare = cc->EvalSquare(ctxtAfterFBT_id);
    cc->ModReduceInPlace(csquare);
    auto csquare_decode = cc->EvalHomDecoding(csquare, scaleTHI * scaleTHI, 0);
    auto polys          = SchemeletRLWEMP::convert(csquare_decode, Q);
    auto computed =
        SchemeletRLWEMP::DecryptCoeff(polys, Q, POutput, keyPair.secretKey, ep, numSlotsCKKS, numSlotsCKKS, flagBR);
    std::cerr << "FBT square decode result: [";
    std::copy_n(computed.begin(), 8, std::ostream_iterator<int64_t>(std::cerr, " "));
    std::cerr << "]" << std::endl;
}

I want to compute (x-y)^2, where x = [ 1, 2, 3, 4, 5, 6, 7, 8] and y = [1, 3, 1, 3, 1, 3, 1, 3], but the decryption result is randomly [0 1 0 0 0 0 0 0 ], [0 -1 0 0 0 0 0 0 ] or [0 0 0 0 0 0 0 0 ]. Could you provide some insights about this problem?

6

The issue in your code was the way you set the number of slots in CKKS; it has to match the number of slots in BFV auto numSlotsCKKS = numSlots;.

Also, note that you set POutput = 16, so the output will be in this range. Moreover, when you do intermediate computations in CKKS, you might need to set larger scaling factor, so if you don’t see correct results, increase Q and Bigq, to e.g., 2^{50} instead of 2^{47}.

1 Like
7

Thank you for your detailed explanation! Based on your guidance, I can now perform leveled computations after the FBT. However, I encountered an issue when attempting to execute multiple FBTs sequentially with different functions.
In the following code, I first perform an identity function through FBT, followed by a leveled multiplication. Then, I adjust the modulus and perform a mod function through another FBT. However, I encountered an error when calling EvalHomDecoding after these operations. Specifically, the error occurs during the homomorphic decoding step, likely due to inconsistencies in the EvalFBTSetup phase (different functions) or modulus adjustments between the FBT operations. Could you please provide guidance on how to execute multiple FBTs sequentially with different functions?
Here is my code:

int main() {
    FBTtest(QBFVINIT, BigInteger(256), BigInteger(16), (BigInteger(1) << 47), (BigInteger(1) << 47), 32, 1, 8, 4096);

    return 0;
}

void FBTtest(BigInteger QBFVInit, BigInteger PInput, BigInteger POutput, BigInteger Q, BigInteger Bigq,
             uint32_t scaleTHI, size_t order, uint32_t numSlots, uint32_t ringDim) {
    auto numSlotsCKKS      = numSlots;
    std::vector<int64_t> x = {1, 2, 3, 4, 5, 6, 7, 8};
    std::cerr << "First 8 elements of the input x :" << std::endl;
    std::cerr << x << std::endl;

    std::vector<int64_t> y = {1, 3, 1, 3, 1, 3, 1, 3};
    std::cerr << "First 8 elements of the input y :" << std::endl;
    std::cerr << y << std::endl;

    std::vector<std::complex<double>> coeffcompidentity, coeffmod;

    auto funcidentity = [](int64_t x) -> int64_t {
        return x;
    };

    auto funcmod = [](int64_t x) -> int64_t {
        return x % 16;
    };
    coeffcompidentity = GetHermiteTrigCoefficients(funcidentity, PInput.ConvertToInt(), order,
                                                   scaleTHI);  // divided by 2
    coeffmod          = GetHermiteTrigCoefficients(funcmod, PInput.ConvertToInt(), order, scaleTHI);
    uint32_t dcrtBits = Bigq.GetMSB() - 1;
    uint32_t firstMod = Bigq.GetMSB() - 1;
    uint32_t levelsAvailableAfterBootstrap  = 0;
    uint32_t levelsAvailableBeforeBootstrap = 0;
    uint32_t dnum                           = 3;
    SecretKeyDist secretKeyDist             = SPARSE_ENCAPSULATED;
    std::vector<uint32_t> lvlb              = {3, 3};
    auto levelsComputation                  = 1;
    CCParams<CryptoContextCKKSRNS> parameters;
    parameters.SetSecretKeyDist(secretKeyDist);
    parameters.SetSecurityLevel(HEStd_NotSet);
    parameters.SetScalingModSize(dcrtBits);
    parameters.SetScalingTechnique(FIXEDMANUAL);
    parameters.SetFirstModSize(firstMod);
    parameters.SetNumLargeDigits(dnum);
    parameters.SetRingDim(ringDim);
    parameters.SetBatchSize(numSlotsCKKS);
    uint32_t depth = levelsAvailableAfterBootstrap + lvlb[0] + lvlb[1] + 2 + levelsComputation;
    bool flagBR    = true;

    depth += FHECKKSRNS::AdjustDepthFBT(coeffcompidentity, PInput, order, secretKeyDist);

    parameters.SetMultiplicativeDepth(depth);

    auto cc = GenCryptoContext(parameters);
    cc->Enable(PKE);
    cc->Enable(KEYSWITCH);
    cc->Enable(LEVELEDSHE);
    cc->Enable(ADVANCEDSHE);
    cc->Enable(FHE);

    std::cout << "CKKS scheme is using ring dimension " << cc->GetRingDimension() << " and a multiplicative depth of "
              << depth << std::endl
              << std::endl;

    auto keyPair = cc->KeyGen();
    cc->EvalFBTSetup(coeffcompidentity, numSlotsCKKS, PInput, POutput, Bigq, keyPair.publicKey, {0, 0}, lvlb,
                     levelsAvailableAfterBootstrap, levelsComputation, order);
    cc->EvalBootstrapKeyGen(keyPair.secretKey, numSlotsCKKS);
    cc->EvalMultKeyGen(keyPair.secretKey);
    auto ep = SchemeletRLWEMP::GetElementParams(keyPair.secretKey, depth - (levelsAvailableBeforeBootstrap > 0));

    auto cx_bfv = SchemeletRLWEMP::EncryptCoeff(x, QBFVInit, PInput, keyPair.secretKey, ep, flagBR);
    auto cy_bfv = SchemeletRLWEMP::EncryptCoeff(y, QBFVInit, PInput, keyPair.secretKey, ep, flagBR);

    Ciphertext<DCRTPoly> ctxtAfterFBT_id, ctxtAfterFBT_mod;
    SchemeletRLWEMP::ModSwitch(cx_bfv, Q, QBFVInit);
    SchemeletRLWEMP::ModSwitch(cy_bfv, Q, QBFVInit);

    auto cx = SchemeletRLWEMP::convert(*cc, cx_bfv, keyPair.publicKey, Bigq, numSlotsCKKS,
                                       depth - (levelsAvailableBeforeBootstrap > 0));
    auto cy = SchemeletRLWEMP::convert(*cc, cy_bfv, keyPair.publicKey, Bigq, numSlotsCKKS,
                                       depth - (levelsAvailableBeforeBootstrap > 0));

    auto c_sub      = cc->EvalSub(cx, cy);
    ctxtAfterFBT_id = cc->EvalFBTNoDecoding(c_sub, coeffcompidentity, PInput.GetMSB() - 1, ep->GetModulus(), order);

    auto csquare = cc->EvalSquare(ctxtAfterFBT_id);
    cc->ModReduceInPlace(csquare);
    auto csquare_decode = cc->EvalHomDecoding(csquare, scaleTHI * scaleTHI, 0);
    auto polys          = SchemeletRLWEMP::convert(csquare_decode, Q);

    auto computed =
        SchemeletRLWEMP::DecryptCoeff(polys, Q, POutput, keyPair.secretKey, ep, numSlotsCKKS, numSlotsCKKS, flagBR);
    std::cerr << "FBT square decode result: [";
    std::copy_n(computed.begin(), 8, std::ostream_iterator<int64_t>(std::cerr, " "));
    std::cerr << "]" << std::endl;

    SchemeletRLWEMP::ModSwitch(polys, Q, QBFVInit);
    auto c_txt_mod = SchemeletRLWEMP::convert(*cc, polys, keyPair.publicKey, Bigq, numSlotsCKKS,
                                              depth - (levelsAvailableBeforeBootstrap > 0));

    ctxtAfterFBT_mod = cc->EvalFBTNoDecoding(c_txt_mod, coeffmod, PInput.GetMSB() - 1, ep->GetModulus(), order);

    auto c_comp = cc->EvalHomDecoding(ctxtAfterFBT_mod, scaleTHI * scaleTHI, 0);
    polys       = SchemeletRLWEMP::convert(c_comp, Q);
    computed =
        SchemeletRLWEMP::DecryptCoeff(polys, Q, POutput, keyPair.secretKey, ep, numSlotsCKKS, numSlotsCKKS, flagBR);

    for (int i = 0; i < 8; i++) {
        std::cout << "(x-y)^2 %16  :" << static_cast<int>((x[i] - y[i]) * (x[i] - y[i])) % 16 << ", dec: " << computed[i]
                  << std::endl;
    }
}
8

As long as the functions have the same input and output size, you can use the same setup and the same EvalFBT call. If they don’t have the same input and output, you need to call the setup for the larger one and then ensure you adjust the levels (the one with larger input will consume more levels) and scaling for the smaller one during the computation.

Here is an example with running consecutive FBTs for LUTs of the same size.

1 Like
9

Thank you very much for your reply!!

ctxtAfterFBT_id = cc->EvalFBTNoDecoding(c_sub, coeffcompidentity, PInput.GetMSB() - 1, ep->GetModulus(), order); // identity function

// csquare->GetScalingFactor(): 1.40737e+14
auto csquare = cc->EvalSquare(ctxtAfterFBT_id);
// csquare->GetScalingFactor(): 1.9807e+28
cc->ModReduceInPlace(csquare); 
// csquare->GetScalingFactor(): 1.40737e+14

auto csquare_decode = cc->EvalHomDecoding(csquare, scaleTHI * scaleTHI, 0);
auto polys = SchemeletRLWEMP::convert(csquare_decode, Q);
auto c_txt_mod = SchemeletRLWEMP::convert(*cc, polys, keyPair.publicKey, Bigq, numSlotsCKKS,depth - (levelsAvailableBeforeBootstrap > 0));

ctxtAfterFBT_mod = cc->EvalFBTNoDecoding(c_txt_mod, coeffmod, PInput.GetMSB() - 1, ep->GetModulus(), order); // mod function
auto c_comp = cc->EvalHomDecoding(ctxtAfterFBT_mod, scaleTHI * scaleTHI, 2);
polys       = SchemeletRLWEMP::convert(ctxtAfterFBT_mod, Q);

computed =  SchemeletRLWEMP::DecryptCoeff(polys, Q, POutput, keyPair.secretKey, ep, numSlotsCKKS, numSlotsCKKS, flagBR);

However, I am still confused about how to correctly track the scaling factor in the above code. After the first FBT (identity function) followed by EvalSquare, using

cc->EvalHomDecoding(csquare, scaleTHI * scaleTHI, 0)

can successfully decode and decrypt the results. Then, I apply convert and EvalFBTNoDecoding to perform the second FBT (mod function). Since the mod function consumes less multiplicative depth than the identity function, I try to use

cc->EvalHomDecoding(ctxtAfterFBT_mod, scaleTHI * scaleTHI, 2)

to adjust the final decoding level. However, the outputs are incorrect.

When I print the scaling factor using GetScalingFactor(), it is 1.40737e+14 before squaring, 1.9807e+28 before modulus reduction, and 1.40737e+14 after modulus reduction. This makes me wonder:

  1. Why does EvalHomDecoding after EvalSquare and modulus reduction require scaleTHI * scaleTHI, while the example in UnitTest_ConsecLevLUT only uses t.scaleTHI instead of t.scaleTHI * t.scaleTHI?

  2. How should the scaling factor be adjusted properly in the second FBT and during EvalHomDecoding?

Thank you again for your patience and guidance!

10
  1. The Hermite coefficients are scaled by scaleTHI, and this scaling is removed in EvalHomDecoding for convenience. If you square the ciphertext before EvalHomDecoding, then it will be scaled by scaleTHI ^2, and you have to appropriately remove this scaling.
  2. There are several inconsistencies in what you are doing. It seems that both your functions use the same PInput, therefore, evaluating the corresponding interpolation should take the same number of levels. But as I mentioned before, you have set POutput which is different than PInput as the output plaintext size of all functional bootstrapping calls, yet the second call expects the ciphertext to be scaled by PInput. You have to align them.

Please take some time to pin the exact flow of what you are trying to achieve and ensure that the parameters align. If you still have questions, please create a different thread.

1 Like