{"id":28372,"date":"2019-09-03T15:04:24","date_gmt":"2019-09-03T19:04:24","guid":{"rendered":"https:\/\/www.kaspersky.com\/blog\/?post_type=emagazine&p=28372"},"modified":"2022-11-17T03:29:36","modified_gmt":"2022-11-17T08:29:36","slug":"quantum-encryption","status":"publish","type":"emagazine","link":"https:\/\/www.kaspersky.com\/blog\/secure-futures-magazine\/quantum-encryption\/28372\/","title":{"rendered":"A new breed of encryption algorithms that quantum computers can’t yet beat"},"content":{"rendered":"

With the quest to build a full-scale quantum computer now expanding beyond the science lab to encompass technology giants (such as IBM<\/a>, Google<\/a>, Microsoft<\/a>) and quantum computing start-ups (including Rigetti<\/a>, IonQ<\/a> and 1Qubit<\/a>), the race is on to create the hardware and software powering the next generation of computation.<\/p>\n

Quantum simulation looks set to revolutionize chemical and pharmaceutical companies. AI efforts could be enhanced with quantum machine learning, posing huge opportunities for businesses to optimize how they use their data. But as the charge towards a universal quantum computer starts to unlock these benefits for business and society as a whole, the threat to cybersecurity systems around the world looms larger. This is because quantum computers, once built up to their full potential, will have the ability to solve particular kinds of hard problems, and one of these problems is at the root of protecting the world\u2019s information. The excitement about the potential of quantum computers also brings worry about our current encryption methods.<\/p>\n

Quantum-powered codebreakers<\/h2>\n

Many security systems protocols \u2013 such as RSA, Diffie-Hellman or Elliptic-Curve Cryptography \u2013 use public-key encryption techniques based on hard mathematical problems like integer factorization. They\u2019re the most popular and prevalent cryptographic algorithms due to their efficiencies, and they\u2019re the industry\u2019s precedent, built into early versions of the Secure Sockets Layer (SSL) protocol, for example.<\/p>\n

The power in the integer factorization problem, and thus the reliability of these methods for our standard security efforts, is that it simply takes conventional computers too long to compute the answer to break the encryption. Quantum computers, with their completely different architecture and theoretical ability to solve the famous Shor\u2019s algorithm<\/a>, once built to their full-scale versions will be able to solve integer factorization problems at speed and put these pervasive conventional security methods at risk.
\n\"\"
\nNo-one has come close to building a universal quantum computer capable of running Shor\u2019s algorithm, and so conventional security methods are safe from quantum computing right now. But standards organizations are on the hunt for the new quantum-safe algorithms right now, so they can be adopted globally across the industry in time for a future quantum revolution. The National Institute of Standards and Technology put out a call out to researchers in 2016 to submit post-quantum algorithms, and only this year narrowed it down to the final 26 candidates<\/a>. They\u2019re still evaluating which should become the new standard.<\/p>\n

In some sense, this pace is understandable as there\u2019s no immediate rush right now \u2013 we are still far away from having a full-scale universal quantum computer. The most advanced versions released by universities and companies in 2019 are extremely nascent in comparison to what will be needed to crack Shor\u2019s. But on the other hand, no one can predict the future, and it\u2019s true that many of the finest mathematical, engineering and computer science minds are working hard to build quantum computers. To start the subsequent global rollout of the new algorithms, having the regulation and agreed standards in place should be a priority if companies and governments are not to be taken by surprise.<\/p>\n

Quantum-safe algorithm systems<\/h2>\n

Quantum-safe algorithms need to be based on mathematical problems which are not only too difficult for conventional computers to solve in a reasonable time but also too tricky for quantum computers. Most of these algorithms can be grouped into three families of problems: lattice cryptosystems, code-based systems and multivariate systems.<\/p>\n

Lattice cryptosystems<\/h3>\n

Lattice-based algorithms come from a core problem called the Shortest Vector Problem (SVP), which is about finding the smallest non-zero vector within the lattice. If you take a two-dimensional lattice (a grid of regularly spaced dots you could draw on a piece of paper) and draw a line from the bottom left-hand corner (zero) to a dot in the grid, you\u2019ll have a vector. Vectors can be combined using addition, subtraction and multiplication to traverse the lattice and find routes to other dots, in the process, creating new lines from the zero point to the new destination. The Shortest Vector Problem asks you to take a particular vector and work out how to multiply, add and subtract combinations of it to get to the dot closest to zero. This sounds like an easy enough problem to solve, particularly if you are working with a two-dimensional lattice, but as you add in multiple dimensions \u2013 there could be up to 10,000 \u2013 the problem quickly becomes too difficult for both conventional and quantum computers, making it a compelling candidate for quantum-safe cryptography.<\/p>\n

Code-based systems<\/h3>\n

Code-base cryptosystems are based on a tough mathematical problem called syndrome decoding, which is linked to error correction. Codes for error-correcting are used to fix mistakes in the code, such as a 1 that should be a 0 or vice versa, which inevitably occur during transmission of digital messages. These are essentially secret decoding functions which only the person in possession of it can use to recover the original message, in the same way most forms of cryptography have worked throughout the ages: from Caesar\u2019s men running secret messages to the Roman battlefields where the generals already had in their possession the recipe to translate them from gibberish, to the secret decoding techniques of the German war communicators that Alan Turing\u2019s Enigma machine managed to crack.
\n\"\"
\nThese error-correcting codes are usually used in situations where it would be cumbersome or costly to retransmit messages to work out where the errors are, for example, receiving data from faraway spacecraft, which can take hours to transmit back to Earth \u2013 not something you\u2019d want to do many times. Instead, the error-correcting code is essentially baked into the message by deliberately creating \u2018errors\u2019, or scrambles of the original message, within. Without the recipe on the other end to decode this scrambled message, it\u2019s computationally too hard for both standard and quantum computers to reverse the errors and the encoding to crack the message. The most popular of these error-correcting codes is called a Goppa code, which could be a way to save security professionals from quantum-powered attacks.<\/p>\n

Multivariate systems<\/h3>\n

The clue is in the name here, as these algorithms are based on the difficulty of solving systems of equations with multiple variables. If you remember trying to solve quadratic equations in high school \u2013 which only have two variables, say x and y \u2013 it soon becomes clear how difficult it can be to solve systems with three, ten or even hundreds of variables. The most promising systems include the creatively named Unbalanced Oil and Vinegar (UOV) scheme and the Rainbow scheme; these can be used for digital signatures, just two options among many in the quest to replace our current public-key methods.<\/p>\n

Future-proofing encryption standards<\/h2>\n

The direction of quantum encryption practice isn\u2019t to find \u2018one quantum-safe algorithm to rule them all,\u2019 though. As the history of cryptography has shown us \u2013 from the ciphers used in the Spartan military to the Bletchley Park code-breakers in World War II \u2013 old methods become useless as researchers become smarter. The algorithms being put forward by mathematicians, cybersecurity researchers and quantum computing scientists as quantum-safe standards may, one day, be proven to be not so quantum-safe after all. The scientists of the future might find other ways to break these algorithms, just like Shor\u2019s has been found as a solution to break integer factorization.<\/p>\n

But the uncertainty about the future safety of these new algorithms doesn\u2019t remove the need to make our security standards tighter now based on our knowledge that quantum computing will pose a huge threat to current systems. As emerging technologies reach the market, we need to make standards stronger to enable innovators to make the most of these incredible new inventions, as opposed to feeling threatened and missing out on their potential to improve the state of the world.<\/p>\n

The cybersecurity industry must be comfortable questioning its confidence in existing methods. It must ensure the traditional, sometimes slow-moving institutions in charge of standards and regulations move more quickly. The industry cannot fall into the trap of assuming quantum computing is still too far away to be a threat to \u2018business as usual.\u2019<\/p>\n

It\u2019s only all of the world\u2019s digital information that\u2019s at stake, after all.<\/p>\n

This article represents the personal opinion of the author.<\/em><\/p>\n

Article published in 2019.<\/p>\n","protected":false},"excerpt":{"rendered":"

As the race to build quantum computers heats up, the cybersecurity industry looks to the planet\u2019s best mathematicians to protect the world\u2019s information.<\/p>\n","protected":false},"author":2518,"featured_media":46220,"template":"","coauthors":[3504],"class_list":{"0":"post-28372","1":"emagazine","2":"type-emagazine","3":"status-publish","4":"has-post-thumbnail","6":"emagazine-category-future-tech","7":"emagazine-category-opinions","8":"emagazine-category-trends","9":"emagazine-tag-encryption","10":"emagazine-tag-quantum-computing"},"hreflang":[{"hreflang":"x-default","url":"https:\/\/www.kaspersky.com\/blog\/secure-futures-magazine\/quantum-encryption\/28372\/"},{"hreflang":"en-gb","url":"https:\/\/www.kaspersky.co.uk\/blog\/secure-futures-magazine\/quantum-encryption\/20317\/"}],"acf":[],"_links":{"self":[{"href":"https:\/\/www.kaspersky.com\/blog\/wp-json\/wp\/v2\/emagazine\/28372","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.kaspersky.com\/blog\/wp-json\/wp\/v2\/emagazine"}],"about":[{"href":"https:\/\/www.kaspersky.com\/blog\/wp-json\/wp\/v2\/types\/emagazine"}],"author":[{"embeddable":true,"href":"https:\/\/www.kaspersky.com\/blog\/wp-json\/wp\/v2\/users\/2518"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.kaspersky.com\/blog\/wp-json\/wp\/v2\/media\/46220"}],"wp:attachment":[{"href":"https:\/\/www.kaspersky.com\/blog\/wp-json\/wp\/v2\/media?parent=28372"}],"wp:term":[{"taxonomy":"author","embeddable":true,"href":"https:\/\/www.kaspersky.com\/blog\/wp-json\/wp\/v2\/coauthors?post=28372"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}