Tiresias: Large Scale, Maliciously Secure Threshold Paillier

Abstract

We address threshold Paillier encryption where a set of parties collectively holds the secret decryption key through a secret sharing scheme. We present an improved distributed key generation protocol that achieves malicious security under the decisional composite residuosity assumption alone, rather than non-standard assumptions.

Key contributions include novel reduction techniques connecting zero-knowledge proof soundness to factoring, batching capabilities for threshold Paillier decryption in fully distributed settings, and practical implementation supporting up to 1000 parties.

Performance metrics show approximately 50 decryptions per second across 100 parties and 3.6 decryptions per second with 1000 parties on EC2 C6i machines.

The work aims to make threshold Paillier schemes practical for large-scale deployments by shifting computational bottlenecks from verification to plaintext reconstruction.