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
Abstract

Given two linear codes, the code equivalence problem asks to find an isometry mapping one code into the other. The problem can be described in terms of group actions and, as such, finds a natural application in signatures derived from a Zero-Knowledge Proof system. A recent paper, presented at Asiacrypt 2023, showed how a proof of equivalence can be significantly compressed by describing how the isometry acts only on an information set. Still, the resulting signatures are far from being optimal, as the size for a witness to this relation is still significantly larger than the theoretical lower bound of $2\lambda$. In this paper, we fill this gap and propose a new notion of equivalence, which leads to a drastically reduced witness size. In particular, for many cases, the size obtained is exactly the optimal one given by the lower bound. We do this by introducing the framework of canonical forms, that is, representatives for classes of codes which are equivalent under some notion of equivalence. We propose new notions of equivalence which encompass and further extend all the existing ones: this allows to identify broader classes of equivalent codes, for which the equivalence can be proved with a very compact witness. We associate these new notions to a specific problem, called Canonical Form Linear Equivalence Problem (CF-LEP), which we show to be as hard as the original one, providing reductions in both ways. As an added consequence, we show how this reduction leads to a new solver for the code equivalence problem, which is the fastest solver when the finite field size is large enough. Finally, we analyze the impact of our technique, showing that it yields a remarkable reduction in signature size when compared to the LESS submission. Our variant is able to obtain very compact signatures, around 2 KB or less, which are among the smallest in the post-quantum ecosystem.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
Code Equivalence; Canonical Forms; LESS
Contact author(s)
blueprint @ crypto tw
epersichetti @ fau edu
p santini @ staff univpm it
History
2024-06-03: revised
2023-10-07: received
See all versions
Short URL
https://ia.cr/2023/1533
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1533,
      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},
      url = {https://eprint.iacr.org/2023/1533}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.