Welcome to the resource topic for 2023/1533
Title:
On Linear Equivalence, Canonical Forms, and Digital Signatures
Authors: Tung Chou, Edoardo Persichetti, Paolo Santini
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.
ePrint: https://eprint.iacr.org/2023/1533
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .