Generic Decoding of Restricted Errors

Sebastian Bitzer; Alessio Pavoni; Violetta Weger; Paolo Santini; Marco Baldi; Antonia Wachter-Zeh

doi:10.1109/ISIT54713.2023.10206983

Generic Decoding of Restricted Errors

Sebastian Bitzer, Alessio Pavoni, Violetta Weger, Paolo Santini, Marco Baldi, Antonia Wachter-Zeh

Associate Professorship of Coding and Cryptography

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

3 Scopus citations

Abstract

Several recently proposed code-based cryptosystems base their security on a slightly generalized version of the classical (syndrome) decoding problem. Namely, in the so-called restricted (syndrome) decoding problem, the error values stem from a restricted set. In this paper, we propose new generic decoders, that are inspired by subset sum solvers and tailored to the new setting. The introduced algorithms take the restricted structure of the error set into account in order to utilize the representation technique efficiently. This leads to a considerable decrease in the security levels of recently published code-based cryptosystems.

Original language	English
Title of host publication	2023 IEEE International Symposium on Information Theory, ISIT 2023
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	246-251
Number of pages	6
ISBN (Electronic)	9781665475549
DOIs	https://doi.org/10.1109/ISIT54713.2023.10206983
State	Published - 2023
Event	2023 IEEE International Symposium on Information Theory, ISIT 2023 - Taipei, Taiwan, Province of China Duration: 25 Jun 2023 → 30 Jun 2023

Publication series

Name	IEEE International Symposium on Information Theory - Proceedings
Volume	2023-June
ISSN (Print)	2157-8095

Conference

Conference	2023 IEEE International Symposium on Information Theory, ISIT 2023
Country/Territory	Taiwan, Province of China
City	Taipei
Period	25/06/23 → 30/06/23

Access to Document

10.1109/ISIT54713.2023.10206983

Cite this

Bitzer, S., Pavoni, A., Weger, V., Santini, P., Baldi, M., & Wachter-Zeh, A. (2023). Generic Decoding of Restricted Errors. In 2023 IEEE International Symposium on Information Theory, ISIT 2023 (pp. 246-251). (IEEE International Symposium on Information Theory - Proceedings; Vol. 2023-June). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT54713.2023.10206983

@inproceedings{46193ea783f4463a8bff1b61dd1589ed,

title = "Generic Decoding of Restricted Errors",

abstract = "Several recently proposed code-based cryptosystems base their security on a slightly generalized version of the classical (syndrome) decoding problem. Namely, in the so-called restricted (syndrome) decoding problem, the error values stem from a restricted set. In this paper, we propose new generic decoders, that are inspired by subset sum solvers and tailored to the new setting. The introduced algorithms take the restricted structure of the error set into account in order to utilize the representation technique efficiently. This leads to a considerable decrease in the security levels of recently published code-based cryptosystems.",

author = "Sebastian Bitzer and Alessio Pavoni and Violetta Weger and Paolo Santini and Marco Baldi and Antonia Wachter-Zeh",

note = "Publisher Copyright: {\textcopyright} 2023 IEEE.; 2023 IEEE International Symposium on Information Theory, ISIT 2023 ; Conference date: 25-06-2023 Through 30-06-2023",

year = "2023",

doi = "10.1109/ISIT54713.2023.10206983",

language = "English",

series = "IEEE International Symposium on Information Theory - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "246--251",

booktitle = "2023 IEEE International Symposium on Information Theory, ISIT 2023",

}

Bitzer, S, Pavoni, A, Weger, V, Santini, P, Baldi, M & Wachter-Zeh, A 2023, Generic Decoding of Restricted Errors. in 2023 IEEE International Symposium on Information Theory, ISIT 2023. IEEE International Symposium on Information Theory - Proceedings, vol. 2023-June, Institute of Electrical and Electronics Engineers Inc., pp. 246-251, 2023 IEEE International Symposium on Information Theory, ISIT 2023, Taipei, Taiwan, Province of China, 25/06/23. https://doi.org/10.1109/ISIT54713.2023.10206983

Generic Decoding of Restricted Errors. / Bitzer, Sebastian; Pavoni, Alessio; Weger, Violetta et al.
2023 IEEE International Symposium on Information Theory, ISIT 2023. Institute of Electrical and Electronics Engineers Inc., 2023. p. 246-251 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2023-June).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Generic Decoding of Restricted Errors

AU - Bitzer, Sebastian

AU - Pavoni, Alessio

AU - Weger, Violetta

AU - Santini, Paolo

AU - Baldi, Marco

AU - Wachter-Zeh, Antonia

PY - 2023

Y1 - 2023

N2 - Several recently proposed code-based cryptosystems base their security on a slightly generalized version of the classical (syndrome) decoding problem. Namely, in the so-called restricted (syndrome) decoding problem, the error values stem from a restricted set. In this paper, we propose new generic decoders, that are inspired by subset sum solvers and tailored to the new setting. The introduced algorithms take the restricted structure of the error set into account in order to utilize the representation technique efficiently. This leads to a considerable decrease in the security levels of recently published code-based cryptosystems.

AB - Several recently proposed code-based cryptosystems base their security on a slightly generalized version of the classical (syndrome) decoding problem. Namely, in the so-called restricted (syndrome) decoding problem, the error values stem from a restricted set. In this paper, we propose new generic decoders, that are inspired by subset sum solvers and tailored to the new setting. The introduced algorithms take the restricted structure of the error set into account in order to utilize the representation technique efficiently. This leads to a considerable decrease in the security levels of recently published code-based cryptosystems.

UR - http://www.scopus.com/inward/record.url?scp=85171449492&partnerID=8YFLogxK

U2 - 10.1109/ISIT54713.2023.10206983

DO - 10.1109/ISIT54713.2023.10206983

M3 - Conference contribution

AN - SCOPUS:85171449492

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 246

EP - 251

BT - 2023 IEEE International Symposium on Information Theory, ISIT 2023

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2023 IEEE International Symposium on Information Theory, ISIT 2023

Y2 - 25 June 2023 through 30 June 2023

ER -

Generic Decoding of Restricted Errors

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this