Multiparty key generation

Turning CKKS into a multiparty computation only requires changing two pieces of the pipeline: key generation and decryption. Encoding, encryption, the homomorphic operations, and decoding all run unchanged on the joint keys produced by this protocol. The cost is that key generation becomes a three-round ceremony among the $n$ parties, and that decryption requires at least $t$ of them to come back together at the end.

The ceremony runs in three rounds:

• Round 1. Each party samples a secret-key shard $s_i(X)$ locally. The group secret key is $s(X) = s_1(X) + \cdots + s_n(X)$, but this sum is never actually computed. Each party then publishes shards of the public key, the rotation keys, and the conjugation key derived from its $s_i$; summing the broadcasts yields the joint public key, joint rotation keys, and joint conjugation key. The parties also publish auxiliary information that round 2 will need to produce the relinearization key.
• Round 2. Each party combines its $s_i$ with the round-1 broadcasts to produce a shard of the relinearization key; the sum of the shards is the joint relinearization key. To enable $t$-of-$n$ decryption, every pair of parties also exchanges a small piece of information, so that any $t$ of them can reconstruct the missing parties' contributions during decryption.
• Round 3. The parties jointly compute the ephemeral key-switching keys used internally during bootstrapping. This round is only needed when the computation involves bootstrapping; if it doesn't, the ceremony ends after round 2.

Key generation: round 1

[WORK IN PROGRESS]

Secret-key shards

How the parties agree on common randomness and sample their secret-key shards $s_i$.

Public, rotation, and conjugation key shards

How each party derives its shards of the joint public key, rotation keys, and conjugation key from $s_i$.

Relinearization key setup

The auxiliary information broadcast in round 1 that round 2 will need to produce the joint relinearization key.

Key generation: round 2

[WORK IN PROGRESS]

Relinearization key shards

How each party combines its $s_i$ with the round-1 broadcasts to produce a relinearization key shard, and how the shards sum to the joint relinearization key.

Pairwise $t$-of-$n$ shares

The Shamir procedure: the information every pair of parties exchanges so that any $t$ of them can later reconstruct the missing parties' contributions at decryption time.

Key generation: round 3

[WORK IN PROGRESS]

How the parties jointly compute the ephemeral key-switching keys used internally during bootstrapping. This round is only needed when the computation involves bootstrapping; if it doesn't, the ceremony ends after round 2.

Multiparty decryption

[WORK IN PROGRESS]

How any $t$ of the $n$ parties combine their partial decryptions to recover the result, why noise flooding is needed to keep partial decryptions from leaking the shards, and how much flooding noise is enough.