Quantum vs. Crypto

Quantum computers are incredibly powerful machines that take a new approach to processing information. They may one day lead to revolutionary breakthroughs in materials and drug discovery, the optimization of complex manmade systems, and artificial intelligence.

Origin and Description

The first notion of quantum computing was put forward by Richard Feynman, who thought up the idea of a 'quantum computer', a computer that uses the effects of quantum mechanics to its advantage. In the classical world we were limited to transformations from one state to one other state. Now with quantum states we can make programs that transform from a combination of states into another combination of states. This ability is a problem for modern cryptography. Some quantum algorithms are an order of magnitude faster than their classical counterparts because of this. The most famous example is Shor’s algorithm, which allows for easy factoring of large prime numbers (breaking RSA and all discrete logarithm based cryptosystems).

Quantum computers take advantage of unusual phenomena, such as:
  • Electrons can be both waves and particles
  • Objects can exist in multiple places at once
In classical computing, a bit is a single piece of information that can exist in two states – 1 or 0. Quantum computing uses quantum bits, or “qubits” instead. These are quantum systems with two states. However, unlike a usual bit, they can store much more information than just 1 or 0, because they can exist in any superposition of these values.

Quantum computers also utilize another aspect of quantum mechanics known as entanglement. One problem with the idea of quantum computers is that if you try to look at the subatomic particles, you could bump them, and thereby change their value. If you look at a qubit in superposition to determine its value, the qubit will assume the value of either 0 or 1, but not both (virtually turning into a mundane digital computer). To make a practical quantum computer, scientists have to devise ways of making measurements indirectly to preserve the system's integrity. Entanglement provides a potential answer. In quantum physics, if you apply an outside force to two atoms, it can cause them to become entangled, and the second atom can take on the properties of the first atom. So if left alone, an atom will spin in all directions. The instant it is disturbed it chooses one spin, or one value; and at the same time, the second entangled atom will choose an opposite spin, or value. This allows scientists to know the value of the qubits without actually looking at them.

Grover's algorithm is a quantum algorithm for searching an unsorted database. It was invented by Lov Grover in 1996. Classically, searching an unsorted database requires a linear search, which takes twice the time required by Grover's algorithm. It is for now the fastest possible quantum algorithm for searching an unsorted database! The Grover algorithm is a clear symptom of the advantage that quantum computers have over classical computers. Grover defeats the strength of symmetric ciphers and cryptographic hash functions by a factor of two. Furthermore, Grover’s algorithm can be used to find collisions in hash functions much faster.

Because of these properties, quantum computing will make computing more secure using quantum encrypted communications, execute digital transactions almost instantaneously, and solve intractable computational problems. In addition, it will significantly help us reduce energy consumption in computing. Google has started exploring new approaches to building a full-scale multipurpose quantum computer. Many believe that thanks to Google’s research, the quantum computer age is imminent. In effect, according to MIT Technology Review, “Researchers at Google may unveil a truly powerful quantum computer by the end of next year.”

In September 2017, Satya Nadella announced that Microsoft is working on a quantum computer architecture. Since then,Intel also has announced it is working on a quantum computer architecture. Microsoft and Intel join Alibaba, Google, IBM, Tencent and a host of academic and national research labs (including China, the European Commission, Russia and the US) in a quest to build working QC hardware and software that can solve real-world problems.
For today, the most advanced quantum computers have not gone beyond manipulating more than 16 qubits, meaning that they are a far cry from practical application. However, the potential remains that quantum computers one day could perform, quickly and easily, calculations that are incredibly time-consuming on conventional computers.

Quantum and Bitcoin

On the most basic level, Bitcoin, as the decentralized currency, exists alongside the blockchain thanks to the Bitcoin mining algorithm. And so, computers, from the day that the blockchain first came into being, have been working to actually execute the algorithm that makes it all real. This work to execute the algorithm, which results in adding more transactions to the blockchain, also creates more bitcoins in the process. This process is called Bitcoin mining, and for the most part, it’s currently done through Bitcoin mining farms around the world.

But what happens when quantum computing comes in? In a recent piece for Hacker Noon, author and entrepreneur Riz Virk shared his ideas for using a quantum computer to completely corner the Bitcoin mining market. Of course, it’s all just theoretical, as quantum computers are far from being commercially available. Quantum computing will soon become a reality that can help to reduce Bitcoin mining energy consumption and thus benefit the environment. Certainly, this development, in turn, will also affect the economics of mining. As a result, more individuals might wish to start mining, thereby increasing decentralization, as perhaps Satoshi Nakamoto had envisioned.

On the other hand, a crucial feature of Bitcoin is its security. Bitcoins have two important security features that prevent them from being stolen or copied. Both are based on cryptographic protocols that are hard to crack. In other words, they exploit mathematical functions, like factorization, that are easy in one direction but hard in the other—at least for an ordinary classical computer. But quantum computers can solve these problems easily. That raises an urgent question: how secure is Bitcoin to the kinds of quantum attack that will be possible in the next few years?

Divesh Aggarwal from the National University of Singapore suggests that the danger is real and imminent. Aggarwal studied the likelihood of a quantum computer becoming so powerful on the network, that it breaks the 50% computational power threshold and chooses to control the ledger (this made possible by the PoW algorithm behind the Bitcoin network). His team looked at the projected clock speeds of quantum computers in the next decade and compared that to the likely power of conventional hardware. Their conclusion came as a relief to Bitcoin miners. Most mining is done by application-specific integrated circuits (ASICs), and this hardware is likely to maintain a speed advantage over quantum computers over the next ten years or so.
But there is a different threat that is much more worrying. Bitcoin has a cryptographic security feature to ensure that only the owner of a Bitcoin can spend it. This is based on the same mathematics used for public-key encryption schemes. The idea is that the owner generates two numbers — a secret private key and a public key. The public key can be easily generated from the private key, but not vice versa. A signature can be used to verify that the owner holds the private key, without revealing it, using a technique known as an elliptic curve signature algorithm (ECDSA). The only way to cheat this system is to calculate the private key using the public key, which is extremely hard with conventional computers, but easy with a quantum computer.

