Is it Possible to Use iterative Bootstrapping in Multiparty-Case

Library Questions
1

Hi,

I’m trying to set up a multiparty scenario with iterative bootstrapping.
The design concept is as follow: I have different scenarios with 2, 4 or 6 parties.
Each party encrypts data and send it to a computational host where the calculations are made.

I’m struggeling at some points…
Is iterative bootstrapping even possible? I had a look into the examples, but there is another approach of bootstrapping implemented.
On the other hand, I’m getting “approximation error too high” while trying to decrypt my data.
Basically, before rotation, the decryption works, after that, it doesn’t.

Could somebody have a look on my code and tell me what’s wrong with it?

double eps = 0.0001;

// Initialize Public Key Containers
KeyPair<DCRTPoly> kp1;  // Party 1
KeyPair<DCRTPoly> kp2;  // Party 2
KeyPair<DCRTPoly> kp3;  // Lead party - who finalizes interactive bootstrapping

KeyPair<DCRTPoly> kpMultiparty;
std::vector<int32_t> indices = {2};

////////////////////////////////////////////////////////////
// Perform Key Generation Operation
////////////////////////////////////////////////////////////

// Round 1 (party A)
kp1 = cryptoContext->KeyGen();

// Generate evalmult key part for A
auto evalMultKey = cryptoContext->KeySwitchGen(kp1.secretKey, kp1.secretKey);

// Generate evalsum key part for A
cryptoContext->EvalSumKeyGen(kp1.secretKey);
auto evalSumKeys = std::make_shared<std::map<usint, EvalKey<DCRTPoly>>>(
    cryptoContext->GetEvalSumKeyMap(kp1.secretKey->GetKeyTag()));

auto evalAtIndexKeys = std::make_shared<std::map<usint, EvalKey<DCRTPoly>>>(
            cryptoContext->GetEvalAutomorphismKeyMap(kp1.secretKey->GetKeyTag()));

// Round 2 (party B)
kp2                  = cryptoContext->MultipartyKeyGen(kp1.publicKey);
auto evalMultKey2    = cryptoContext->MultiKeySwitchGen(kp2.secretKey, kp2.secretKey, evalMultKey);
auto evalMultAB      = cryptoContext->MultiAddEvalKeys(evalMultKey, evalMultKey2, kp2.publicKey->GetKeyTag());
auto evalMultBAB     = cryptoContext->MultiMultEvalKey(kp2.secretKey, evalMultAB, kp2.publicKey->GetKeyTag());
auto evalSumKeysB    = cryptoContext->MultiEvalSumKeyGen(kp2.secretKey, evalSumKeys, kp2.publicKey->GetKeyTag());
auto evalSumKeysJoin = cryptoContext->MultiAddEvalSumKeys(evalSumKeys, evalSumKeysB, kp2.publicKey->GetKeyTag());
cryptoContext->InsertEvalSumKey(evalSumKeysJoin);

auto evalAtIndexKeysB =
            cryptoContext->MultiEvalAtIndexKeyGen(kp2.secretKey, evalAtIndexKeys, indices, kp2.publicKey->GetKeyTag());
auto evalAtIndexKeysJoin =
    cryptoContext->MultiAddEvalAutomorphismKeys(evalAtIndexKeys, evalAtIndexKeysB, kp2.publicKey->GetKeyTag());
cryptoContext->InsertEvalAutomorphismKey(evalAtIndexKeysJoin);

auto evalMultAAB   = cryptoContext->MultiMultEvalKey(kp1.secretKey, evalMultAB, kp2.publicKey->GetKeyTag());
auto evalMultFinal = cryptoContext->MultiAddEvalMultKeys(evalMultAAB, evalMultBAB, evalMultAB->GetKeyTag());
cryptoContext->InsertEvalMultKey({evalMultFinal});

/////////////////////
// Round 3 (party C) - Lead Party (who encrypts and finalizes the bootstrapping protocol)
kp3                 = cryptoContext->MultipartyKeyGen(kp2.publicKey);
auto evalMultKey3   = cryptoContext->MultiKeySwitchGen(kp3.secretKey, kp3.secretKey, evalMultKey);
auto evalMultABC    = cryptoContext->MultiAddEvalKeys(evalMultAB, evalMultKey3, kp3.publicKey->GetKeyTag());
auto evalMultBABC   = cryptoContext->MultiMultEvalKey(kp2.secretKey, evalMultABC, kp3.publicKey->GetKeyTag());
auto evalMultAABC   = cryptoContext->MultiMultEvalKey(kp1.secretKey, evalMultABC, kp3.publicKey->GetKeyTag());
auto evalMultCABC   = cryptoContext->MultiMultEvalKey(kp3.secretKey, evalMultABC, kp3.publicKey->GetKeyTag());
auto evalMultABABC  = cryptoContext->MultiAddEvalMultKeys(evalMultBABC, evalMultAABC, evalMultBABC->GetKeyTag());
auto evalMultFinal2 = cryptoContext->MultiAddEvalMultKeys(evalMultABABC, evalMultCABC, evalMultCABC->GetKeyTag());
cryptoContext->InsertEvalMultKey({evalMultFinal2});

auto evalAtIndexKeysC =
            cryptoContext->MultiEvalAtIndexKeyGen(kp3.secretKey, evalAtIndexKeys, indices, kp3.publicKey->GetKeyTag());
auto evalAtIndexKeysJoin2 =
    cryptoContext->MultiAddEvalAutomorphismKeys(evalAtIndexKeys, evalAtIndexKeysC, kp3.publicKey->GetKeyTag());
cryptoContext->InsertEvalAutomorphismKey(evalAtIndexKeysJoin2);

auto evalSumKeysC     = cryptoContext->MultiEvalSumKeyGen(kp3.secretKey, evalSumKeys, kp3.publicKey->GetKeyTag());
auto evalSumKeysJoin2 = cryptoContext->MultiAddEvalSumKeys(evalSumKeys, evalSumKeysC, kp3.publicKey->GetKeyTag());
cryptoContext->InsertEvalSumKey(evalSumKeysJoin2);

if (!kp1.good()) {
    std::cout << "Key generation failed!" << std::endl;
    exit(1);
}
if (!kp2.good()) {
    std::cout << "Key generation failed!" << std::endl;
    exit(1);
}
if (!kp3.good()) {
    std::cout << "Key generation failed!" << std::endl;
    exit(1);
}
cryptoContext->EvalBootstrapKeyGen(kp3.secretKey, batchSize);
cryptoContext->EvalRotateKeyGen(kp3.secretKey, {1,2,3,-1,-2,-3});
// END of Key Generation

std::vector<double> input1 = {14.0,47.89746762162162,9.182932, 97.5,53.902815050857185, 14.932224832748549,25.70880986063563, 42.76932656905464};
std::vector<double> input2 = {11.0,47.89746762162162,10.008757825825825, 189.16666666666666,53.784931171127575, 70.36906413174,13.117850483332402, 16.90789035155603};

Plaintext pt1       = cryptoContext->MakeCKKSPackedPlaintext(input1);
Plaintext pt2       = cryptoContext->MakeCKKSPackedPlaintext(input2);
usint encodedLength = input1.size();

auto ct1 = cryptoContext->Encrypt(kp3.publicKey, pt1);
auto ct2 = cryptoContext->Encrypt(kp3.publicKey, pt2);

auto cLat1Rad = cryptoContext->EvalMult(0.0174533, ct1); //Decryption works at this point
auto cLon1Rad = cryptoContext->EvalAtIndex(cLat1Rad, indices[0]); //After rotation, I'm getting approximation error too high

// INTERACTIVE BOOTSTRAPPING STARTS

auto ca1 = cryptoContext->IntMPBootAdjustScale(cLon1Rad);

// Leading party (party C) generates a Common Random Poly (crp) at max coefficient modulus (QNumPrime).
// a is sampled at random uniformly from R_{Q}
auto crp = cryptoContext->IntMPBootRandomElementGen(kp3.publicKey);
// Each party generates its own shares: maskedDecryptionShare and reEncryptionShare
// (h_{0,i}, h_{1,i}) = (masked decryption share, re-encryption share)
// we use a vector inseat of std::pair for Python API compatibility
vector<Ciphertext<DCRTPoly>> sharesPair0;  // for Party A
vector<Ciphertext<DCRTPoly>> sharesPair1;  // for Party B
vector<Ciphertext<DCRTPoly>> sharesPair2;  // for Party C

