Talk:McEliece cryptosystem

Recent DJB papers

anyone updating the article according to this?

http://cr.yp.to/codes/grovercode-20091123.pdf

abstract: McEliece is a subject to Grover code attack on quantum computers, making the attack faster by a square-root. —Preceding unsigned comment added by 90.176.241.199 (talk) 21:40, 25 January 2010 (UTC)

The paper states that 'n', and thus 'k', must be doubled, so this means a four-fold key increase, not a squared! Anyway, note added to article text. Nageh (talk) 10:31, 3 June 2010 (UTC)

INSECURE?

We really need to do something about the line which says the knapsack problem has been proven insecure. All Shamir did in his analysis of Merkle-Hellman was break THEIR construction. If the knapsack problem was broken then we wouldn't be talking about P=NP? There is absolutely no reason to believe that you can't get a good trapdoor out of a knapsack.--Gtg207u 09:46, 10 March 2007 (UTC)

It appears that you posted your comment on the wrong page. The McEliece cryptosytem is based on the difficulty of an error correction problem and not on the difficulty of solving knapsack problems. 85.2.115.82 10:29, 10 March 2007 (UTC)

I didn't post my comment on the wrong page. This is the second paragraph:

"Attempts have been made to cryptanalyze McEliece, but none have been successful. However, the algorithm is never used in practice because of the massive keys and because the ciphertext is twice as large as the plaintext. The similarity between this algorithm and the knapsack problem (which has been proven insecure) also worries some."

Your thinking that I posted on the wrong page seeks to verify my point. It is immediatly unclear how these two things are related. Furthermore, as I stated above, knapsacks are still hard.--Gtg207u 20:06, 10 March 2007 (UTC)

I agree with you that it is unclear how McEliece and the knapsack problem are related. The statement "The similarity between this algorithm and the knapsack problem ... also worries some" is either wrong or a least not properly cited. Therefore I'm removing it. Your claim that there is no reason to believe that you can't get a good trapdoor from knapsacks, however is not justified by the observation that knapsack problems are NP-complete. It is one thing to have a NP complete problem. It is another thing to find a trapdoor based on the same problem. There have been quite a serie of knapsack based cryptosystems that have been broken not just the Merkle-Hellman scheme. This is a valid reason why many researchers are sceptical against proposed cryptosystems using knapsacks. But again, I think this discussion should be on a page describing knapsack based schemes and not here. 85.2.59.190 09:59, 11 March 2007 (UTC)

Well, from what I can see the page is pretty good other than that. So if you're going to remove it then my objections to the page will go with it.--Gtg207u 17:53, 11 March 2007 (UTC)

contradiction

...the algorithm is never used in practice because of the massive keys and because the ciphertext is twice as large as the plaintext. McEliece is used for...

Well, which is it? —porges_(talk) 07:25, 6 April 2007 (UTC)

stub

changed status from crypto-stub to expand. imho the article is not missing necessary information and contains more than a few sentences. i am not sure what to add, so maybe even the "expand" template could be removed. MarioS-de (talk) 09:29, 23 July 2008 (UTC)

23 oct 2008

the McEliece cryptosystem has been cracked/hacked this is the first time. Technische Unversiteit te Eindhoven in the Netherlands have hack/crack it http://www.nu.nl/news/1803064/56/TUE_kraakt_internetbeveiliging_van_de_toekomst.html

 —Preceding unsigned comment added by 145.91.134.29 (talk) 10:34, 23 October 2008 (UTC) 

As usual, news articles lack important details and are confusing. Is this about an implementation of the attack by Bernstein, Lange and Peters that is already mentioned in this wikipedia article, and does it verify their claims? I.e. according to their paper the minimum parameters for 80-bit security would be n=1632, k=1269. Is this still the case? 85.2.54.236 (talk) 20:10, 23 October 2008 (UTC)

Inconsistency in steps for encryption

The Handbook of Applied Cryptography states as part of the encryption algo: "Choose a random binary error vector z of length n having at most t 1’s." whereas McEliece gives "a vector of length n and weight t" which means containing EXACTLY t amount 1's in my book. Should I be wrong please revert my changes, but a number of attacks assume the error-vector to have exactly t error-places, therefore I think I am correct in revising this step. 89.12.179.221 (talk) 11:42, 21 February 2009 (UTC)Ced

You are correct. HAC even contradicts itself in note 8.31(ii) where it states the probability of selecting a sequence 'z' (not vector!) being not in error as $\scriptstyle {\binom {n-t}{k}}/{\binom {n}{k}}$. Nageh (talk) 19:52, 2 June 2010 (UTC)

Polynomial Time Attack on Wild McEliece Over Quadratic Extensions

http://eprint.iacr.org/2014/112.pdf

--131.152.209.79 (talk) 15:02, 19 March 2014 (UTC)

Brute force

The article states that the system can be broken when knowing the secret generator matrix $G$. I tried to find a source for this, but was not able to find one. It is not obvious to me that the referenced algorithm Sardinas–Patterson_algorithm to this problem will in fact solve this. Also, the citation that was given for this fact was a reference to Pattersons-Algorithm, which is something completely different. I think this is wrong. --131.152.209.70 (talk) 12:57, 18 June 2014 (UTC)

The security of the McEliece cryptosystem comes from the proven NP-hard problem that there doesn't exist any decoding algorithms for random linear codes. The private key consist of the matrices $S$ (scramble matrix), $G$ (generator matrix) and $P$ (permutation matrix). These matrices $S$ and $P$ cause the composed generator matrix S*G*P to be a random linear code. If the secret generator matrix $G$ can be obtained from S*G*P, the adversary can use the Sardinas–Patterson_algorithm to decode the message. This algorithm is the decoding algorithm for Goppa codes. Markovisch (talk • contribs) 23:02, 26 March 2017 (UTC)

"Security grows much faster" with key size

From the article

The McEliece cryptosystem has some advantages over, for example, RSA. [...] [W]ith the growth of the key size, the security grows much faster.

Since it's being considered as post-quantum encryption, I have no problem with the assertion that it has "some advantages over RSA", but stating as fact (without reference) a higher security by increasing the key size – in bits – I find highly dubious since later in the same introduction it reads

For a standard selection of parameters, the public key is 512 kilobits long.

And the highest used key size for RSA currently is 4 kilobits. So McEliece is already at a 128x disadvantage. Which doesn't (necessarily) mean the statement is untrue, but in highly serious need of citation. I have therefore added the {{Citation needed}} template and will remove this dubious claim if it remains uncited through, say, February 2015. 129.217.129.130 (talk) 00:52, 9 February 2015 (UTC)

The offending diff. I'd ping the user, but he seems to have been inactive for 5 years. 129.217.129.130 (talk) 01:27, 9 February 2015 (UTC)

Example?

I think that giving some explicit example would clearly help to understand the contents of this page. For instance, it may be not completely clear to the reader what an "efficient decoding algorithm A" might be. Spirandola (talk) 10:56, 28 December 2021 (UTC)