Indeed, quantum computers pose a similar risk to all encryption schemes that use a similar technology, which includes many common forms of encryption. Of course, there are public-key schemes that are resistant to attack by quantum computers. So it is conceivable that the Bitcoin protocols could be revised to make the system safer. But there are no plans to do that now.

As for RSA, similar encryption methods are based on the premise that factoring large numbers is computationally unattractive. However, with the advent of quantum computers, the factoring of large numbers now becomes more real. Quantum computers could potentially become so powerful they require their own kind of cryptography, but that doesn’t mean Bitcoin and today’s encryption methods must be left out entirely. With some reworking, they could be made more secure. Some experts suggest doubling or tripling the length of cryptographic keys.

According to MIT Technology Review, Bitcoin doesn’t have any plans to revise its current security protocols just yet, but with usable quantum computers still a decade or two away, cryptocurrency platforms have time to reconsider their encryption methods. No research group has come close to building a quantum computer with enough bits to break any real-world crypto.
Besides, new “post-quantum” cryptographic algorithms are currently being developed. These new algorithms are based on other hard math problems, which even quantum computers cannot efficiently solve. Most of these algorithms use very large keys, which makes them impractical, but reasonable candidates have been proposed and even implemented in mainstream software. It is clear however that we will eventually have to replace all public key crypto by post-quantum algorithms, and that this must happen rather sooner than later.

Quantum Computing Challenges

Quantum computing has the potential to quickly solve problems that are impossible to calculate in useful timeframes (or even human lifetimes) today. But there several challenges it has to overcome before reaching such power. Solving useful real-world problems, such as breaking 128-bit encryption keys, will require assembling and orchestrating thousands of logical qubits at near absolute zero temperatures. It will also require learning how to write complex programs for quantum computing architectures. There are quantum computing algorithmic frameworks for writing programs that can help speed up cracking encryption keys, such as Shor’s and Grover’s algorithms, but quantum computing researchers still don’t understand how to frame those algorithms as an expression of qubit.

Researchers are learning to build quantum computing systems that can reliably orchestrate thousands of logical qubits. And they are learning how to usefully program those qubits. Then they must build a software ecosystem to commercialize their quantum computing systems. Of course, it also requires building thousands of qubits. Using graphics processing units (GPUs) compute as a model, quantum computing must implement layers of software abstraction and easy-to-use development environments, so average programmers can use quantum computing systems as compute accelerators without having to understand how to program any specific quantum computing system.

In general, quantum computing researchers believe that shipping a commercial quantum computing accelerator based on logical qubits is still at least 15 years away, pointing to commercialization in the early 2030 at the soonest.

Post-quantum Technologies

The US National Institute of Standards and Technology (NIST) is working on detailed recommendations for a post-quantum cryptography world. Its intent is to issue draft standards on post-quantum cryptography in the 2023-2025 timeframe, about halfway through an industry consensus minimum 15-year quantum computing development and commercialization period. Quantum computing will not break encryption keys this decade. It will happen at some point, but there are reasonable steps that can be taken now to keep data safe for at least a couple of decades. In a few years NIST, and presumably other governmental organizations across the globe, will publish stronger recommendations that will directly address post-quantum computing cryptographic safety.

Cryptographic algorithms are used to encrypt a plaintext into a scrambled ciphertext using a unique key. The ciphertext can only be converted back to a readable plaintext using a complementary decryption algorithm, together with the key. The key encapsulates all of the secrecy in this process, and data can only be decrypted with the correct key. There is no secrecy embodied in the algorithm, which is assumed to be known by any potential attacker. Public and private keys are related by integer factorizations. Improved approaches to factoring large numbers, such as Shor’s Algorithm running on a sufficiently large quantum computer, will improve the likelihood of breaking public-key cryptography. These algorithms are therefore deemed quantum-breakable, because their protection decreases as quantum computers become more powerful.

Luckily, not all of today’s cryptosystems are expected to yield to quantum attack. Shor’s algorithm (and similar algorithms) shows promise only for cryptosystems based on integer factorization, however other cryptosystems are available that rely on different safer mathematical bases. For example, the symmetrical AES algorithm uses a substitution-permutation network to scramble and unscramble data, and as such its security is weakened slightly by quantum attacks. To compensate for this weakening, it is necessary to simply double the key length, with no change to the algorithm. This creates a secure cipher, resistant to quantum attack.

In addition, new cryptosystems are being developed that do not rely on quantum-breakable algorithms. Several approaches have been proposed, and some are receiving institutional support. One of these is the “Never-The-Same” (NTS) encryption. This algorithm never generates the same ciphertext twice, even when the plaintext and encryption keys remain constant. Independent security analysis by Royal Holloway, University of London concluded that NTS is secure against chosen-ciphertext attack (CCA). NTS is based on the McEliece cryptosystem, which relies on injecting random noise into a message. This noise is removed on decryption using error correcting techniques derived from the field of digital and satellite communication.

To conclude, we may say that quantum computing definitely poses new serious challenges for the blockchain technology. Fortunately, developers and researches still have at least a decade to work out solutions to fight back the threat.


Popular posts from this blog

Crowdfunding vs ICO: major differences

Marketing ICO case

ICO regulation: Global trends