Multi Party Computation From Threshold Homomorphic Function in Semi-honest setting

Notation: m' is the ciphertext on encrypting m

Threshold homomorphic encryption is a homomorphic encryption scheme where t (threshold) parties alone cannot decrypt the secret. Decrypt algorithm takes common input m' and public key pk and secret input sk_i from party p_i (secret key is distributed among all parties) decrypts m' and discloses m to all parties.

PrivateDecrypt

PrivateDecrypt is a decryption sub-protocol that decrypts an encryption m' in such a way that only one particular participant learns the message. It is implemented in the following way:

 Let the intended party to receive decrypted message be p_i.

 1. p_i chooses a random value d and broadcasts d'.

 2. All the parties then compute e' = m' + d' and call Decrypt.

 3. Decrypt discloses the message e to all parties.

But only p_i can know original message m from the operation m = e - d.

  

Additive secret sharing

All participating parties know a' = ENC(a). They want to secret share a'.

 1. Each party p_i chooses a random value d_i and broadcasts d_i'.

 2. All parties compute d' such that d' = ∑d_i'.

 3. All parties compute e'=a' + d' and call Decrypt.

 4. Fix an ordering among parties. The first party in the order computes its share as a_i' = e' - d_i', a_i = e - d_i. Rest of the parties compute -d_j', -d _j as their share.

 Thus if all parties add their respective shares which is e'- d' = a'.

Multiplication protocol

The goal of this protocol is given two encryptions a', b' we have to share (ab)' among n parties.

 1. All parties additively secret share a'.

 2. Then every party multiplies a_i with b'.

 3. By the second homomorphic property of constant multiplication all parties together can compute (ab)' .