Paper 2025/1665 Original: eprint.iacr.org/2025/1665 ↗

Threshold Public-Key Encryption: Definitions, Relations, and CPA-to-CCA Transforms

Abstract

Threshold public-key encryption (TPKE) allows $t$ out of $k$ parties to jointly decrypt a ciphertext, while ensuring confidentiality against any coalition of $t-1$ parties. Despite its long history and ongoing standardisation efforts, there has not been a dedicated study on its basic security notions, and a handful of variations are currently in use. We initiate the systematic study of TPKE confidentiality and develop relations between notions contrasting indistinguishability (IND) vs. simulatability (SIM), passive (CPA) vs. active (CCA) attacks, and static vs. adaptive corruptions. One of our insights is that security under maximal corruptions does not imply security under fewer corruptions when the adversary has access to partial decryptions on challenge ciphertexts. Maximal corruption was adopted by a significant portion of prior works, and this calls for cautious interpretation when using such a notion. We complement our study by providing two generic CPA-to-CCA transforms for TPKE. The first is effectively the Naor--Yung transform, for which we fix a gap in prior work by requiring the underlying TPKE to achieve semi-malicious CPA security, where the adversary can choose randomness for non-challenge ciphertexts. Our second transform applies to any CPA secure TPKE in the random oracle model. We abstract the underlying technique as a standalone novel primitive called non-interactive proof of randomness (NIPoR), and we provide a simple construction from straightline extractable non-interactive zero-knowledge proofs and commitments, which we consider of independent interest.