A QUANTUM LEAP INTO INSECURITY

Trading cryptocurrencies in the age of supercomputers will be less safe than ever? Yup, but it’s not so bad.

Security has always been a scarce resource in the world of digital data. Although based on advanced cryptography the nascent blockchain economy is obviously in no better position. And things tend to be getting only worse. The potential advent of the quantum computer can cause havoc and disbalance to the realm of Bitcoin and Etherium, similar to what the first atomic bomb, Little Boy, did to the mid-last-century world of conventional weapons. Someone will achieve supremacy, quantum supremacy. “Quantum supremacy” aka “quantum advantage” is, in fact, a term used to describe the potential ability of quantum computing devices to solve problems that classical computers practically cannot. Why?

Quantum computers are faster. Much faster. While in classical computing the data is encoded into binary digits (bits), which are always in only one of two definite states (0 or 1), quantum computers, due to the special nature of quantum states, can use bits (called qubits), that can act as both 0 and 1 at any given time. Qubits can do this trick because of their ability to superpose. Remember the famous Schroedinger’s cat paradox whare a cat may be simultaneously dead and alive in a closed box? This enables each qubit to perform two calculations at once. Better still (or worse?) if two qubits are bound-up (entangled) through quantum mechanics, they can then perform four synchronous calculations; three qubits are capable of ²³ or eight calculations; and so on. To give you an idea, a theoretical quantum machine with 300 qubits could do 2 to the power of 300 calculations in a single parallel computation. Which is about as many as there are particles in the visible universe.

Bitcoin is safe for now?

The implications of quantum supremacy for blockchain protocols and cryptocurrencies are enormous. To begin with, a quantum computer will outdo conventional machines in performing the hashcash proof of work function used in Bitcoin. So if it falls into malicious hands it could break Bitcoin? Not yet. According to the recent research paper titled Quantum attacks on Bitcoin, and how to protect against them (by Divesh Aggarwal, Gavin K. Brennen, Troy Lee, Miklos Santha, and Marco Tomamichel), this is still relatively far away:

