International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

A Security Analysis of Restricted Syndrome Decoding Problems

Authors:
Ward Beullens , IBM Research Europe
Pierre Briaud , Simula UiB
Morten Øygarden , Simula UiB
Download:
DOI: 10.62056/a06cy7qiu
URL: https://cic.iacr.org//p/1/3/33
Search ePrint
Search Google
Abstract:

Restricted syndrome decoding problems (R-SDP and R-SDP($G$)) provide an interesting basis for post-quantum cryptography. Indeed, they feature in CROSS, a submission in the ongoing process for standardizing post-quantum signatures.

This work improves our understanding of the security of both problems. Firstly, we propose and implement a novel collision attack on R-SDP($G$) that provides the best attack under realistic restrictions on memory. Secondly, we derive precise complexity estimates for algebraic attacks on R-SDP that are shown to be accurate by our experiments. We note that neither of these improvements threatens the updated parameters of CROSS.

BibTeX
@article{cic-2024-34844,
  title={A Security Analysis of Restricted Syndrome Decoding Problems},
  journal={cic},
  publisher={International Association for Cryptologic Research},
  volume={1, Issue 3},
  url={https://cic.iacr.org//p/1/3/33},
  doi={10.62056/a06cy7qiu},
  author={Ward Beullens and Pierre Briaud and Morten Øygarden},
  year=2024
}