Paper 2023/847

A New Formulation of the Linear Equivalence Problem and Shorter LESS Signatures

Edoardo Persichetti, Florida Atlantic University, Sapienza University of Rome
Paolo Santini, Marche Polytechnic University

The Linear Equivalence Problem (LEP) asks to find a linear isometry between a given pair of linear codes; in the Hamming weight this is known as a monomial map. LEP has been used in cryptography to design the family of LESS signatures, which includes also some advanced schemes, such as ring and identity-based signatures. All of these schemes are obtained applying the Fiat-Shamir transformation to a Sigma protocol, in which the prover's responses contain a description of how the monomial map acts on all code coordinates; such a description constitutes the vast majority of the signature size. In this paper, we propose a new formulation of LEP, which we refer to as Information-Set (IS)-LEP. Exploiting IS-LEP, it is enough for the prover to provide the description of the monomial action only on an information set, instead of all the coordinates. Thanks to this new formulation, we are able to drastically reduce signature sizes for all LESS signature schemes, without any relevant computational overhead. We prove that IS-LEP and LEP are completely equivalent (indeed, the same problem), which means that improvement comes with no additional security assumption, either.

Note: Minor differences from previous version (e.g., fixed some typos)

Available format(s)
Public-key cryptography
Publication info
A minor revision of an IACR publication in ASIACRYPT 2023
Code EquivalenceSignaturesGroup Actions
Contact author(s)
p santini @ staff univpm it
2023-09-21: revised
2023-06-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Edoardo Persichetti and Paolo Santini},
      title = {A New Formulation of the Linear Equivalence Problem and Shorter LESS Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2023/847},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.