Paper 2023/998

Tiresias: Large Scale, Maliciously Secure Threshold Paillier

Offir Friedman, dWallet labs
Avichai Marmor, dWallet labs
Dolev Mutzari, dWallet labs
Yehonatan C. Scaly, dWallet labs
Yuval Spiizer, dWallet labs
Avishay Yanai

In the threshold version of Paillier's encryption scheme, a set of parties collectively holds the secret decryption key through a secret sharing scheme. Whenever a ciphertext is to be decrypted, the parties send their decryption shares, which are then verified for correctness and combined into the plaintext. The scheme has been widely adopted in various applications, from secure voting to general purpose MPC protocols. However, among the handful existing proposals for a maliciously secure scheme, one must choose between an efficient implementation that relies on non-standard assumptions or a computationally expensive implementation that relies on widely acceptable assumptions. In this work, we show that one can enjoy the benefits of both worlds. Specifically, we adjust a scheme by Damgard et al. (Int. J. Inf. Secur. 2010) to get a practical distributed key generation (DKG). While the original scheme was only known to be secure under ad-hoc non-standard assumptions, we prove that the adjusted scheme is in fact secure under the decisional composite residuosity (DCR) assumption alone, required for the semantic security of the Pallier encryption scheme itself. This is possible thanks to a novel reduction technique, from the soundness of a zero-knowledge proof of equality of discrete logs, to the factoring problem. Furthermore, we use similar ideas to prove that batching techniques by Aditya et al. (ACNS 2004), which allows a prover to batch several statements into a single proof, can be applied to our adjusted scheme. This enables a batched threshold Paillier decryption in the fully distributed setting for the first time. Until now, verifying that a decryption share is correct was the bottleneck of threshold Paillier schemes and hindered real world deployments (unless one is willing to rely on a trusted dealer). Our work accumulates to shifting the bottleneck back to the plaintext reconstruction, just like in the semi-honest setting, and render threshold Paillier practical for the first time, supporting large scale deployments. We exemplify this shift by implementing the scheme and report our evaluation with up to 1000 parties, in the dishonest majority setting. For instance, over an EC2 C6i machine, we get a throughput of about 50 and 3.6 decryptions per second, when run over a network of 100 and 1000 parties, respectively.

Available format(s)
Cryptographic protocols
Publication info
Additive Homomorphic EncryptionPaillier EncryptionThreshold EncryptionBatched ZK Arguments
Contact author(s)
offir @ dwalletlabs com
avichai @ dwalletlabs com
dolev @ dwalletlabs com
yehonatan @ dwalletlabs com
yuval @ dwalletlabs com
ay yanay @ gmail com
2024-02-17: last of 5 revisions
2023-06-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Offir Friedman and Avichai Marmor and Dolev Mutzari and Yehonatan C. Scaly and Yuval Spiizer and Avishay Yanai},
      title = {Tiresias: Large Scale, Maliciously Secure Threshold Paillier},
      howpublished = {Cryptology ePrint Archive, Paper 2023/998},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.