Complex-values Bootstrapping

[lawrencekhlim]

Dear authors of FIDESlib,

I have few questions regarding bootstrapping: I wanted to support complex-values in my application using FIDESlib. I noticed that OpenFHE only supported complex values starting in version 1.3.0, which is the version right after FIDESlib interoperates with OpenFHE, which is version 1.2.4. So at the commit where complex values were supported in OpenFHE, I tweaked it to be compatible with FIDESlib. You can see my modifications to OpenFHE here. There are a few minor tweaks to FIDESlib as well to enable compilation. (I am happy to share them with you if you are interested.)

This mostly worked, and I was able to get additions, multiplications, rotations, and conjugations on complex-values with FIDESlib to work. However, I was only able to somewhat get bootstrapping to work. I say somewhat because some configurations of parameters work while other do not. As far as I can tell, between OpenFHE version 1.2.4 and the commit that added complex-valued support, not much is changed about bootstrapping (but I may be wrong), so it's puzzling to me that it sometimes works but other times does not.

My main questions are:

1. What should we modify about FIDESlib to get complex-valued support for bootstrapping?
2. What are the main differences between the OpenFHE's bootstrapping (on version 1.2.4) and FIDESlib's bootstrapping?

Here are some parameters that I've tested (all of the below work on OpenFHE with little error):

This one has bootstrapping working correctly:

    constexpr uint32_t ring_dim = 1 << 16;
    constexpr uint32_t num_slots = ring_dim / 2;
    const std::vector<uint32_t> level_budget = {3, 3};

    constexpr uint32_t scale_mod_size = 59;
    constexpr uint32_t first_mod = 60;
    constexpr uint32_t num_large_digits = 5;

    lbcrypto::CCParams<lbcrypto::CryptoContextCKKSRNS> parameters;
    parameters.SetScalingModSize(scale_mod_size);
    parameters.SetFirstModSize(first_mod);
    parameters.SetRingDim(ring_dim);
    parameters.SetBatchSize(num_slots); 
    parameters.SetSecurityLevel(lbcrypto::HEStd_NotSet);
    parameters.SetScalingTechnique(lbcrypto::FLEXIBLEAUTO);
    parameters.SetNumLargeDigits(num_large_digits);
    parameters.SetCKKSDataType(lbcrypto::COMPLEX);

    // Default secret key distribution.
    // parameters.SetSecretKeyDist(secretKeyDist);

    // Parámetros bootstrap.
    constexpr uint32_t levelsAvailableAfterBootstrap = 12;

    usint depth = levelsAvailableAfterBootstrap + lbcrypto::FHECKKSRNS::GetBootstrapDepth(level_budget, parameters.GetSecretKeyDist());
    parameters.SetMultiplicativeDepth(depth);

But set the secret key distribution to sparse ternary, and it does not decrypt properly.

auto secretKeyDist = lbcrypto::SecretKeyDist::SPARSE_TERNARY;
parameters.SetSecretKeyDist(secretKeyDist);

Setting the modulus sizes to be smaller with the default secret key distribution also does not decrypt properly (but this one is at least within an order of magnitude):

    constexpr uint32_t scale_mod_size = 49;
    constexpr uint32_t first_mod = 52;

    // Later    

    // Default secret key distribution.
    // parameters.SetSecretKeyDist(secretKeyDist);

[lawrencekhlim]

These were my minor modifications to FIDESlib to enable complex-values:

