A new one-time signature scheme from syndrome decoding
We describe a one-time signature scheme based on the hardness of the syndrome decoding problem, and prove it secure in the random oracle model. Our proposal can be instantiated on general linear error correcting codes, rather than restricted families like alternant codes for which a decoding trapdoor is known to exist.
Decoding square-free Goppa codes over $\F_p$
We propose a new, efficient decoding algorithm for square-free (irreducible or otherwise) Goppa codes over $\F_p$ for any prime $p$. If the code in question has degree $t$ and its average code distance is at least $(4/p)t + 1$, the proposed decoder can uniquely correct up to $(2/p)t$ errors with high probability. The correction capability is higher if the distribution of error magnitudes is not uniform, approaching or reaching $t$ errors when any particular error value occurs much more often than others or exclusively. This makes the method interesting for (semantically secure) cryptosystems based on the decoding problem for permuted and punctured Goppa codes.