NP-completeness of the random binary quasi-dyadic coset weight problem and the random binary quasi-dyadic subspace weight problem

Abstract

In 1978, the Syndrome Decoding Problem (SDP) was proven to be NP-complete for random binary codes. Since then, the security of several cryptographic applications relies on its hardness. In 2009, Finiasz extended this result by demonstrating the NP-completeness of certain sub-classes of the SDP (see [9]). In this paper, we prove the NP-completeness of the SDP for a specific family of codes: the random binary quasi-dyadic codes. We use a reduction to the Four Dimensional Matching Problem (proven NP-complete).