diff --git a/include/CKKS/openfhe-interface/RawCiphertext.cuh b/include/CKKS/openfhe-interface/RawCiphertext.cuh
index 51b83e6..d544f72 100644
--- a/include/CKKS/openfhe-interface/RawCiphertext.cuh
+++ b/include/CKKS/openfhe-interface/RawCiphertext.cuh
@@ -34,7 +34,7 @@ struct RawCipherText {
 
 struct RawPlainText {
     //  lbcrypto::CryptoContext<lbcrypto::DCRTPoly> & cc; // Original CryptoContext object from OpenFHE;
-    lbcrypto::Plaintext originalPlainText;  // Original Ciphertext object from OpenFHE;
+    lbcrypto::ConstPlaintext originalPlainText;  // Original Plaintext object from OpenFHE;
     std::vector<std::vector<uint64_t>> sub_0;
     std::vector<uint64_t> moduli;  // moduli for each limb
     int numRes;     // number of residues of ciphertext, length of moduli array and first dimension of sub-ciphertexts
@@ -94,7 +94,7 @@ RawCipherText GetRawCipherText(lbcrypto::CryptoContext<lbcrypto::DCRTPoly>& cc,
 
 void GetOpenFHECipherText(lbcrypto::Ciphertext<lbcrypto::DCRTPoly> result, RawCipherText raw, int REV = 1);
 
-RawPlainText GetRawPlainText(lbcrypto::CryptoContext<lbcrypto::DCRTPoly>& cc, lbcrypto::Plaintext pt);
+RawPlainText GetRawPlainText(lbcrypto::CryptoContext<lbcrypto::DCRTPoly>& cc, lbcrypto::ConstPlaintext pt);
 
 void GetOpenFHEPlaintext(lbcrypto::Plaintext result, RawPlainText raw, int REV = 1);
 
diff --git a/src/CKKS/openfhe-interface/RawCiphertext.cu b/src/CKKS/openfhe-interface/RawCiphertext.cu
index 32d5112..feec7be 100644
--- a/src/CKKS/openfhe-interface/RawCiphertext.cu
+++ b/src/CKKS/openfhe-interface/RawCiphertext.cu
@@ -159,7 +159,7 @@ void FIDESlib::CKKS::GetOpenFHEPlaintext(lbcrypto::Plaintext result, RawPlainTex
 }
 
 FIDESlib::CKKS::RawPlainText FIDESlib::CKKS::GetRawPlainText(lbcrypto::CryptoContext<lbcrypto::DCRTPoly>& cc,
-                                                             lbcrypto::Plaintext pt) {
+                                                             lbcrypto::ConstPlaintext pt) {
     RawPlainText result;  //{.cc = cc};
     result.originalPlainText = pt;
     result.numRes = pt->GetElement<DCRTPoly>().GetAllElements().size();

Any help would be greatly appreciated. Thanks so much!

[carlostriste]

Alright, I'd maybe have to look deeper into this, but this looks easy to add:

• Use ConstPlaintext like you show
• Implement complex operand AddScalar and MultScalar

Surprisingly, bootstrap remains unchanged (not really that surprising since linear transforms and polynomial evaluation should work on complex values no problem). (I think not even complex AddScalar and MultScalar are needed for complex bootstrapping)

What I think is causing problems in FIDESlib bootstrap:

• Handling SPARSE_TERNARY, I think we just do not do this. Most importantly, OpenFHE does not handle the scale adjustment the same on UNIFORM_TERNARY and SPARSE_TERNARY bootstrap so that might break the code.
• This public FIDESlib version might not do full ModDown hoisting which might increase noise, and so fails to decrypt when the scaling factor is smaller (see that 6-bit precision decrypts, <= 5 bit precision launches an exeption in OpenFHE).

I have already fixed these issues with bootstrapping on my private branch. At this point we are close to releasing all the improvements as a major update to the library, so really, all that would be needed is the new AddScalar and MultScalar functionality.

Also, it is on my bucket list to create OpenFHE 1.3.X and 1.4.X patches for FIDESlib, but on the complex value support side, we could do that on 1.2.X like you said.

If you want to speed up the process, implement complex AddScalar and MultScalar. Fixes to Bootstrapping are coming soon on our side.

[lawrencekhlim]

Thank you for the response! I will look into it!

[lawrencekhlim]

Looking for a little help (as we're not completely familiar with how to implement add and multiply complex scalar in CKKS). We were modifying FIDESlib based on the EvalAdd algorithm in OpenFHE here. But our modifications have led to decryption errors so I'm not completely understanding the algorithm:

First, the OpenFHE implementation separates the real and imaginary parts and calls GetElementForEvalAddOrSub on each. This maps to a similar function that you have implemented here. But the next step I'm not completely understanding in OpenFHE: For each of the q primes, add the real part from GetElementForEvalAddOrSub to the first coefficient of the polynomial (line 87), and the imaginary part to the N/2 coefficient (line 88). Everything else is zero. Is it supposed just the first coefficient and N/2 coefficient?

In FIDESlib, I noticed that you sum the real part from ElemForEvalAddOrSub with all of the coefficients (and obviously this provides correctness). We thought that (based on the OpenFHE implementation), we were only supposed to add to the first coefficient and N/2 coefficient and implemented that by adding an add_complex_scalar kernel (based on your add_scalar kernel) but that did not work. Is there some guidance you could provide as to what we're supposed to do?

[carlostriste]

Without looking at this further, I believe that for the single-real value encoding, we know that the evaluation of the polynomial $p(X) = \sum{a_i X^i} = a_0$ is that $NTT(p)_i = p(\omega^{2*i+1}) = a_0 \forall i \in { 0, \ldots, N-1}$ so I might be skipping computing the actual NTT on the input. This assumption might break for complex values since we have to project the complex value into a polynomial with real (and then integer) coefficients.

You will have to adapt carefully OpenFHE's implementation.

I'd suggest to first try an easier path, just encode a 1 slot, complex value plaintext in OpenFHE and use Ciphertext::addPt and Ciphertext::MultPt to emulate the functionality in a less efficient way.

For an optimized implementation, you will have to analyze the actual structure of the precomputed elements after the NTT

DCRTPoly elemsComplex(elemParams, Format::COEFFICIENT, true); uint32_t sizeQl = elemsComplex.GetNumOfElements(); for (uint32_t i = 0; i < sizeQl; i++) { NativeVector vec(N, cv[0].GetElementAtIndex(i).GetModulus()); NativeInteger mod = cv[0].GetElementAtIndex(i).GetModulus(); vec[0] = (operand.real() > 0) ? NativeInteger(elemsRe[i].Mod(mod)) : mod.ModSub(elemsRe[i], mod); vec[N / 2] = (operand.imag() > 0) ? NativeInteger(elemsIm[i].Mod(mod)) : mod.ModSub(elemsIm[i], mod); NativePoly element(cv[0].GetElementAtIndex(i)); element.SetValues(vec, Format::COEFFICIENT); elemsComplex.SetElementAtIndex(i, element); } **elemsComplex.SetFormat(Format::EVALUATION);**

That last SetFormat corresponds with an NTT. I'd say that if the structure of elemsComplex is not predictable (something like {a, a, ..., a, b, b, ...., b} ) its not worth to impement an optimized kernel for it.

Whatever the final result is, if you end up having to load whole plaintexts from host to GPU, a good solution might be to cache those GPU plaintexts since the likelihood of reuse is high and you will remove unneccessary host-to-device transfers.

I hope this helps.

[lawrencekhlim]

Hi Carlos,

Apologies for the slow reply. We've been busy with other work. We have a working prototype implementation of addScalar (for a complex value) that creates a plaintext. We also tried setting up the polynomials, but couldn't figure out how to call the GPU NTT for a plaintext. Let us know if you're interested in our first implementation.

For the modifications to bootstrapping and other updates, we're wondering: what your timeline is for releasing updates? Our research is a little dependent on your updates, so we're trying to figure out what we should do. (If we could see your private branch, that would be great too.)

Thanks,
Lawrence

[carlostriste]

Hello, I believe calling NTT will be something like
plaintext.c0.NTT();

I'm interested to know whether this ends up working, its a very interesting addition. I also have an additional interest on how the noise management/estimation works with complex OpenFHE since AFAIK error is estimated during decription by analizing the magnitude of the complex components of the real plaintext (perhaps by computing $$abs(Im(x + HConj(x)))$$, I just thought about it).

For updates to bootstrap (and a bunch of other stuff), hopefully before christmas, I really hope this is not a problem, I'll make an effort to get it done since we've been delaying it to add improvements.

[lawrencekhlim]

Here's our working add complex scalar implementation (largely following OpenFHE):

void Ciphertext::addScalar(const std::complex<double> c) {
    CudaNvtxRange r(std::string{std::source_location::current().function_name()}.substr(23 + strlen(loc)));

    auto elem1 = cc.ElemForEvalAddOrSub(c0.getLevel(), std::fabs(c.real()), this->NoiseLevel);
    auto elem2 = cc.ElemForEvalAddOrSub(c0.getLevel(), std::fabs(c.imag()), this->NoiseLevel);

    uint32_t sizeQl = c0.getLevel() + 1;

    std::vector<uint64_t> moduli(sizeQl);
    for (int i = 0; i < sizeQl; ++i)
        moduli[i] = cc.prime[i].p;

    std::vector<std::vector<uint64_t>> data;
    for (uint32_t i = 0; i < sizeQl; i++) {
        std::vector<uint64_t> vec(cc.N, 0);
        vec[0]            = (c.real() > 0) ? elem1[i] % (moduli[i]) : (-elem1[i] % (moduli[i]) + moduli[i]) % (moduli[i]);
        vec[cc.N / 2]        = (c.imag() > 0) ? elem2[i] % (moduli[i]) : (-elem2[i] % (moduli[i]) + moduli[i]) % (moduli[i]);
        data.push_back(vec);
    }

    RNSPoly elemComplex(cc, data);
    elemComplex.NTT(cc.batch);
    c0.add(elemComplex);
}

[lawrencekhlim]

Thanks so much for your help! Regarding noise estimation on OpenFHE, I believe that OpenFHE does not handle noise estimation for complex values. If it's possible to release your updates before Christmas, then that would be extremely helpful to us, as we're nearing completion of a few papers that require your bootstrapping.

Here's our working multiply complex scalar (also largely following OpenFHE):

void Ciphertext::multScalar(const std::complex<double> c, bool rescale) {
    CudaNvtxRange r(std::string{std::source_location::current().function_name()}.substr(23 + strlen(loc)));

    if (cc.rescaleTechnique == Context::FLEXIBLEAUTO || cc.rescaleTechnique == Context::FLEXIBLEAUTOEXT ||
        cc.rescaleTechnique == Context::FIXEDAUTO) {
        if (NoiseLevel == 2)
            this->rescale();
    }
    assert(this->NoiseLevel == 1);

    auto elem1 = cc.ElemForEvalMult(c0.getLevel(), c.real());
    auto elem2 = cc.ElemForEvalMult(c0.getLevel(), c.imag());

    RNSPoly real0 = c0.clone();
    RNSPoly imag0 = c0.clone();
    RNSPoly real1 = c1.clone();
    RNSPoly imag1 = c1.clone();
    real0.multScalar(elem1);
    imag0.multScalar(elem2);
    real1.multScalar(elem1);
    imag1.multScalar(elem2);

    uint32_t N               = cc.N;
    uint32_t M               = 2 * N;

    std::vector<std::vector<uint64_t>> poly;
    uint32_t power        = M / 4;
    uint32_t powerReduced = power % M;
    uint32_t index        = power % N;
    for (int i = 0; i <= c0.getLevel(); ++i) {
        std::vector<uint64_t> vec(N, 0);
        vec[index]       = powerReduced < N ? 1 : cc.prime[0].p - 1;
        poly.push_back(vec);
    }
    RNSPoly monomial(cc, poly);
    monomial.NTT(cc.batch);

    imag0.multElement(monomial);
    imag1.multElement(monomial);
    c0.add(real0, imag0);
    c1.add(real1, imag1);

    // Manage metadata
    NoiseLevel += 1;
    NoiseFactor *= cc.param.ScalingFactorReal.at(c0.getLevel());
    if (rescale) {
        NoiseFactor /= cc.param.ModReduceFactor.at(c0.getLevel());
        NoiseLevel -= 1;
    }

    if (rescale) {
        c0.rescale();
        c1.rescale();
    }
}

I can make a pull request when I'm free sometime.

[lawrencekhlim]

Happy Holidays! Are there any updates on this? To help us make a decision on what to do?

[carlostriste]

Hey, can you shoot me an email at carlos.a.d@um.es,? let's get you an updated version before we add the final touches for public release.