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

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. [ABSTRACT FROM AUTHOR]

Copyright of Advances in Mathematics of Communications is the property of American Institute of Mathematical Sciences and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)