The appropriate circumstances for each privacy protection methods

[vrvrv]

Question

General question 1

Homomorphic encryption makes possible simple computation, such as addition and multiplication, in encrypted space. I have question "Even if private keys are different, still is it possible to compute in encrypted space?". In other words, let Enc₁ be
an homomorphism that client 1 has (private key1) and Enc₂ be another homomorphism that client 2 has (private key2). Then, the followings may be possible
Enc₁(x+y) = Enc₁(x)+ Enc₁(y) and Enc₁(xy) = Enc₁(x) Enc₁(y)
Enc₂(x+y) = Enc₂(x)+ Enc₂(y) and Enc₂(xy) = Enc₂(x) Enc₂(y)
But, is it possible to decrypt Enc₁(x)+Enc₂(y) or Enc₁(x)Enc₂(y)? I think it would be matter if there are multiple clients(or input sources) and they can't share private keys.

General question 2

In the "Alice and Bob" example in SMPC, does the third-party indicate one of Alice or Bob? So, is it a sort of HE because we can think of the data Alice holds as the private key for the original data holder?

Simulation study

In Lesson 4, I learned several important privacy protection methods(DP, HE, SMPC). Important thing is thinking about how to combine them in real life, rather than using only one of technique,. So, I've made several virtual situations to clarify when each methods(DP, HE, SMPC) are appropriate and when some of them should not be used. Mentors' opinions on my thoughts will be helpful.

Situations

I'll use the term "communication" for the number of times each clients send a message. Consider when each clients must send their messages multiple times(communications), e.g. Federated Learning setting.

Single input source

• DP 🥉 We can not apply Law of Large numbers. the output may have large variance :(
• HE 🥈 It is safe. But there is a huge computation budget to deal with encrypted message especially when we want to operate non-linear computation (compared to SMPC).
• SMPC 🥇 Moderate

Multiple input sources and Single communication

• HE 🥉 Cannot share private keys(general question 1)
• SMPC 🥈 high budget for communication
• DP 🥇 moderate

Multiple input sources and Multiple communications

• HE 🥉 Cannot share private keys(general question 1)
• SMPC🥈: high budget for communication
• DP🥈: For the clients whose inputs don't fluctuate pretty much, I think we can estimate the input value with low variance if there were enough communications. How can we handle this problem?

[ZSoumia]

General Question 1:

To the best of my knowledge it is possible to perform arithmetic operations on ciphertexts encrypted under different keys and it's called Multi-Key Homomorphic Encryption (MKHE).

General Question2 :

Can you explain what do you mean by the original data holder ? The core idea of SMPC is that you have multiple data holders that can contribute in a computation and only a specific party will know the result of this computation without those paticipating parties learning anything about the different data parts that any of the participants has.

[vrvrv]

Thanks @ZSoumia! I think I should check that paper you shared! Trask gave a situation where someone(original data holder) wants to send the integer he holds, say 5. He splitted the integer by -1 and 6 and then sends each integers to Alice and Bob. Finally, the reciptant who will receive the data Alice and Bob holding (-1 and 6) can induce the original data(5). If I understood correctly, at least one of Alice and Bob will be the third party. Is it right?

[znreza]

For General Question 1: Please check the link @ZSoumia shared.

For General Question 2: In SMPC, the purpose of having a third-party is to limit the participants to obtain the ability to "guess" or trace back to the original data. Therefore, Alice or Bob being the third-party will give them an unfair advantage. Based on my understanding of SMPC, the third-party should not be any of the share holders of the data, neither the original data owner. Please someone correct me if my understanding is wrong :)