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.
Generic Decoding of Restricted Errors / Bitzer, Sebastian; Pavoni, Alessio; Weger, Violetta; Santini, Paolo; Baldi, Marco; Wachter-Zeh, Antonia. - ELETTRONICO. - (2023), pp. 246-251. (Intervento presentato al convegno 2023 IEEE International Symposium on Information Theory (ISIT 2023) tenutosi a Taipei, Taiwan nel 25-30 June 2023) [10.1109/ISIT54713.2023.10206983].
Generic Decoding of Restricted Errors
Pavoni, Alessio;Santini, Paolo;Baldi, Marco;
2023-01-01
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.