International Association
for Cryptologic Research

Threshold public-key encryption (TPKE) allows $t$ out of $k$ parties to jointly decrypt, but any $t-1$ subset obtains no information on the underlying plaintext. The ongoing standardisation efforts on threshold primitives by NIST make it a pressing question to understand TPKE security notions, which, perhaps surprisingly, have remained varied.

We systematically develop what we view as minimal security properties for TPKE, formalise these into indistinguishability-based and simulation-based security notions, and establish implications and separations between different variants. One of our insights is that the common belief of maximal corruption implying the same security notion under fewer corruption is generally false, and the importance of partial decryptions on challenge ciphertexts is often neglected. Concretely, we design a (contrived) scheme which is CCA-simulation-secure under maximal corruptions, but not IND-CPA-secure under arbitrary corruptions. Our scheme is so that a random, initially hidden subset of $t-1$ parties can jointly decrypt and thus trivially insecure, but which can still be proven secure when partial decryption queries are disallowed.

To show that our security notions are achievable, we prove that threshold ElGamal (Desmedt-Frankel, 1989) achieves simulation-CPA-security under DDH, borrowing techniques from a concurrent work. We also revisit CPA-to-CCA transforms in the style of Naor and Yung (NY) and discover that, generically, NY does not upgrade CPA to CCA security for TPKE. We provide two alternatives: (1) We propose and construct a novel building block called non-interactive proofs of randomness (NIPoR) in the random oracle model, and show that NIPoR allows a generic CPA-to-CCA transform. (2) We show that assuming the stronger semi-malicious CPA security, NY-style techniques suffice to upgrade to CCA security.