A Security Analysis of Restricted Syndrome Decoding Problems

Authors:
Open Access
Publisher website
Google Scholar
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.

This publication has 15 references indexed in Scilit: