Distributed / Multiparty Bootstrapping

Hello everyone,

I would like to use CKKS in a multiparty setting.
Thanks to the threshold-fhe.cpp example, I was able to perform the basic operations in multiparty setting. However, I cannot find a multiparty bootstrapping functionality. Is there any workaround for that?

I think my question is also quite related to this one: Encryption to additive Shares. Since Mouchet et al. designed a multiparty bootstrapping functionality by converting a ciphertext to secret shares and back.

Thanks for your attention!

Hi @FMazzone - the development of the functionality you are asking about is underway. We did a POC internally, and it proved to be working successfully. Adding the functionality to OpenFHE requires further testing and software development efforts.

Hi @Caesar, thanks for the prompt reply. This is very good news!

Is there any chance you already have an estimated time you expect the functionality to be available to the users? (like a matter of a couple of months? or maybe a year?)

Did the POC implement the method described by Mouchet et al.?

We followed this work.

Thanks! It is very similar to what is done by Mouchet et al.

Is it possible to get the alpha version of the implementation?

1 Like

I would be interested in the alpha version of the implementation as well :slight_smile:

Just to put some context, our first work instantiated MHE over BFV, where the plaintext domain is mod T. In this case it is easy to switch in and out of the secret sharing domain without introducing new security assumptions because everything happens mod T. The shares can be created and reconstructed mod T using the native plaintext space of the scheme.

However for CKKS (in the Poseidon work) the plaintext domain is the complex space, not a finite field. You could still generate shares mod q0 and do LSS arithmetique mod q0, but when reconstructing you also need to do it mod q0 or you will have to do a homomorphic modular reduction (the EvalMod step of the bootstrapping). Thus it does not help increasing the modulus. Instead you have to generate and reconstruct the shares without modular reduction. This changes the usual security assumption from perfect hiding mod T to a statistical hiding in the complex space. To achieve this statistical hiding the shares must be much larger than the values you want to hide. The cost of having to generate such large shares is that you have to refresh not when you reach level 0 but at a level that has still enough modulus to store without modular reduction the sum of all the shares of the parties.

A benefit of doing the refresh by going in and out of the LSS domain is that during that temporary time where the plaintext is in the LSS domain you can carry out any public linear transformation without interaction basically for free and this includes homomorphic encoding and decoding.

Interesting, thanks for the insight @Pro7ech .

Just to be sure that I fully understood: we cannot use shares mod q0 because - when we reconstruct - we would still be mod q0, but the newly refreshed ciphertext should be supposed to be associated to mod qL, is that right? (Sorry for the possibly dumb question but I’m quite a rookie wrt CKKS.)

@Pro7ech thank you the explanation. I want to add a couple of comments and answer the question about the “alpha” version of interactive CKKS bootstrapping.

As @Pro7ech pointed out, in the proposed interactive protocol, we do need to do masking using a flooding distribution of 128+ bits as we do masking over integers rather than integers mod q. This requires carrying additional (typically 3) RNS limbs (“levels”) before interactive CKKS bootstrapping can be called. This flooding does get trickier in the case of regular threshold FHE or IND-CPA decryption (not interactive bootstrapping), and we will soon update the existing thread on it in the discourse forum: Appropriate error parameters for the noise flooding. Some new options are also getting added to OpenFHE.

As for the availability of interactive CKKS bootstrapping in OpenFHE, we are planning to add the initial implementation to the main OpenFHE repo shortly after the v1.0 release. Currently we are wrapping up v1.0, which will be released in November. It will have a couple of significant improvements as compared to v0.9.5.

1 Like