{"id":2115,"date":"2008-10-31T17:37:58","date_gmt":"2008-11-01T00:37:58","guid":{"rendered":"http:\/\/dabacon.org\/pontiff\/?p=2115"},"modified":"2008-10-31T17:37:58","modified_gmt":"2008-11-01T00:37:58","slug":"original-mceliece-cracked","status":"publish","type":"post","link":"https:\/\/dabacon.org\/pontiff\/2008\/10\/31\/original-mceliece-cracked\/","title":{"rendered":"Original McEliece Cracked"},"content":{"rendered":"

Shor’s algorithm is an algorithm for quantum computers which allows for efficiently factoring of numbers. This in turn allows Shor’s algorithm to break the RSA public key cryptosystem. Further variations on Shor’s algorithm break a plethora of other public key cryptosystems, including those based on elliptic curves. The McEliece cryptosystem<\/a> is one of the few public key cryptosystems where variations on Shor’s algorithm do not break the cryptosystem. Thus it has been suggested that the McEliece cryptosystem might be a suitable cryptosystem in the “post quantum world”, i.e. for a world where a quantum computer is built (and if your a commenter who wishes to simply post the quantum computers are like string theory, please…save your keystrokes.)
\n
\nRecently, Tanja Lange<\/a> and coworkers Daniel Bernstein and Christiane Peters have undertaken classical attacks on the McEliece cryptosystem. A public key cryptosystem gives you security as a function of the size of a hard computational problem. For example in the RSA cryptosystem, the problem is closely related to the hardness of factoring. Thus the number of digits in the number being factored gives one a handle on how hard the problem is. For example if you perform RSA using a number which is, say 20 digits long, then I can easily break the key system using my laptop. But if you make the number large enough, then there is no classical computer with enough computational power to break the system. Thus the size of the number to be factored serves as a security parameter. What Lange, Bernstein, and Peters demonstrated was that if one used the original security parameters for the McEliece cryptosystem, then they could break the cryptosystem using classical computers in two weeks on a cluster of one hundred computers. See the press release here<\/a> and the paper here<\/a>. Notably I believe that prior authors had noted that the original parameters for the McEliece cryptosystem did not provide enough security (though I don’t know whether an explicit attack was carried out as the authors do here.) The authors also, notably suggest new security parameters for the McEliece system. (A cool part of the paper is where they thank all the different institutions for the computer time!)
\nSo this is very cool work, an explicit attack on the McEliece system which breaks the original proposed security parameters. And it gives suggestions for what reasonable security parameters should be for the system (which is not used in practice much because the algorithm has a huge key size and is not too fast.)
\nCool, but how it world did the author\/editors of techradar manage to get out of the above story an article titled Quantum computer security cracked<\/a>. Wah? Um, no quantum computer security was cracked. Doh. That’s a long way from the original cool work (though the article doesn’t mess up as badly as that title.)<\/p>\n","protected":false},"excerpt":{"rendered":"

Shor’s algorithm is an algorithm for quantum computers which allows for efficiently factoring of numbers. This in turn allows Shor’s algorithm to break the RSA public key cryptosystem. Further variations on Shor’s algorithm break a plethora of other public key cryptosystems, including those based on elliptic curves. The McEliece cryptosystem is one of the few … <\/p>\n

Continue reading “Original McEliece Cracked”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[20,21,65,84],"tags":[],"class_list":["post-2115","post","type-post","status-publish","format-standard","hentry","category-computer-science","category-computers","category-quantum-computing","category-technology"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts\/2115","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/comments?post=2115"}],"version-history":[{"count":0,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts\/2115\/revisions"}],"wp:attachment":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/media?parent=2115"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/categories?post=2115"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/tags?post=2115"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}