Multiparty non-interactive bootstrapping (CKKS)

[AntonIsraelsson]

Hi,
I'm working on a project that necessitates non-interactive bootstrapping for CKKS. In the paper I believe most of the multi-party construction for Lattigo is based on it is stated that interactive bootstrapping is preferred for performance reasons, implying that it is fully feasible to have non-interactive bootstrapping in the multi-party scheme. Are there any unseen road blocks towards using non-interactive bootstrapping in the multi-party scheme, or is it a straight-forward application of the multi-party key generation steps followed by plugging in into the implemented bootstrapping circuit for CKKS?

[lehugueni]

Hi!

In the end a multi-party ciphertext is just a normal LWE ciphertext encrypted under the common public-key. So applying the bootstrapping circuit to it in a straightforward way should work.
From an implementation point of view, the main task might be to implement a helper function that will generate all needed keys for the bootstrapping (i.e. the multi-party equivalent of GenEvaluationKeys in circuits/ckks/bootstrapping/keys.go).

[ChristianMct]

Actually, there is one important limitation regarding bootstrapping of multiparty ciphertexts.

In short, the bootstrapping algorithm strongly depends on the ciphertext being encrypted with a key in the ternary (and potentially sparse) distribution. Without assuming a trusted dealer or more complex protocol for key-generation, this is typically not the case in the multiparty setting.

In more details, the bootstrapping algorithm homorphically evaluates a modular reduction, a non-polynomial function. To do so, it is approximated over some interval, the size of which grows with the "norm" of the secret-key. The degree of the estimation grows with the interval size, hence so does the required ciphertext modulus. So, technically, one could bootstrap a multiparty ciphertext by growing the bootstrapping parameters. However, such parameterisation would most probably be impractical (esp. for large number of parties). In any case, the example parameters in the library assume ternary keys, so the using them in the multiparty setting would not result in a correct bootstrapping.