Code-based Signatures from New Proofs of Knowledge for the Syndrome Decoding Problem. (arXiv:2201.05403v1 [cs.CR])

In this paper, we study code-based signatures constructed from Proof of
Knowledge (PoK). This line of work can be traced back to Stern who introduces
the first efficient PoK for the syndrome decoding problem in 1993. Afterward,
different variations were proposed in order to reduce signature's size. In
practice, obtaining a smaller signature size relies on the interaction of two
main considerations: (i) the underlying protocol and its soundness error and
(ii) the type of optimizations which are compatible with …

code problem signatures syndrome