Supporting multiple keys in a single context

[Kim Laine]

Hi everyone,

We are starting a concrete discussion on how to improve the draft API at https://github.com/HomomorphicEncryption/API_Standard.

The second question we have is related to supporting multiple keys for multi-party FHE scenarios. Please post any comments and questions in this thread.

Question:

Currently the core API specification assumes a single secret key per context, with all public/evaluation keys derived from it. There are cases when HE computations operate on data from multiple parties, e.g., multi-key FHE, threshold FHE, or proxy re-encryption. How should these scenarios be handled?

Example:

Consider FHE with proxy re-encryption enabled. A ciphertext is re-encrypted from secret key A to secret key B. Then we need to call EvalMult with relinearization. How does the context know that it needs to apply the relinearization key corresponding to secret key B?

Possible solution 1:

Every secret key could carry a unique “tag” with it that identifies all crypto objects derived from it (ciphertexts, public keys). This tag would be stored in the serializations of ciphertexts, public keys, etc. This would make the problem easy to solve, but raises some potential security questions: two ciphertexts encrypted under different secret keys can now be distinguished.

Possible solution 2:

Carry a unique “tag” only during runtime, thus supporting multiple secret keys within the same context. The important difference w.r.t. Solution 1 is that the “tag” is not serialized to persistent storage at any point.

Possible solution 3:

Add a mechanism for context switching. For instance, we could store a runtime context id to indicate the new context in this scenario.  The requirement is that both contexts should be loaded in the memory.

Best,

Kim and Yuriy