Eden Labs – Quantum Computing and Blockchain

Except for “Artificial Intelligence,” there may be no more sensationalized term today than “Quantum Computing.” Quantum computing, proponents say, will transform the world we know today, enabling us to solve previously unsolvable problems, and rendering most modern-day encryption schemes irrelevant in the process. Regardless of the speculative impacts, how soon we achieve quantum computing is debatable, and most predictions today, regarding its impact and capabilities, are simply theoretical. However, this hasn’t slowed the speculation or prevented many industries from taking “preventative” measures – or at least as preventative as one can be regarding theoretical speculation. Blockchain has been no different. Some DLT projects choose to exploit the hype and promote more complex encryption techniques, somewhat believed to be quantum resistant. The question arises whether or not this is actually entirely necessary. The following article provides a brief introduction to quantum computing, its potential impact on blockchain, and how relevant a threat it actually is.

What is quantum computing and how does it work?

To understand quantum computing, it is necessary to understand how information is represented in normal computing. Normal processors represent information in bits of 1s and 0s, whereby, a single bit can only take the form 1 or 0. This information can be further defined as  High or Low voltage in a wire, or Light ON/OFF within an optical fibre. If we transfer information at the same time through wires, parallel to each other, we can move information even faster. Afterwards, the information is passed through gates, called logic gates, e.g. AND, OR, NOT; to put the bits in context. Most logic gates have two inputs and one output, which allows processors to combine bits and provide more complex information.

While bits are the basis for standard computing, qubits are the basis for quantum computing. “A single qubit can be in the quantum state |0> or quantum state |1>, or in a special quantum state called the superposition state.” (2) The notation, showing the state of the qubits, is called the ket-notation.

What is the superposition state?

In classical mechanics, any particle has an exact state, which can be defined by the x, y, z coordinates along a three-dimensional graph. This is similar to positioning in a city. We define our location according to these three coordinates. For example: 36th (East to West positioning), A St. (North to South positioning), third floor (vertical positioning). In contrast, in quantum mechanics, any particle, “electron with spin, a photon with polarisation, impurity spins, trapped ions, neutral atom, semiconducting circuits” (2) etc. can have several states simultaneously. Resulting, any particle can exist in multiple positions at the same time. This is called the superposition state.

