Paper 2023/1533

On Linear Equivalence, Canonical Forms, and Digital Signatures

Tung Chou, Academia Sinica
Edoardo Persichetti, Florida Atlantic University
Paolo Santini, Marche Polytechnic University

The LESS signature scheme, introduced in 2020, represents a fresh research direction to obtain practical code-based signatures. LESS is based on the linear equivalence problem for codes, and the scheme is entirely described using matrices, which define both the codes, and the maps between them. It makes sense then, that the performance of the scheme depends on how efficiently such objects can be represented. In this work, we investigate canonical forms for matrices, and how these can be used to obtain very compact signatures. We present a new notion of equivalence for codes, and prove that it reduces to linear equivalence; this means there is no security loss when applying canonical forms to LESS. Additionally, we flesh out a potential application of canonical forms to cryptanalysis, and conclude that this does not improve on existing attacks, for the regime of interest. Finally, we analyze the impact of our technique, showing that it yields a drastic reduction in signature size when compared to the LESS submission, resulting in the smallest sizes for code-based signature schemes based on zero-knowledge.

Available format(s)
Public-key cryptography
Publication info
Code Equivalence; Canonical Forms; LESS
Contact author(s)
blueprint @ crypto tw
epersichetti @ fau edu
p santini @ staff univpm it
2023-10-09: approved
2023-10-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Tung Chou and Edoardo Persichetti and Paolo Santini},
      title = {On Linear Equivalence, Canonical Forms, and Digital Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1533},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.