Back to the future: simple threshold decryption secure against adaptive corruptions

Victor Shoup

Paper 2025/1578

Back to the future: simple threshold decryption secure against adaptive corruptions

Victor Shoup

, Offchain Labs

Abstract

We present a practical, non-interactive threshold decryption scheme. It can be proven CCA secure with respect to adaptive corruptions in the random oracle model under the decisional Diffie-Hellman assumption. Our scheme, called TDH2a, is a minor modification on the TDH2 scheme presented by Shoup and Gennaro at Eurocrypt 1998, which was proven secure against static corruptions under the same assumptions. The design and analysis of TDH2a are based on a straightforward extension of the simple information-theoretic argument underlying the security of the Cramer-Shoup encryption scheme presented at Crypto 1998. We also present another variant, TDH2abc, which offers a higher degree of backward compatibility with TDH2, allowing one to effectively "hot swap" TDH2abc in to replace TDH2 in a "live" system, without changing the public encryption key, so that any extant ciphertexts remain decryptable.

Note: (1) 2025-09-02: initial post. (2) 2025-09-05: title change, minor edits. (3) 2025-09-09: added variation TDH2abc that provides better backward compatibility with TDH2, minor edits. (4) 2025-09-10: minor edits. (5) 2025-09-12: more related work, minor edits. (6) 2025-09-14: more related work, minor edits. (7) 2025-09-17: minor edits. (8) 2025-12-05: significant modifications to the treatment to erasure-free corruptions, and addition of an appendix that covers simulation-CCA security in depth. (9) 2025-12-07: restructured and simplified the proof of simulation-CCA security. (10) 2025-12-09: moved appendix on simulation-CCA security to the body

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: threshold decryption adaptive corruptions
Contact author(s): victor @ shoup net
History: 2025-12-09: last of 11 revisions; 2025-09-02: received; See all versions
Short URL: https://ia.cr/2025/1578
License: CC BY-NC-ND

BibTeX

@misc{cryptoeprint:2025/1578,
      author = {Victor Shoup},
      title = {Back to the future: simple threshold decryption secure against adaptive corruptions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1578},
      year = {2025},
      url = {https://eprint.iacr.org/2025/1578}
}