Classic McEliece is one of the three code-based candidates in the fourth round of the NIST post-quantum cryptography standardization process in the Key Encapsulation Mechanism category. As such, its decapsulation algorithm is used to recover the session key associated with a ciphertext using the private key. In this article, we propose a new side-channel attack on the syndrome computation in the decapsulation algorithm that recovers the private key, which consists of the private Goppa...

We present a new distinguisher for alternant and Goppa codes, whose complexity is subexponential in the error-correcting capability, hence better than that of generic decoding algorithms. Moreover it does not suffer from the strong regime limitations of the previous distinguishers or structure recovery algorithms: in particular, it applies to the codes used in the Classic McEliece candidate for postquantum cryptography standardization. The invariants that allow us to distinguish are graded...

We introduce a novel algebraic approach for attacking the McEliece cryptosystem which is currently at the $4$-th round of the NIST competition. The contributions of the article are twofold. (1) We present a new distinguisher on alternant and Goppa codes working in a much broader range of parameters than \cite{FGOPT11}. (2) With this approach we also provide a polynomial--time key recovery attack on alternant codes which are distinguishable with the distinguisher \cite{FGOPT11}. ...

In this work, we propose the first post-quantum UC-commitment scheme in the Global Random Oracle Model, where only one non-programmable random oracle is available. The security of our proposal is based on two well-established post-quantum hardness assumptions from coding theory: The Syndrome Decoding and the Goppa Distinguisher. We prove that our proposal is perfectly hiding and computationally binding. The scheme is secure against static malicious adversaries.

Strong designated verifier signatures make the message authenticated only to a designated person called the designated verifier while privacy of the signer's identity is preserved. This primitive is useful in scenarios that authenticity, signer ambiguity and signer's privacy are required simultaneously such as electronic voting and tendering. To have quantum-attack-resistant strong designated verifier signatures as recommended in National Institute of Standards and Technology internal report...

Concurrent signatures allow two entities to generate two signatures in such a way that both signatures are ambiguous till some information is revealed by one of the parties. This kind of signature is useful in auction protocols and a wide range of scenarios in which involving participants are mutually distrustful. In this paper, to have quantum-attack-resistant concurrent signatures as recommended by National Institute of Standards and Technology (NISTIR 8105), the first concurrent signature...

Signatures with partially message recovery in which some parts of messages are not transmitted with signatures to make them shorter are useful where bandwidth is one of the crucial concern and especially in case of signing short messages in applications such as time stamping, certified email services and identitybased cryptosystems. In this paper, to have quantum-attackresistant short signatures, a signature scheme with partially message recovery from coding theory is proposed. The security...

We present a polynomial time structural attack against the McEliece system based on Wild Goppa codes from a quadratic finite field extension. This attack uses the fact that such codes can be distinguished from random codes to compute some filtration, that is to say a family of nested subcodes which will reveal their secret algebraic description.

The Goppa Code Distinguishing (GD) problem consists in distinguishing the matrix of Goppa code from a random matrix. Up to now, it was widely believed that this problem is computationally hard. The hardness of this problem was a mandatory assumption to prove the security of code-based cryptographic primitives like McEliece's cryptosystem. We present a polynomial time distinguisher for alternant and Goppa codes of high rate over any field. The key ingredient is an algebraic technique already...

We implement one-out-of-two bit oblivious transfer (OT) based on the assumptions used in the McEliece cryptosystem: the hardness of decoding random binary linear codes, and the difficulty of distinguishing a permuted generating matrix of Goppa codes from a random matrix. To our knowledge this is the first OT reduction to these problems only.

McEliece is one of the oldest known public key cryptosystems. Though it was less widely studied that RSA, it is remarkable that all known attacks are still exponential. It is widely believed that code-based cryptosystems like McEliece does not allow practical digital signatures. In the present paper we disprove this belief and show a way to build a practical signature scheme based on coding theory. It's security can be reduced in the random oracle model to the well-known {\em syndrome...