\n<\/p>\n
The original version<\/span> of<\/em> this story<\/em> appeared in<\/em> Quanta Magazine.<\/em><\/p>\n Hard problems are usually not a welcome sight. But cryptographers love them. That\u2019s because certain hard math problems underpin the security of modern encryption. Any clever trick for solving them will doom most forms of cryptography.<\/p>\n Several years ago, researchers found a radically new approach to encryption that lacks this potential weak spot. The approach exploits the peculiar features of quantum physics. But unlike earlier quantum encryption schemes, which only work for a few special tasks, the new approach can accomplish a much wider range of tasks. And it could work even if all the problems at the heart of ordinary \u201cclassical\u201d cryptography turn out to be easily solvable.<\/p>\n But this striking discovery relied on unrealistic assumptions. The result was \u201cmore of a proof of concept,\u201d said Fermi Ma, a cryptography researcher at the Simons Institute for the Theory of Computing in Berkeley, California. \u201cIt is not a statement about the real world.\u201d<\/p>\n Now, a new paper by two cryptographers has laid out a path to quantum cryptography without those outlandish assumptions. \u201cThis paper is saying that if certain other conjectures are true, then quantum cryptography must exist,\u201d Ma said.<\/p>\n You can think of modern cryptography as a tower with three essential parts. The first part is the bedrock deep beneath the tower, which is made of hard mathematical problems. The tower itself is the second part\u2014there you can find specific cryptographic protocols that let you send private messages, sign digital documents, cast secret ballots, and more.<\/p>\n In between, securing those day-to-day applications to mathematical bedrock, is a foundation made of building blocks called one-way functions. They\u2019re responsible for the asymmetry inherent in any encryption scheme. \u201cIt\u2019s one-way because you can encrypt messages, but you can\u2019t decrypt them,\u201d said Mark Zhandry, a cryptographer at NTT Research.<\/p>\n In the 1980s, researchers proved that cryptography built atop one-way functions would ensure security for many different tasks. But decades later, they still aren\u2019t certain that the bedrock is strong enough to support it. The trouble is that the bedrock is made of special hard problems\u2014technically known as NP problems\u2014whose defining feature is that it\u2019s easy to check whether any candidate solution is correct. (For example, breaking a number into its prime factors is an NP problem: hard to do for large numbers, but easy to check.)<\/p>\n Many of these problems seem intrinsically difficult, but computer scientists haven\u2019t been able to prove it. If someone discovers an ingenious algorithm for rapidly solving the hardest NP problems, the bedrock will crumble, and the whole tower will collapse.<\/p>\n Unfortunately, you can\u2019t simply move your tower elsewhere. The tower\u2019s foundation\u2014one-way functions\u2014can only sit on a bedrock of NP problems.<\/p>\n To build a tower on harder problems, cryptographers would need a new foundation that isn\u2019t made of one-way functions. That seemed impossible until just a few years ago, when researchers realized that quantum physics could help.<\/p>\n","protected":false},"excerpt":{"rendered":" The original version of this story appeared in Quanta Magazine. Hard problems are usually not a welcome sight. But cryptographers love them. That\u2019s because certain hard math problems underpin the security of modern encryption. Any clever trick for solving them will doom most forms of cryptography. Several years ago, researchers found a radically new approach<\/p>\n","protected":false},"author":1,"featured_media":19735,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[52],"tags":[12122,4693,4361],"class_list":{"0":"post-19734","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-technology","8":"tag-cryptography","9":"tag-math","10":"tag-quantum"},"_links":{"self":[{"href":"https:\/\/naijaglobalnews.org\/index.php?rest_route=\/wp\/v2\/posts\/19734","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/naijaglobalnews.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/naijaglobalnews.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/naijaglobalnews.org\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/naijaglobalnews.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=19734"}],"version-history":[{"count":0,"href":"https:\/\/naijaglobalnews.org\/index.php?rest_route=\/wp\/v2\/posts\/19734\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/naijaglobalnews.org\/index.php?rest_route=\/wp\/v2\/media\/19735"}],"wp:attachment":[{"href":"https:\/\/naijaglobalnews.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=19734"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/naijaglobalnews.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=19734"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/naijaglobalnews.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=19734"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}Castle in the Sky<\/h2>\n