Clarification about collective key switching

[jon-chuang]

I don't understand why collective key switching must be performed rather than generating keyswitch keys.

Can't a similar procedure be used to generating relinearisation keys collectively?

This approach seems to introduce unnecessary communication costs.

Furthermore, there does not seem to be a description of how galois keys can be generated. However, can't one generate Galois keys by just permuting the coefficients of the secret key? This is not a problem even if we are dealing with shared secrets. So it is easy to publish galois keys, is it not? What other purpose is there for collective key switching?

[Pro7ech]

Hello Jon-Chuang,

Yes you are right, the parties could in theory also generate in advance a keyswitching key and have someone else carry the operation using only public operations. Using such an approach does however introduces a larger noise amount than just having each party partialy re-encrypt the ciphertext.

Edit1 : an other point to take into consideration is that the collective key switching protocol enables the parties to keep control on input key. If a key-switching key s1 -> s2 was created, then anyone could operate the re-encryption and both keys would become equivalent.

Edit2 : the protocol "relinkey_gen" does enable the generation a collective relinearisation key.

The galois keys are an encryption of a permutation of the coefficients of the collective secret-key, so yes they are as "easy" to generate as the collective public-key.

What do you mean by "What other purpose is there for collective key switching?" ?

[ChristianMct]

To add up to @Pro7ech 's answer, the CKS protocol enables the parties to allow decryption or, re-encryption under the receiver's key, of the computation result (and only the computation result) to be performed. Indeed, this needs to be an interactive functionality (because of @Pro7ech's Edit1).

So, in our terminology, we differentiate the notions of key-switching (s1 -> s2) and relinearization (s^2 -> s).

[jon-chuang]

Hi all, I understand this better now, thank you.

Essentially, collective keyswitching is meant as a barrier so that the parties who have a stake in the data can collectively agree to allow a single party to decrypt the data, even if they do not know the secret key of that party (PCKS), or that party has shared it with them collectively through secret sharing (CKS).

However, I still feel there is a missing piece of the puzzle, which is zero knowledge. That's because none of the parties involved could otherwise verify the result of the computation is correct without possibly revealing secret information to some parties, by decrypting the result, which could happen prematurely.

On the other hand, if all the parties fully trust the server to perform all the computations before allowing them to decrypt the ciphertext, then they should trust it to send the ciphertext directly to the recepient. Hence the barrier only becomes of use if parties can efficiently verify that the computation has been performed correctly on the data.

This would incur some overhead (100x?) but may be what an application developer wants, to have more control over their data.

I am interested in this as a research topic as well as implementation perspective, and will look into feasibility from recent work on zk-SNARKs/STARKS like Fractal or Aurora.

I am also working on a HE protocol that would allow multiple parties to force a server to only be able to decrypt a piece of data only after a computation has been done, in a non-interactive way. Since the power to encrypt is distributed, there may not be a risk in utilising a smaller subset of a for which the result is precomputed, and I believe I can show that choosing a sufficiently large such set, to match the intrisic entropy of the data itself, instead of drawn uniformly from Rq each time, one can achieve this.

By generating random such a as a shared secret, and computing the result of a function on these a in a homomorphic way via zero knowledge and/or 100% consensus, we can verify that the computed values only decrypt the pseudorandom mask -s.f(a), which can be decrpyted via the published public keys s.f(a) + e, without any of the parties knowing the underlying a, only the id associated with them. This would be true as long as s.f(a) + e is a one way function of a, given no colluding knowledge of s. In RLWE, we normally demand that conversely, it is computationally hard to obtain information about s given a and s.a+e. This may be possible to show if we can show that the addition and multiplication of two pseudorandom plaintexts is pseudorandom.

It could then be relatively cheap to compute 2^15 such values collectively, although the exact threshold required must be calculated by taking into account the entropy of the data themselves.

We have to show this holds true for all homomorphic operations and a given entropy in the underlying data.

Since the cost of zero-knowledge is limited to the prior decrpytion-key generation stage, it is much less costly than zk for the computations of a server on arbitrary data.

Via this method, it is trivial to show that two party computation between client and server can be reduced to one-way communication.

[ChristianMct]

You are correct about the need for ZK primitives when more guarantees are needed and we would be happy to push this discussion further. As for the HE scheme you are proposing, this seems like an interesting path to investigate. However, since it does not concern the code-base directly, please use the Lattigo mailing list: lattigo@listes.epfl.ch.

[ChristianMct]

Closing: discussion taken offline.

[jon-chuang]

The above scheme I described does not exist, as I just figured out today.

Hence I think zero knowledge is the only viable alternative we known of.