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

Chris Brzuska; Michael Klooß; Ivy K. Y. Woo

Paper 2025/1665

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

Chris Brzuska

, Aalto University

Michael Klooß

, Karlsruhe Institute of Technology

Ivy K. Y. Woo

, Aalto University

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.

Note: This is the full version of a publication in PKC 2026 with the same title, containing additional proofs in the appendices. 2026-07-17: Fixed typos and small bugs. 2026-04-13: Added table of properties and notations. Refined discussions. Updated Appendix G preliminaries and proofs. Fixed typos. 2025-10-28: Strengthened definition of NIPoR. Simplified CPA-to-CCA transformation. Extended related work discussion. Fixed typos and small bugs. General editorial refinements. 2025-09-13: First eprint version.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: A major revision of an IACR publication in PKC 2026
DOI: 10.1007/978-3-032-26740-5_6
Keywords: threshold PKE separations CPA-to-CCA transforms non-interactive proof of randomness partial decryption queries
Contact author(s): chris brzuska @ aalto fi
klooss @ mail informatik kit edu
ivy woo @ aalto fi
History: 2026-07-17: last of 3 revisions; 2025-09-13: received; See all versions
Short URL: https://ia.cr/2025/1665
License: CC BY

BibTeX

@misc{cryptoeprint:2025/1665,
      author = {Chris Brzuska and Michael Klooß and Ivy K. Y. Woo},
      title = {Threshold Public-Key Encryption:  Definitions, Relations, and {CPA}-to-{CCA} Transforms},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1665},
      year = {2025},
      doi = {10.1007/978-3-032-26740-5_6},
      url = {https://eprint.iacr.org/2025/1665}
}