Repository logo
Research Outputs
Projects
People
Statistics
  1. Home
  2. HSG CRIS
  3. HSG Publications
  4. A new path to code-based signatures via identification schemes with restricted errors
Details

A new path to code-based signatures via identification schemes with restricted errors

Journal
Advances in Mathematics of Communications
ISSN
1930-5346
ISSN-Digital
1930-5338
Type
journal article
Date Issued
2025
Author(s)
Baldi, Marco
;
Battaglioni, Massimo
;
Chiaraluce, Franco
;
Anna-Lena Horlemann  
;
Persichetti, Edoardo
;
Santini, Paolo
;
Weger, Violetta
DOI
10.3934/amc.2024058
Abstract
In this paper, we introduce a new variant of the syndrome decoding problem (SDP), called restricted SDP (R-SDP), in which the entries of the solution vector live in a fixed subset of the underlying finite field. We prove the NP-completeness of R-SDP via a reduction from SDP and show how this new problem can be employed in identification schemes. We revisit some concepts of classical coding theory in light of this new setting, provide several bounds such as the Gilbert-Varshamov, the Singleton, and the Plotkin bound, and study the behavior of random codes. Resulting from this initial work, several proposals have arisen; in particular, the code-based digital signature scheme named CROSS, which is currently competing within NIST's additional call for post-quantum digital signatures, is based on R-SDP.
Language
English
Keywords
Coding theory
decoding problems
restricted errors
bounds
HSG Classification
contribution to scientific community
Refereed
Yes
Publisher
American Institute of Mathematical Sciences (AIMS)
Volume
19
Number
5
Start page
1360
End page
1381
URL
https://alexandria.unisg.ch/handle/20.500.14171/143191
Subject(s)

computer science

Division(s)

ICS - Institute of Co...

Support
HSG researchers can find instructions here for adding or importing publications (DOI, ORCID). Please send questions to alexandria@unisg.ch

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science

  • Accessibility settings
  • Privacy policy
  • End User Agreement
  • Send Feedback
Repository logo COAR Notify