Paper 2021/096

Gladius: LWR based efficient hybrid public key encryption with distributed decryption

Kelong Cong, Daniele Cozzo, Varun Maram, and Nigel P. Smart


Standard hybrid encryption schemes based on the KEM-DEM framework are hard to implement efficiently in a distributed manner whilst maintaining the CCA security property of the scheme. This is because the DEM needs to be decrypted under the key encapsulated by the KEM, before the whole ciphertext is declared valid. In this paper we present a new variant of the KEM-DEM framework, closely related to Tag-KEMs, which sidesteps this issue. We then present a post-quantum KEM for this framework based on Learning-with-Rounding, which is designed specifically to have fast distributed decryption. Our combined construction of a hybrid encryption scheme with Learning-with-Rounding based KEM, called Gladius, is closely related to the NIST Round 3 candidate called Saber. Finally, we give a prototype distributed implementation that achieves a decapsulation time of 4.99 seconds for three parties.

Note: Clarified an issue which was written in a confusing way before

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in ASIACRYPT 2021
Contact author(s)
kelong cong @ esat kuleuven be
daniele cozzo @ kuleuven be
nigel smart @ kuleuven be
vmaram @ inf ethz ch
2021-08-31: last of 5 revisions
2021-01-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Kelong Cong and Daniele Cozzo and Varun Maram and Nigel P.  Smart},
      title = {Gladius: LWR based efficient hybrid public key encryption with distributed decryption},
      howpublished = {Cryptology ePrint Archive, Paper 2021/096},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.