But this striking discovery relied on unrealistic assumptions. The result was \u201cmore of a proof of concept,\u201d said Fermi Ma<\/a>, 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<\/a> 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 Castle in the Sky<\/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 \u2014 there 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<\/a>. 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>, 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 \u2014 technically known as NP problems \u2014 whose 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<\/a>. 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 \u2014 one-way functions \u2014 can 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 It started with a 2021 paper<\/a> by a graduate student named William Kretschmer<\/a> that drew attention to a strange problem about the properties of quantum systems. Researchers soon showed that Kretschmer\u2019s problem could replace one-way functions as the foundation for a new tower of cryptographic<\/a> protocols<\/a>. The following year, Kretschmer and others proved<\/a> that this alternative approach could work even without hard NP problems. Suddenly, it seemed like it might be possible to construct a cryptographic fortress that would be far sturdier.<\/p>\n But where to build it? The quantum problem Kretschmer used as his foundation involved hypothetical computing devices called oracles<\/a> that can instantaneously answer specific questions. Oracles can be useful theoretical tools, but they don\u2019t actually exist. Kretschmer\u2019s proofs were like a blueprint for building a castle in the sky. Was there a way to bring it down to earth?<\/p>\n Second Foundation\u00a0\u00a0 <\/p>\n In the fall of 2022, that question caught the attention of Dakshita Khurana<\/a>, a cryptographer at the University of Illinois at Urbana-Champaign and NTT Research. Khurana and her graduate student Kabir Tomer<\/a> set out to build a new tower of cryptography. Her first step was to build a new foundation using quantum building blocks instead of classical one-way functions. She would then need to prove that this new foundation could support a tower of other cryptographic protocols. Once she proved that the foundation could support the tower, she would have to find a solid place for the whole thing to sit \u2014 a bedrock of real-world problems that seem even harder than the NP problems used in classical cryptography.<\/p>\n Dakshita Khurana set out to find mathematical building blocks that could replace one-way functions as a foundation for quantum cryptography.<\/p>\n For the first step, Khurana and Tomer focused on a quantum version of a one-way function, called a one-way state generator<\/a>, that satisfied the three properties that make one-way functions useful. First, the function must run quickly so that you can easily generate a cryptographic lock and the corresponding key to open it for each message you want to send. Second, each lock must be secure, requiring great effort to break open without the right key. Finally, every lock must be easy to open with the right key.<\/p>\n The crucial difference lay in the nature of the locks. Classical one-way functions generate mathematical locks made of bits \u2014 the 0s and 1s that store information in a classical computer. Quantum one-way state generators would instead generate locks made of units of quantum information called qubits. These quantum locks could potentially remain secure even if all classical locks are easy to break. Khurana and Tomer hoped to start with this new quantum foundation and build a tower of cryptographic protocols on top of it. \u201cThis turned out to be quite hard,\u201d Khurana said. \u201cWe were stuck for many, many months.\u201d<\/p>\n We\u2019re just trying to understand this new landscape.<\/p>\n Mark Zhandry<\/p>\n By July 2023, Khurana was nearly nine months pregnant and planning for parental leave. Tomer was out of ideas. \u201cI\u2019m much more pessimistic than Dakshita,\u201d he said. \u201cShe\u2019s always the one who believes that things will work.\u201d<\/p>\n Then they made a breakthrough. The crucial step was defining another mathematical building block that served as something like a basement floor: a structure that would connect the foundation of one-way state generators to a tower of cryptographic protocols. When Khurana and Tomer worked out what properties that building block would need to have, they found that it resembled a one-way function with a perplexing mixture of quantum and classical characteristics. As in an ordinary one-way function, both locks and keys were made of classical bits, but the procedure for generating these locks and keys would only run on a quantum computer. Stranger still, the new building block satisfied the first two defining properties of one-way functions, but not the third: It was easy to generate locks and keys, and every lock was hard to break. But a key wouldn\u2019t easily open its lock.<\/p>\n Khurana and Tomer dubbed these perplexing new building blocks one-way puzzles. Intuitively, it\u2019s hard to imagine how they could possibly be useful: What good is a key that you can never use? But the two cryptographers showed that one-way puzzles combined with other quantum trickery would actually enable many cryptographic protocols<\/a>. If you can generate locks and keys that fit together in principle, it doesn\u2019t matter whether the unlocking procedure is wildly inefficient.<\/p>\n Kabir Tomer and Khurana connected the new quantum building blocks to real-world problems harder than the ones used in classical cryptography.<\/p>\n \u201cJust knowing that there exists some algorithm that can be arbitrarily slow is sufficient,\u201d said Kretschmer, who is now a researcher at the Simons Institute. \u201cThat is very surprising.\u201d<\/p>\n With that missing piece in place, they quickly finished the proof on August 4. Khurana\u2019s daughter was born just days later.<\/p>\n Permanent Record<\/p>\n By November, Khurana was back at work and ready to attempt the second phase of her plan. She and Tomer had shown that many kinds of cryptography could be built upon one-way puzzles, and that one-way puzzles could in turn be built upon a new quantum foundation made of one-way state generators. The next step in their original plan was to connect that quantum foundation to a new bedrock \u2014 some relatively unassailable set of math problems that are even more intractable than those in NP.<\/p>\n But as Khurana and Tomer grappled with that task, they decided to take a more direct approach: Forget about the one-way state generators, and instead anchor one-way puzzles directly to the mathematical bedrock.<\/p>\n William Kretschmer showed that in theory, quantum cryptography could be secure without the one-way functions that are essential to all classical encryption.<\/p>\n From one perspective, that seemed like an odd choice. One-way puzzles were mathematical oddities that Khurana and Tomer had used in an intermediate step of their proof.<\/p>\n Yet one-way puzzles had some advantages. For one thing, while they\u2019re quantum, the locks and keys that they generate are classical. Khurana thought that might make it easier to connect them to a bedrock of classical mathematics. In addition, one-way puzzles generate keys that are too unwieldy to actually open locks. That could make it easier to link them to problems so tricky that even checking solutions seems hopelessly hard.<\/p>\n But what specific problems would work? Khurana had a candidate in mind: calculating a specific combination of the entries in a table of numbers called a matrix. This problem, known as the matrix permanent problem, is notoriously difficult to solve for large matrices, and there\u2019s no simple way to check whether a calculation is correct. The matrix permanent problem also has other special mathematical properties that cryptographers find appealing.<\/p>\n \u201cThis would be a beautiful problem to base cryptography on,\u201d Khurana said.<\/p>\n The matrix permanent problem also connects to a different problem that quantum computers can easily solve but classical computers seemingly can\u2019t<\/a>. Researchers are working on proving this quantum computational advantage in a precise theoretical sense. Khurana and Tomer showed that such a proof would also let them build secure one-way puzzles \u2014 and thus the whole tower of quantum cryptography \u2014 on top of the permanent problem.<\/p>\n \u201cThey were able to do this from these well-studied assumptions,\u201d Kretschmer said. \u201cI was really happy to see that.\u201d<\/p>\n With their new result, Khurana and Tomer have effectively reduced two open problems to one. If researchers complete the proof that quantum computers truly surpass classical ones at a specific task, that will automatically put quantum cryptography on much stronger theoretical footing than practically any kind of classical cryptography.<\/p>\n Alas, you won\u2019t be able to use Khurana and Tomer\u2019s new approach to send secret messages any time soon. Despite recent progress<\/a>, quantum computing technology is not yet mature enough to put their ideas into practice. Meanwhile, other researchers have devised quantum cryptography methods that could be used sooner<\/a>, though more work will be needed to establish that they\u2019re truly secure.<\/p>\n Quantum cryptography has already proved full of surprises, and researchers have only recently begun exploring the possibilities. \u201cWe\u2019re just trying to understand this new landscape that really existed the whole time,\u201d Zhandry said.<\/p>\n","protected":false},"excerpt":{"rendered":"Hard problems are usually not a welcome sight. But cryptographers love them. That\u2019s because certain hard math problems…\n","protected":false},"author":2,"featured_media":36657,"comment_status":"","ping_status":"","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[191,74],"class_list":{"0":"post-36656","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-computing","8":"tag-computing","9":"tag-technology"},"_links":{"self":[{"href":"https:\/\/www.newsbeep.com\/us\/wp-json\/wp\/v2\/posts\/36656","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.newsbeep.com\/us\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.newsbeep.com\/us\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.newsbeep.com\/us\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.newsbeep.com\/us\/wp-json\/wp\/v2\/comments?post=36656"}],"version-history":[{"count":0,"href":"https:\/\/www.newsbeep.com\/us\/wp-json\/wp\/v2\/posts\/36656\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.newsbeep.com\/us\/wp-json\/wp\/v2\/media\/36657"}],"wp:attachment":[{"href":"https:\/\/www.newsbeep.com\/us\/wp-json\/wp\/v2\/media?parent=36656"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.newsbeep.com\/us\/wp-json\/wp\/v2\/categories?post=36656"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.newsbeep.com\/us\/wp-json\/wp\/v2\/tags?post=36656"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}![\"Dakshita](\"https:\/\/www.newsbeep.com\/us\/wp-content\/uploads\/2025\/07\/DakshitaKhurana-crRaviShankarKhurana.webp.webp\")
<\/p>\n![\"Kabir](\"https:\/\/www.newsbeep.com\/us\/wp-content\/uploads\/2025\/07\/KabirTomer-crJamesBartusek-7-copy.webp.webp\")
<\/p>\n![\"William](\"https:\/\/www.newsbeep.com\/us\/wp-content\/uploads\/2025\/07\/WilliamKretschmer-crJustinDuRant.V2.webp.webp\")
<\/p>\n