Simona Etinski – Generic Syndrome Decoding Problem and its Application to Cryptography

Syndrome decoding problem is one of the central problems in coding theory as well as in code-based cryptography. The problem is known to be NP-complete and, for conveniently chosen parameters, exponentially hard for both classical and quantum algorithms. As such, it is proposed as a basis of classical protocols resistant to quantum attacks, i.e., post-quantum protocols. The main drawback of already existing protocols is the lack of efficiency, which is a major obstacle to using them in practice. In this work, we thus aim to improve the efficiency of a well-known Stern signature scheme by modifying the underlying syndrome decoding problem. More precisely, we first generalize the syndrome decoding problem and then aim to find a version of the problem, as well as its optimal parameters, that yield a shorter Stern’s signature.