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 hold a share of the secret decryption key. Whenever a ciphertext is to be decrypted, the parties sends 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 handful proposals for a maliciously secure scheme, one must choose between an efficient implementation that relies on non-standard assumptions or an infeasible one that relies on widely acceptable assumptions. In this work, we present a new protocol that combines the benefits of both worlds. We depart from the efficient scheme, which was proven secure relying on non-standard assumptions, and for the first time, prove that it is secure under standard assumptions only. 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, our simple and efficient proof supports batching, and hence enables batched threshold Paillier decryption for the first time. Until now, verifying that a decryption share is correct was the bottleneck of threshold Paillier schemes, and prevented its implementation in practice (unless one is willing to rely on a trusted dealer). Our new proof and batching techniques shift that 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 implemented our 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
2023-06-27: approved
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.