Paper 2023/1533

On Linear Equivalence, Canonical Forms, and Digital Signatures

Abstract

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.