Paper 2023/836

Covercrypt: an Efficient Early-Abort KEM for Hidden Access Policies with Traceability from the DDH and LWE

Théophile Brézot, Cosmian
Paola de Perthuis, Cosmian, École Normale Supérieure - PSL
David Pointcheval, École Normale Supérieure - PSL

Attribute-Based Encryption (ABE) is a very attractive primitive to limit access according to specific rights. While very powerful instantiations have been offered, under various computational assumptions, they rely on either classical or post-quantum problems, and are quite intricate to implement, generally resulting in poor efficiency; the construction we offer results in a powerful efficiency gap with respect to existing solutions. With the threat of quantum computers, post-quantum solutions are important, but not yet tested enough to rely on such problems only. We thus first study an hybrid approach to rely on the best of the two worlds: the scheme is secure if at least one of the two underlying assumptions is still valid (i.e. the DDH and LWE). Then, we address the ABE problem, with a practical solution delivering encrypted contents such that only authorized users can decrypt, without revealing the target sets, while also granting tracing capabilities. Our scheme is inspired by the Subset Cover framework where the users' rights are organized as subsets and a content is encrypted with respect to a subset covering of the target set. Quite conveniently, we offer black-box modularity: one can easily use any public-key encryption of their choice, such as Kyber, with their favorite library, to combine it with a simple ElGamal variant of key encapsulation mechanisms, providing strong security guarantees.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. ESORICS 2023
Key Encapsulation MechanismPost-QuantumSubset CoverHidden Access PolicyTraceabilityHybridization
Contact author(s)
paola de perthuis @ ens fr
david pointcheval @ ens fr
2023-09-19: last of 5 revisions
2023-06-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Théophile Brézot and Paola de Perthuis and David Pointcheval},
      title = {Covercrypt: an Efficient Early-Abort KEM for Hidden Access Policies with Traceability from the DDH and LWE},
      howpublished = {Cryptology ePrint Archive, Paper 2023/836},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.