Is it possible to implement Paillier joint decryption on the high-level interface of MP-SPDZ?

[linen101]

Hi Marcel,

I was looking on the threshold version of paillier cryptosystem from here where multiple parties hold sharings of the secret key used in Paillier. The high-level idea is the following: to jointly decrypt a ciphertext, first, each party computes their partial decryption of the ciphertext using their share of the key and reveals the obtained value, and then the parties agrregate their partial decryptions and with some extra public computation over the group they obtain the message.

I am interested in implementing the decryption phase for benchmark purposes only, assuming that the key set up phase has been performed. I find trouble though implementing this in MP-SPDZ mainly beacuse of the following.

• spdz maps integers to prime field elements or Z_2k ring elements while paillier maps integers to Z_n and Z_n^2 where n is a composite of two primes.
• spdz prime field is much smaller than paillier group (usually 2048 bit lenght)

I was thinking something like this (of course this is not correct) with additive secret sharing in the malicious setting.

def joint_decryption(c, n, shared_key, inv_theta):
    shared_key = sint(shared_key)
    c_exp = ((c) ** shared_key) 
    c_exp_rev = c_exp.reveal()
    c_exp_rev_mod = c_exp_rev % n**2
    c_exp_rev_mod_L = (c_exp_rev_mod - cint(1) // n)
    m = (c_exp_rev_mod_L * inv_theta) % n
    return m

c = cint(2627728219289497236)
n = cint(2754706117)
s = (1156700780489019724)
th = cint(2664777559)    

m = joint_decryption(c, n, s, th)

Am I missing something obvious?

(Sorry if the question is not relevant at all)

[TLDR] The protocol with additive secret sharing works as follows:

1. Key generation: Choose two equal lengthed strong primes p, q s.t. p = 2p' + 1 and q = 2q' + 1 where p', q' are primes. Set n = pq. Set the generator g as g = n+1. The secret key is sk = φ(n) = (p-1)(q-1). Choose β from the multiplicative group of Zn and set θ = β φ(n) mod n. β is the blinding factor for the secret key. θ does not leak anything about sk since it can be any element of the group. The public key is the pair (n,θ). The blinded secret key is additively shared among the parties over the group Z_{nφ(n)}, each party Pi holds a share s_i.

2. Encryption: The encryption phase works as in the original scheme, i.e. it maps the private message and the private randomness from Z_n to Z_n^2. c = Enc_pk (x,r) = (n+1)^x r^n mod n^2

3. The decryption works as follows: a. Each party computes the partial decryption c_i = c^{sk_i} and reveals it to the other parties. b. The parties jointly compute Π c_i = c^{βφ(n) c. The parties obtain m as 1/n (c^{β φ(n) } mod n^2 - 1) θ^{-1} mod n

[mkskeller]

MP-SPDZ doesn't implement several aspects that would be needed here. Not only is the ciphertext domain not supported, but you would need to deal with a domain of unknown size (for the shared keys). There is a paper for threshold Paillier (https://eprint.iacr.org/2019/1136.pdf) whose implementation is here: https://github.com/TNO-MPC/protocols.distributed_keygen

[linen101]

Hi. thanks for the quick reply! I understand that It would not be possible to implement joint paillier decryption phase even if we assumed a trusted dealer for the key generation phase of Paillier, right?

[mkskeller]

Not absolutely impossible, but there is a lot missing

[linen101]

I see, thanks a lot for the clarifications!