Paper 2026/799

EQuADiSE: Efficient Quantum-safe Adaptive Distributed Symmetric-key Encryption

Abstract

Distributed symmetric-key encryption (DiSE), introduced in CCS' 18, enables threshold versions of traditional (symmetric-key) authenticated encryption. In DiSE, the long-term master secret key is secret-shared among multiple parties following a threshold access structure, and both encryption and decryption are performed in a distributed manner. An adaptively secure DiSE, introduced in INDOCRYPT' 20 tolerates adaptive corruptions of the key-holding parties for arbitrary thresholds, while simultaneously retaining efficient encryption and decryption. Unfortunately, all existing instances of adaptively secure DiSE are either quantum-unsafe (due to their inherent-reliance on discrete log-hard groups), or incur exponential (in the number of parties) online overheads for encryption/decryption. In this paper, we present EQuADiSE -- the first practically efficient, adaptively secure, and plausibly post-quantum secure construction of DiSE that incurs linear (in the number of parties) encryption/decryption overheads. We prove the adaptive security of EQuADiSE in the Quantum Random Oracle model (QROM) based on the Module Learning with Rounding (MLWR) assumption. As a core building block of independent interest, we introduce an MLWR-based distributed pseudorandom function (DPRF) that enjoys adaptive security in the QROM and practically outperforms all existing adaptively secure DPRF constructions in terms of online evaluation time. We present a prototype implementation of EQuADiSE and evaluate its performance. Our experiments demonstrate that EQuADiSE achieves higher online throughput (number of encryptions/decryptions per second) than all prior realizations of DiSE, including quantum-unsafe realizations based on discrete log-hard groups.

Note: An extended abstract of this paper will appear in the proceedings of ESORICS 2026. This is the full version and includes detailed background material and complete security proofs, in particular, the proofs of adaptive security in both the Random Oracle Model (ROM) and the Quantum Random Oracle Model (QROM). We thank the anonymous reviewers of ESORICS 2026 for their valuable feedback, which has been incorporated into this version. In addition, this full version includes comparison of the communication overheads of existing DPRF constructions.