{"id":1086,"date":"2005-10-03T12:05:28","date_gmt":"2005-10-03T19:05:28","guid":{"rendered":"http:\/\/dabacon.org\/pontiff\/?p=1086"},"modified":"2005-10-03T12:05:28","modified_gmt":"2005-10-03T19:05:28","slug":"shor-broke-our-toys","status":"publish","type":"post","link":"https:\/\/dabacon.org\/pontiff\/2005\/10\/03\/shor-broke-our-toys\/","title":{"rendered":"Shor Broke Our Toys"},"content":{"rendered":"

Rod Van Meter has an interest post up today on his blog titled Stop the Myth: QKD doesn’t fix what Shor broke<\/a>. Along similar lines, Rod points to the paper quant-ph\/0406147<\/a> by Kenneth G. Paterson, Fred Piper, and Ruediger Schack, “Why Quantum Cryptography?”
\nHere is my take on what Rod and quant-ph\/0406147 are arguing (but I’d recommend reading what they say, because my expertise on quantum cryptography goes to zero in the limit of the people who know what they are talking about going to some number greater than four.) Mostly I’ve just cobbled this together from what Rod said and my own personal misunderstandings. So you should read Rod’s post first, and then laugh at my silly rehashing of the main points.
\n To simplify life let’s break secure communication into two steps. The first is authentication and the second is key exchange. In most applications what we need to do is first authenticate our channel and then second we need to do key exchange using this authenticated channel. Now Shor’s algorithm broke the most popular public key cryptosystems (those based on the difficulty of factoring and discrete log.) These public key cryptosystems were often used for both authentification and for key exchange. Thus Shor broke both of these when operating with those cryptosystems.
\nOK, now what the quantum cryptography (QKD) do? Well what it does is, given an authenticated channel, it allows you to create secret keys whose security is based on quantum theory being a correct description of nature. But how does one establish this authentification? Because Shor broke the most widely used public key cryptosystems, we need to establish this with some other technique. One way to do this is for the parties to share some small secret keys which they can then use to establish the authenticated channel. So the point Rod and others are making is that QKD doesn’t provide for an authentication scheme whose security is based on the quantum theory. Rod thinks that physicists haven’t known about this or realized it’s importance, which may be true as I can’t read other physicists brains or listen to all they, but I certainly think everyone working in quantum cryptography realizes this (and even some people who don’t like me \ud83d\ude09 ) QKD is thus best viewed not as a way to providing a total solution to unconditional security but as a way to take a small secret key and use it to create a huge shared secret key. The security of this will be based on (1) the security of the authentication scheme and (2) the laws of quantum theory. Maybe to put this into simple words, I would say that QKD fixes only part of what Shor broke.
\nAnother important point is that in the above paragraph I’m talking about using QKD as a way to distribute keys at a sufficiently high rate to use these keys as one time pads for communication. Right now, many of the QKD systems do not opperate at speeds fast enough to achieve this goal for reasonable communciation rates. Certainly getting to these high speeds is one of the grand challenges in experimental QKD! Currently, I am told, that many QKD systems sold use the keys they generate as part of another layer of cryptography (like 3DES or AEA). This does provide security, but weakens the security (one could conveivably break these other systems…one would need to do this for the size of the key the QKD creates: so as QKD rates go up and up, conceivably one should be able to make this security higher and higher until eventually you will just want to use the key as a pad.)
\nBut, like I said, my understanding of this is murky, so go read Rod’s blog<\/a> and check out quant-ph\/0406147<\/a>! Oh, and for all you lurking quantum cryptologists, I’d love to hear your take on all of this. <\/p>\n","protected":false},"excerpt":{"rendered":"

Rod Van Meter has an interest post up today on his blog titled Stop the Myth: QKD doesn’t fix what Shor broke. Along similar lines, Rod points to the paper quant-ph\/0406147 by Kenneth G. Paterson, Fred Piper, and Ruediger Schack, “Why Quantum Cryptography?” Here is my take on what Rod and quant-ph\/0406147 are arguing (but … <\/p>\n

Continue reading “Shor Broke Our Toys”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","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,63],"tags":[],"class_list":["post-1086","post","type-post","status-publish","format-standard","hentry","category-computer-science","category-quantum"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts\/1086","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=1086"}],"version-history":[{"count":0,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts\/1086\/revisions"}],"wp:attachment":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/media?parent=1086"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/categories?post=1086"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/tags?post=1086"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}