A Security Analysis of Restricted Syndrome Decoding Problems

ePrint Report: A Security Analysis of Restricted Syndrome Decoding Problems

Ward Beullens, Pierre Briaud, Morten Øygarden

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 …

analysis cryptography decoding eprint report feature indeed post-quantum post-quantum cryptography problems process quantum quantum cryptography report restricted sdp security security analysis signatures submission syndrome understanding work