// extract c1 - element-wise
auto c1 = ca1->Clone();
c1->GetElements().erase(c1->GetElements().begin());
// masked decryption on the client: c1 = a*s1
sharesPair0 = cryptoContext->IntMPBootDecrypt(kp1.secretKey, c1, crp);
sharesPair1 = cryptoContext->IntMPBootDecrypt(kp2.secretKey, c1, crp);
sharesPair2 = cryptoContext->IntMPBootDecrypt(kp3.secretKey, c1, crp);

vector<vector<Ciphertext<DCRTPoly>>> sharesPairVec;
sharesPairVec.push_back(sharesPair0);
sharesPairVec.push_back(sharesPair1);
sharesPairVec.push_back(sharesPair2);

// Party B finalizes the protocol by aggregating the shares and reEncrypting the results
auto aggregatedSharesPair = cryptoContext->IntMPBootAdd(sharesPairVec);
auto ciphertextOutput     = cryptoContext->IntMPBootEncrypt(kp3.publicKey, aggregatedSharesPair, crp, ca1);

// INTERACTIVE BOOTSTRAPPING ENDS

// distributed decryption

auto ciphertextPartial1 = cryptoContext->MultipartyDecryptLead({ciphertextOutput}, kp1.secretKey);
auto ciphertextPartial2 = cryptoContext->MultipartyDecryptMain({ciphertextOutput}, kp2.secretKey);
auto ciphertextPartial3 = cryptoContext->MultipartyDecryptMain({ciphertextOutput}, kp3.secretKey);
vector<Ciphertext<DCRTPoly>> partialCiphertextVec;
partialCiphertextVec.push_back(ciphertextPartial1[0]);
partialCiphertextVec.push_back(ciphertextPartial2[0]);
partialCiphertextVec.push_back(ciphertextPartial3[0]);

Plaintext plaintextMultiparty;
cryptoContext->MultipartyDecryptFusion(partialCiphertextVec, &plaintextMultiparty);
plaintextMultiparty->SetLength(encodedLength);
2

In the multiparty case, it is more efficient to use interactive bootstrapping (it gives a higher precision, too). See Collaborative Privacy-Preserving Analysis of Oncological Data using Multiparty Homomorphic Encryption for a technical description of interactive bootstrapping. Also see the following OpenFHE examples:

3

When you say iterative bootstrapping, are you referring to double-precision (iterating to get higher precision) or interactive bootstrapping? I was not sure what you were asking about. So I described the preferred way of using bootstrapping in a multiparty setting.

4

I meant iterative Bootstrapping for double precision actually but it seems not be the preferred approach in the multiparty setting. However, it went through the chebyshev example and I’ve merged it with the code from the unit test hence there is a rotation implemented. In my case, decryption works fine after the multiplication but it throws the approximation error as soon as try a rotation. Do I need to perform the Bootstrapping procedure after each calculation or is there an indicator when the noise level hits the threshold? I appreciate your efforts.

5

No, bootstrapping is only needed when you don’t have enough levels for a computation (you don’t have to bootstrap after operation). Just to rule out the depth as the issue, you can increase the multiplicative depth to a higher number (by 1, for example).

Probably the rotation keys are not generated correctly in your example (using the distributed key generation procedure), which would cause the incorrect result. Did you try the rotation w/o using the bootstrapping feature just to make sure distributed key generation for rotation keys works fine?

It is hard to diagnose this w/o looking at the code. If you are not able to troubleshoot it on your own, please post the code you are trying to run.

7

From what I can see, you use dcrtBits = 80 while firstMod = 81. This can easily lead to an overflow. There may be other issues, too.

In general, I suggest posting only minimal working or reproducible examples in this forum (see Minimal reproducible example - Wikipedia or How to create a Minimal, Reproducible Example - Help Center - Stack Overflow). The Discourse forum is not intended for troubleshooting full applications, advanced examples, or homework assignments. The main idea is to clarify concepts, report bugs, and discuss potential uses of OpenFHE/FHE.