(https://arxiv.org/pdf/1710.10377.pdf)

This plot shows two estimates of the hashing power (in hashes per second) of the bitcoin network… vs. a single quantum computer … as a function of time for the next 25 years. We give more and less optimistic estimates and uncertainty regions…. The model is described in detail in Appendices B and C. Prior to 2028(in the more optimistic estimate) there will not be any quantum computer with sufficiently many qubits to implement the Grover algorithm.

Too early to panic, right? Quantum computing is still in its a nascent phase. The biggest bottleneck of current quantum architectures is slow gate speeds. In quantum electronics, logic gates are basic quantum circles (operating on a small number of qubits) that serve as building blocks of larger circuits like classical logic gates do for conventional digital circuits. At the current difficulty level, slow logic gates essentially defeat the quantum speedup. The existing quantum machines have no advantage over the powerful ASIC hardware used for Bitcoin hashcash PoW. According to the Aggarwal, Brennen, Lee, Santha and Tomamichel research, in order to successfully outperform them, quantum architectures must allow gate speeds up to 100 GHz or 100 times faster than now, which is unlikely to happen before 2028. At which point classical hardware may be much faster, and quantum technology might be so widespread that no single quantum enabled agent could dominate the PoW problem.

2028 may seem far away. But as the authors of the research rightfully admit, they have described attacks on Bitcoin, using only the already existing quantum algorithms and error correction schemes:

(https://arxiv.org/pdf/1710.10377.pdf)

It is important to keep in mind that there are several avenues for improved performance of quantum computers to solve the aforementioned problems. First, the assumed error correction code here is the surface code which needs significant classical computational overhead for state distillation, error syndrome extraction, and correction.Other codes which afford transversal Clifford and non-Clifford gates could overcome the need for slow state distillation. In fact the slow down from classical processing for syndrome extraction and correction could be removed entirely using a measurement free protocol, which in a recent analysis show error thresholds only about 5 times worse than the measurement heavy surface code. This could potentially dramatically improve overall speed of error correction. Second, reductions in logical gate counts of the quantum circuits are possible as more efficient advanced quantum-computation techniques are being developed. For example, using a particular large-size example problem (including oracle implementations), a direct comparison of the concrete gate counts,obtained by the software package Quipper, has been achieved between the old and the new linear-systems solving quantum algorithms, showing an improvement of 11 several orders of magnitude. Given that the quantum Shor and Grover algorithms have been well studied and highly optimized, one would not expect such a dramatic improvement, nonetheless it is likely some improvement is possible.Third, different quantum algorithms might provide relative speedups… Recent work by Kaliski presents a quantum algorithm for the Discrete Logarithm Problem: find m given b=am,where b is a known target value and a is a known base, using queries to a so called “magic box” subroutine which computes the most significant bit of m By repeating queries using judiciously chosen powers of the target value, all bits of m can be calculated and the problem solved. Because different bits are solved one by one the problem can be distributed to multiple quantum processors. Each processor requires a number of logical qubits comparable to solving the entire problem, but the overall time would be reduced by the parallelization. Furthermore, the overhead for quantum error correction is likely reduced as the phases in the quantum fourier transform part of the circuit need not be as accurate as in the original Shor algorithm.

Dated October 2017 the research was compiled some 5 months prior to release of Bristlecone, the 72-qubit quantum processor . The device made by Google was presented on March 5th, 2018 at the annual American Physical Society meeting in Los Angeles. Although the 72 qubits are physical but not logical, the Google team says it may theoretically be able to achieve “quantum supremacy”.

(https://ai.googleblog.com/2018/03/a-preview-of-bristlecone-googles-new.html)

We are cautiously optimistic that quantum supremacy can be achieved with Bristlecone, and feel that learning to build and operate devices at this level of performance is an exciting challenge! We look forward to sharing the results and allowing collaborators to run experiments in the future.

However, even if it will take quantum machines some time to outcompete conventional miners, certain types of attack can become more feasible for quantum-armed hackers much earlier than 2028. This may be true for attacks on mining pools that use smart contracts as a reward to pool miners for withholding their blocks.

(https://arxiv.org/pdf/1710.10377.pdf)

For example, given the optimistic assumptions… where the effective hash rate scales like h = 0.04 × s √D, at D = 10 and s = 50GHz, the fractional hashing power of a group of 20 quantum machines running in parallel relative to total hashing power is 0.1%. This would allow for a quantum attack on pool mining with minimal bribing cost that would reduce pool revenue by 10%.

Hodl tight to your wallets

Quantum computers are way better than classical computers at solving particular types of problems, especially those that have to do with prime factoring natural numbers. Classical machines can achieve that only by exhaustive enumeration which means that the number of computations will grow exponentially with every additional digit of the number (each digit will increase the calculation time by a factor of 10). Quantum computer will only need as much time as there are digits in the number to the second power.

This negates the very fundamental principle of modern cryptography based on the RSA algorithm: prime factoring unknown big numbers is unachievable in a reasonable time frame. Not any more. The security of the Bitcoin system depends on the difficulty of the Elliptic Curve Discrete Log Problem (ECDLP). While it will still take ages to solve with classical computers, quantum Shor algorithm may be able to crack it much faster, All it takes to render the Bitcoin security scheme completely helpless is a sufficiently powerful quantum machine. According to the Research, the Bitcoin network may prove vulnerable in at least three major ways:

(https://arxiv.org/pdf/1710.10377.pdf)

1. (Reusing addresses) To spend bitcoin from an address the public key associated with that address must be revealed. Once the public key is revealed in the presence of a quantum computer the address is no longer safe and thus should never be used again. While always using fresh addresses is already the suggested practice in Bitcoin, in practice this is not always followed. Any address that has bitcoin and for which the public key has been revealed is completely insecure.

2. (Processed transactions) If a transaction is made from an address which has not been spent from before, and this transaction is placed on the blockchain with several blocks following it, then this transaction is reasonably secure against quantum attacks. The private key could be derived from the published public key, but as the address has already been spent this would have to be combined with out-hashing the network to perform a double-spending attack. As we have seen in Section III A, even with a quantum computer a double-spending attack is unlikely once the transaction has many blocks following it.

3. (Unprocessed transactions) After a transaction has been broadcast to the network, but before it is placed on the blockchain it is at risk from a quantum attack. If the secret key can be derived from the broadcast public key before the transaction is placed on the blockchain, then an attacker could use this secret key to broadcast a new transaction from the same address to his own address. If the attacker then ensures that this new transaction is placed on the blockchain first, then he can effectively steal all the bitcoin behind the original address.

We view item (3) as the most serious attack. To determine the seriousness of this attack it is important to precisely estimate how much time it would take a quantum computer to compute the ECDLP, and if this could be done in a time close to the block interval.

Quantum problem — quantum solution

The good news is that quantum mechanics is a double-edged sword that can work equally effectively for both the malefactors and the good guys. Here comes quantum cryptography. The quantum-based system of data encryption uses another important characteristic of qubits: unlike conventional bits, they cannot be copied secretly. Any attempt to eavesdrop on a quantum-encrypted communication will destroy the quantum superposition and hence will not go unnoticed. In more scientific terms the intruder-proof quantum encryption is achieved by utilizing three fundamental laws:

1. The uncertainty principle (that limits the amount of total information that can be extracted from measurements on pairs of conjugate variables)

2. The no-cloning theorem (that prevents the creation of an identical copy of an unknown arbitrary quantum state)

3. The existence of entanglement (by which two physically separated particles are intertwined in such a way that interacting with one of them unavoidably affects the state of the other).

Because of these three principles, any data leakage from a quantum channel will inevitably cause the transmitted information to degrade, provoking an increase in the quantum bit error rate which can be measured by an alert system. Quantum cryptography and it’s the most technologically mature incarnation, quantum key distribution (QKD ), have already been experimentally demonstrated and implemented in a commercially available product. QKD allows two legitimate parties to safely share private keys via public optic fiber communication networks.

(http://publications.jrc.ec.europa.eu/repository/bitstream/JRC107386/jrc_report_quantumcommunications.pdf) (The Impact of Quantum Technologies on the EU’s Future Policies, Adam M. Lewis, AML, Martino Travagnin, MT)

Quantum key distribution is based on a fundamental principle of quantum physics, namely that under certain conditions it is impossible to gain information about quantum states being transmitted from a sender Alice to a receiver Bob without perturbing the states. This principle can clearly be exploited for communications security purposes and, in particular, to establish asymmetric encryption/decryption key, since it allows one to detect the activity of an eavesdropper, assess the amount of leaked information and take the necessary countermeasures to ensure the secrecy of the key. Several different QKD implementations exist, all of them requiring as initial resources a public quantum channel and an authenticated public classic channel. … From this point of view, QKD can be seen as a key expansion technique that has no classical counterparts, since it exploits quantum physics to expand the entropy of the short authentication key to any required level.

QKD in praxis

Quantum communications are a vibrant field with many large business and government actors already involved. Which is no surprise given the huge and inescapable implications of cryptography for both economy and national security. The key market players range from telecom and electronics giants to defence majors and national research institutes from across the globe: NTT (JP), NEC(JP), Mitsubihi (JP), Fujitsu (JP), lNICT (JP), Toshiba(JP), Qasky(China), ROI Optoelectronics Technology (China), IDQ-Jiuzhou Quantum Technologies (China), Huawei (China), Alibaba (China), ZTE(China), South Korea Telecom (SK), Samsung (SK), Korea Telecom(SK), Senetas (Australia), QinetiQ (UK), British Telecom (UK), KPN (NL), Cryptographiq Limited (UK), Thales (FR), SmartQuantum (FR), SeQureNet (FR), Swisscomm(CH), Siemens (GER), AIT Austrian Institute of Technology (Austria), Telefónica (ES), Nokia (FI), MagiQ (USA), BBN Raytheon (USA), Applied Communication Sciences (USA), Batelle (USA), Alcatel (USA), Oak Ridge National Laboratory (USA), NIST — National Institute for Standard and Technology (USA), Darpa (USA), Los Alamos National Laboratory (USA), Nucrypt (USA), Qubittek (USA), Boeing (USA), AT&T(USA).

Quantum-protected platform

A prominent place among the early developers of safe data transmission networks belongs to the QUUBE Project.

Their quantum cryptography solutions have already been recognized by major domestic and international businesses and validated by cooperation agreements. The Centre claims to have created the most efficient error correction system for quantum keys currently available. In 2018 researchers from the QUUBE presented a quantum-safe blockchain trading platform that utilizes quantum key distribution. The most significant attempt at commercial implementation to date, a joint effort with a team of Block A developers and venture capitalists. A Beta version of the platform will be rolled out as early as November this year.

🌐 Website https://quube.exchange
✉️ Telegram Group
https://t.me/QuantumWarriors
🗣 Steem https://steemit.com/@quube-exchange
📸 LinkedIn https://www.linkedin.com/company/quubesecurityexchange
👤 Facebook https://facebook.com/QuubeQuantum
📷 Instagram
https://instagram.com/quube_exchange
🐥 Twitter https://twitter.com/quube_exchange
⭕️ Medium https://medium.com/quubee-exchange
⚙️ GitHub https://github.com/Quube-Exchange-2019
🅱️ Bitcointalk
https://bitcointalk.org/index.php?topic=5180249
https://en.bitcoinwiki.org/wiki/QUUBE.EXCHANGE
🌐 Website https://quube.exchange