Paper 2024/131

Practical Post-Quantum Signatures for Privacy

Sven Argo, Ruhr University Bochum
Tim Güneysu, Ruhr University Bochum, German Research Centre for Artificial Intelligence
Corentin Jeudy, Orange (France), Univ Rennes, CNRS, IRISA
Georg Land, Ruhr University Bochum
Adeline Roux-Langlois, Normandie Univ, UNICAEN, ENSICAEN, CNRS, GREYC, 14000 Caen, France
Olivier Sanders, Orange (France)

The transition to post-quantum cryptography has been an enormous challenge and effort for cryptographers over the last decade, with impressive results such as the future NIST standards. However, the latter has so far only considered central cryptographic mechanisms (signatures or KEM) and not more advanced ones, e.g., targeting privacy-preserving applications. Of particular interest is the family of solutions called blind signatures, group signatures and anonymous credentials, for which standards already exist, and which are deployed in billions of devices. Such a family does not have, at this stage, an efficient post-quantum counterpart although very recent works improved this state of affairs by offering two different alternatives: either one gets a system with rather large elements but a security proved under standard assumptions or one gets a more efficient system at the cost of ad-hoc interactive assumptions or weaker security models. Moreover, all these works have only considered size complexity without implementing the quite complex building blocks their systems are composed of. In other words, the practicality of such systems is still very hard to assess, which is a problem if one envisions a post-quantum transition for the corresponding systems/standards. In this work, we propose a construction of so-called signature with efficient protocols (SEP), which is the core of such privacy-preserving solutions. By revisiting the approach by Jeudy et al. (Crypto 2023) we manage to get the best of the two alternatives mentioned above, namely short sizes with no compromise on security. To demonstrate this, we plug our SEP in an anonymous credential system, achieving credentials of less than 80 KB. In parallel, we fully implemented our system, and in particular the complex zero-knowledge framework of Lyubashevsky et al. (Crypto'22), which has, to our knowledge, not be done so far. Our work thus not only improves the state-of-the-art on privacy-preserving solutions, but also significantly improves the understanding of efficiency and implications for deployment in real-world systems.

Available format(s)
Public-key cryptography
Publication info
Lattice-Based CryptographySignatureEfficient ProtocolsPrivacyAnonymous Credentials
Contact author(s)
sven argo @ rub de
tim gueneysu @ rub de
corentin jeudy @ orange com
mail @ georg land
adeline roux-langlois @ cnrs fr
olivier sanders @ orange com
2024-01-31: approved
2024-01-30: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sven Argo and Tim Güneysu and Corentin Jeudy and Georg Land and Adeline Roux-Langlois and Olivier Sanders},
      title = {Practical Post-Quantum Signatures for Privacy},
      howpublished = {Cryptology ePrint Archive, Paper 2024/131},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.