Paper 2022/1449

ParaDiSE: Efficient Threshold Authenticated Encryption in Fully Malicious Model

Shashank Agrawal, Coinbase
Wei Dai, Bain Capital Crypto
Atul Luykx, Google
Pratyay Mukherjee, SupraOracles
Peter Rindal, Visa Research

Threshold cryptographic algorithms achieve robustness against key and access compromise by distributing secret keys among multiple entities. Most prior work focuses on threshold public-key primitives, despite extensive use of authenticated encryption in practice. Though the latter can be deployed in a threshold manner using multi-party computation (MPC), doing so incurs a high communication cost. In contrast, dedicated constructions of threshold authenticated encryption algorithms can achieve high performance. However to date, few such algorithms are known, most notably DiSE (distributed symmetric encryption) by Agrawal et al. (ACM CCS 2018). To achieve threshold authenticated encryption} (TAE), prior work does not suffice, due to shortcomings in definitions, analysis, and design, allowing for potentially insecure schemes, an undesirable similarity between encryption and decryption, and insufficient understanding of the impact of parameters due to lack of concrete analysis. In response, we revisit the problem of designing secure and efficient TAE schemes. (1) We give new TAE security definitions in the fully malicious setting addressing the aforementioned concerns. (2) We construct efficient schemes satisfying our definitions and perform concrete and more modular security analyses. (3) We conduct an extensive performance evaluation of our constructions, against prior ones.

Note: Contains minor edits compared to prior version.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. INDOCRYPT2022
threshold crypto authenticated encryption provable security
Contact author(s)
shashank agraval @ gmail com
me @ wdai us
atul @ luykx be
pratyay85 @ gmail com
peterrindal @ gmail com
2022-11-02: last of 2 revisions
2022-10-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Shashank Agrawal and Wei Dai and Atul Luykx and Pratyay Mukherjee and Peter Rindal},
      title = {ParaDiSE: Efficient Threshold Authenticated Encryption in Fully Malicious Model},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1449},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.