Paper 2023/847
A New Formulation of the Linear Equivalence Problem and Shorter LESS Signatures
, Florida Atlantic University, Sapienza University of Rome, Marche Polytechnic UniversityAbstract
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)
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- A minor revision of an IACR publication in ASIACRYPT 2023
- Keywords
- Code EquivalenceSignaturesGroup Actions
- Contact author(s)
- p santini @ staff univpm it
- History
- 2023-09-21: revised
- 2023-06-06: received
- See all versions
- Short URL
- https://ia.cr/2023/847
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/847,
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},
url = {https://eprint.iacr.org/2023/847}
}