However, particles are not always able to be in a superposition state. Instead, particles can only be in a superposition state given the proper conditions. Once they are in the superposition state, particles behave like waves, which allows them to be in two states at the same time. In contrast, if anything disrupts the particles, they fall out of the superposition state. It’s a complicated physical concept, but due to the wave/particle duality of electrons, electrons hitting against a wall contact the wall at several places. That’s how the particles behave when they are in a superposition state. Once they fall out of the superposition state, they behave like marbles, only intercepting the all at fixed points. In this state, they can only be in either one state or the other. A more comprehensive explanation can be found in this video (https://youtu.be/DfPeprQ7oGc). When particles fall out of the superposition state, this is called ‘wave function collapse.’ The main challenge for research is that any interference with the particle will force a wave function collapse. Observations need light. If the researchers shine a light on the particles, they disturb their natural state. Developing and researching becomes extremely difficult when the mere act of observation ruins the observed. This is known as the Heisenberg Uncertainty Principle and is foundational to the field of quantum mechanics.

How do qubits work in quantum computing?

Quantum computing is built upon the principles of spinning electrons. Electrons can not only spin up or down, but, while in a superposition state, they can also spin up and down at the same time. As such, by being able to express more states simultaneously than traditional computers, quantum computers unlock vast new potential for computing.

“Take note of the fact, that when the superposition collapses to either |0> or |1> state and you measure it, it turns into a classical bit 0 or 1; and the superposition is lost forever.” (1) Resulting, researchers have to be extremely careful in the way qubits are used.

What is quantum computing?

“Quantum computing studies theoretical computation systems that make direct use of quantum-mechanical phenomena, such as superposition and entanglement, to perform operations on data.” (2) The study of quantum computing deals with the most efficient way of combining several qubits by analysing its properties.

What is quantum entanglement?

“Quantum entanglement is the phenomenon by which more than one particle, generated together or closely interacted, can start a relationship and the quantum state of each particle cannot be described independently.” Ultimately, 2 or more qubits can describe together more distinct states than a single qubit. One qubit can describe 3 different states, 2 qubits can show 9 different states, and 3 qubits can show 27 different states. The growth is exponential. This allows quantum algorithms to test several scenarios at the same time and thus find solutions much faster.

How will Quantum Computing affect Blockchain?

Blockchain security relies on standard encryption keys, such as RSA and ECC. To break these keys requires vast amounts of computational resources.

Normal computing is fast and efficient — provided the problem does not have many possible solution. In that scenario, a processor would try every possibility separately, taking immense time. Modern day encryption methods aren’t impossible to crack; they would just take enormous amounts of computation millions of hours to break. Quantum computing, conceivably, could crack it far quicker. For example, the security of RSA encryption is based on the difficulty to factorise large prime numbers. Quantum computing would be potentially ideal for prime factorisation. Computers today take years for such problems; in comparison, a quantum computer would, potentially, be able to find RSA encrypted keys in seconds; just by knowing the public key. This means that quantum computing could make not only blockchain vulnerable, but all of our modern day encryption and privacy protocols.

While the impact of quantum computing will likely be immense, impacting many of our current systems, the relevance of “quantum resistant” designs is still unclear. This is due to two main factors:

  1. Quantum computing research is still encountering significant obstacles to its technical implementation.
  2. It’s unclear how close we are to the implementation of quantum computing.

The problems with quantum computing we have to solve:

Addressing, point #1, quantum computers still have significant technical problems to solve. As demonstrated before, any qubit can be in three states at the same time. If you increase the number of qubits, the number of potential states increases exponentially. Since we have no way (at the moment) of accessing the information represented in a superposition state, we have to develop quantum algorithms “which explore the existence of huge amounts of information stored in superposition of qubits and at the end of the computation, leave the system in one of the base states which we can detect with certainty.” (2) The base states refer to 1 or 0, but not 1 and 0 at the same time i.e. the superposition state. In other words, while we may be able to create qubits that express multiple states simultaneously, we still do not possess the capability of deriving algorithms for those states, and thus, we cannot make sense of them within the bounds of computing.

How close are we actually to quantum computing?

Addressing point #2, assuming we eventually solve the above obstacles, we may still be decades, if not centuries, away. The important question to explore is: how close are we actually to quantum computing?

  1. China has managed to send quantum encoded data over more than 1.2km via a satellite relay. (Previous attempts, using fibre optic only led 300m plus or minus);
  2. “Michael J. Biercuk, Professor of Quantum Physics and Quantum Technology at the University of Sydney, has pointed out that 50 qubits would not be sufficient for cracking asymmetric encryption and that the number of qubits needed would be significantly higher” than initially thought. This suggests that despite China’s achievement, we are still far from the devastating power of quantum computing;
  3. Google managed to generate quantum computers with up to 72 qubits. However, these are nowhere close to usable for practical applications. While quantum computers will be primarily used for research purposes, normal computers are still faster and more economical in solving most problems.

 In conclusion, it is debatable whether blockchain should concern itself with quantum computing.

  1. First, it could take decades until we can make qubits communicate with each other and develop the appropriate algorithms to retrieve the information.
  2. The first quantum computers will likely cost millions and be unobtainable for the average person. (But then again, that’s was the original assumption for what we thought about standard computers and, 30 years later, home computers are everywhere).

Alternative cryptography (Potentially Quantum Resistant*)

Regardless, some DLT projects are implementing preemptive solutions to protect themselves from the “inevitability” of quantum computing. The difficulty lies in designing a system for a future, speculative, and largely undefined vulnerability. As such, blockchains take several different approaches to implementing defense measures:

Defense through quantum computing

If you can’t beat them, join them. One alternative might be to use quantum computing for key encryption. Quantum key distribution might be unhackable because the “shared encryption key is embedded in quantum entangled particles of light.” (3) “When two quantum particles are entangled, they share the same existence. This happens when they interact at the same point in space and time.” (6) If an attacker intercepts one of the particles, all of the particles would become useless. The state is composed of several qubits; if one of these is missing, then the final state cannot be reconstructed. However, this does not mean that this form of encryption would be completely bulletproof; attackers could still grab encryption data from the end-point devices which do not run on quantum computers. It would merely (conceivably) make the transfer of data impenetrable.

Lattice cryptography

A second approach is based on the principle of solving systems of multivariable polynomials, “finding the shortest distance from a point to an n-dimensional skewed grid of other points, and finding the closest bit string to a set of other bit strings.” (5)

For example, if Alice wants to send Bob a message, she could identify the message with a point in Bob’s n-dimensional grid. To make the point more difficult to identify by another party, Alice could add some “noise” to it (i.e. distorting the original point by moving it a little off the original grid). “If n is huge and the angles in the grid are skewed — meaning, the angles are very far from right angles — it will be difficult “for Eve the Eavesdropper to figure out Alice’s original point, and a quantum computer doesn’t seem to help much.” (5) However, Bob (and only Bob) will have a “different set of lines drawn through the same points, but with angles closer to 90 degrees. This serves as a “trap door”, which allows him to recover the point and the message. (5)

N-dimensional grid (Source: 5):

One of the benefits of lattice cryptography is that it requires less computation to produce than conventional cryptography methods.

However, lattice cryptography is a very different approach than the previously mentioned quantum key approach. Unlike with quantum keys, lattice cryptography merely makes the encryption stronger without requiring additional computation. “Quantum cryptography merely adds a quantum layer to the standard blockchain protocol.” (6) Lattice cryptography is only another security layer. It’s not necessarily uncrackable and the effectiveness depends largely upon how powerful the attacking quantum computer actually is.

Summary/Conclusion

At the moment, due to how many current obstacles still fact quantum computing development, quantum resistance is used generally as a buzzword by projects to market to investors.   Solutions such as lattice cryptography at this stage are not particularly relevant because we do not know when the first 50 qubits + quantum computer will be developed. We also do not know until adequately tested if lattice cryptography will actually be quantum resistant. And we certainly can’t develop quantum keys until we have quantum computers. For now, the debate will rage on whether blockchains should focus on preventing known and anticipated attacks, or also focus on speculative ones such as quantum computing.

Ask the Eden Labs team questions on our Telegram and receive updates, analysis, and research insights.

Sources

  1. https://www.research.ibm.com/5-in-5/lattice-cryptography/
  2. https://hackernoon.com/quantum-computing-explained-a114999299ca
  3. https://medium.com/threat-intel/quantum-computing-encryption-d0bf133cc63d
  4. https://www.technologyreview.com/s/604242/googles-new-chip-is-a-stepping-stone-to-quantum-computing-supremacy/
  5. http://nautil.us/blog/-how-classical-cryptography-will-survive-quantum-computers
  6. https://www.technologyreview.com/s/611022/if-quantum-computers-threaten-blockchains-quantum-blockchains-could-be-the-defense/
  7. http://www.qubitcounter.com/
  8. https://www.technologyreview.com/s/610274/google-thinks-its-close-to-quantum-supremacy-heres-what-that-really-means/
Share this:

Leave a Reply

Your email address will not be published. Required fields are marked *