Paper 2023/1533

On Linear Equivalence, Canonical Forms, and Digital Signatures

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.