Cryptology ePrint Archive: Report 2022/509

Lattice-Based Signature with Efficient Protocols, Revisited

Corentin Jeudy and Adeline Roux-Langlois and Olivier Sanders

Abstract: Digital signature is an essential primitive in cryptography, which can be used as the digital analogue of handwritten signatures but also as a building block for more complex systems. In the latter case, signatures with specific features are needed, so as to smoothly interact with the other components of the systems, such as zero-knowledge proofs. This has given rise to so-called signatures with efficient protocols, a versatile tool that has been used in countless applications. Designing such signatures is however quite difficult, in particular if one wishes to withstand quantum computing. We are indeed aware of only one post-quantum construction, proposed by Libert et al. at Asiacrypt'16, yielding very large signatures and proofs. In this paper, we propose a new construction that can be instantiated in both standard lattices and structured ones, resulting in each case in dramatic performance improvements. In particular, the size of a proof of message-signature possession, which is one of the main metrics for such schemes, can be brought down to less than 650 KB. As our construction retains all the features expected from signatures with efficient protocols, it can be used as a drop-in replacement in all systems using them, which mechanically improves their own performance, and has thus an impact on many applications.

Category / Keywords: public-key cryptography / Lattice-Based Cryptography, Signature, Efficient Protocols, Privacy

Date: received 28 Apr 2022, last revised 12 May 2022

Contact author: corentin jeudy at irisa fr

Available format(s): PDF | BibTeX Citation

Version: 20220512:151519 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]