Talk:McEliece cryptosystem
From Wikipedia, the free encyclopedia
 |
This article is part of WikiProject Cryptography, an attempt to build a comprehensive and detailed guide to cryptography on Wikipedia. If you would like to participate, you can choose to edit the article attached to this page, or visit the project page, where you can join the project and see a list of open tasks. |
[edit] 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)
[edit] 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...
