Threshold encryption with different sources

Library Questions
1

Dear all,

I have the following threshold use case (the classical MPC millionaire’s problem): Three parties wanting to compute the mean of their salaries but not wanting to reveal the private inputs to the others. Threshold FHE seems to be a good approach to solve this problem asynchronously, so I have started to implement the solution.

However, I found out that the shared public key is generated as follows:

  1. P1 generates a CKKS key pair (kp1) using the KeyGen() function.
  2. P2 then runs MultipartyKeyGen(kp1.publicKey) to generate their key pair.
  3. P3 finally runs MultipartyKeyGen(kp2.publicKey) to generate their key pair. The public key of this last key pair is the one used for encryption.

Thus, only P3 is obtaining the resulting (correct) public key, while P1 and P2 should receive it in order to encrypt their private salaries. There is a trust issue here because P3 could send another public key to them and make the threshold FHE protocol go wrong, or even worse, take advantage of it to learn from the other’s salaries.

In consequence, I searched for the theoretical protocol resource to study if there was another way to compute this shared key. I found out that the threshold protocol implemented in OpenFHE seems to be based on the protocol presented in this paper, where they explain that the shared key is no more than pk*=[sum(pk_i[0]), a], where pk_i[0] is the first component of the public key generated by party Pi, and a is a fixed value that all the partial public keys have as second components.

Considering that, it should be possible to change the above public key generation protocol and use the following:

  1. P1 generates a key pair kp1 using KeyGen() and sends kp1.publicKey to P2 and P3
  2. P2 generates a key pair kp2 using KeyGen() and sends kp2.publicKey to P1 and P3
  3. P3 generates a key pair kp3 using KeyGen() and sends kp3.publicKey to P1 and P2
  4. P1, P2 and P3 compute the addition locally and obtain the shared public key.

Hence, I searched inside the OpenFHE MultiParty wrapper for a function allowing to perform additions of public keys and found out one: MultiAddPubKeys(pk1, pk2, tag). However, I do not know if this function gives me the functionality I am expecting…

It would be great to know if the above key generation protocol’s implementation is possible inside the OpenFHE implementation and, if so, how to do it exactly.

Sorry for the large explanation and thanks for reading,

Julen

2

MultiAddPubKeys adds two public keys where the random element is the same (common). It uses the random ring element from the first public key and adds the “encryptions” of secret shares. So yes, it can be be used for this scenario.

To generate public keys using a common random ring element, you can use MultipartyKeyGen and feed to it a public key that only contains the common ring element, i.e., create a public key that is set to (0,a), where a is a random ring element.

3

That is great to know! Is there any built-in function to create such a public key? Meaning a public key that only contains the common ring element (0, a).

Thanks in advance,

Julen

4

I think the easiest way is to create a public key using a constructor (with cryptocontext) and then use SetPublicElements to set it to a vector of ring elements.

Another somewhat related function is IntMPBootRandomElementGen. I suggest looking at https://github.com/openfheorg/openfhe-development/blob/v1.1.1/src/pke/examples/tckks-interactive-mp-bootstrapping.cpp to see how it is typically used.