If the era of quantum computing comes, is our bitcoin safe?

Written by: Li Yu, founder of Ambi Lab, Guo Yu

Correction: Guo Yu

Source: Chain smell

Every time there is news of quantum computing, people have to worry about bitcoin once. The reason is simple. Bitcoin is based on cryptography, and cryptography is based on some kind of computational impossibility. If quantum computing makes calculations that would otherwise be impossible or difficult to achieve become measurable, then this cryptographic approach will fail.

• Xiao Lei: Blockchain is "nuclear energy", bitcoin is "atomic bomb", who is the opponent?
• Bitcoin cash is being questioned, unknown miners control over 50% of computing power for 24 hours
• Speed ​​Reading | Twitter founder Zuckerberg teach how to properly enter the money circle; the fat of the agreement: Reflections from a cost value

But this kind of worry is superfluous. The reason is equally simple: as long as we have calculations that cannot be completed by quantum computing, can we not? The cryptographic method (quantum security cryptography) built on this calculation can not be solved by quantum computing, and then the bitcoin can be upgraded to the cryptography method.

The "difficult problem of lattice" is a typical representative, and even for quantum computing, it maintains computational impossibility. Based on the "ignorance" of human beings, we can always find ways to live under the protection of cryptography.

Cryptographic algorithm in Bitcoin

We know that the Bitcoin wallet address corresponds to a public key and a private key. Only the private key can use the bitcoin in the wallet, but the private key is secure and cannot be calculated by the wallet address or public key.

How is this achieved? Let's start with the billiard hall.

You go to the billiard hall to play billiards, put a ball in a position at the bottom of the billiard table, call it point A, then you hit the ball out, assuming that you hit the ball with great strength, then the ball starts from point A It always hits a point on one side of the pool table, and then it will bounce from that point to another point on the other side of the pool table… it may bounce B times (say 10,000 times) and finally Stop at a point on one side of the pool table and call it C.

At this time your friend is coming. He can see the position of the billiard at point C. You tell him the angle of the ball's initial position A and the angle of the shot. How many times has he played in the middle of the ball, that is, what is B? Your friend should not answer it at the moment.

This is a simple public and private key generation algorithm, C (location) is the public key, and B (number of times) is the private key. In the case where we know that point A and B bounce, we can get point C; but if we only know point A and point C, it is difficult to calculate the number of bounces B.

In true cryptography, the side of the pool table is replaced by an elliptical curve , A is a fixed point on the elliptical curve (actually an elliptical group) , which hits itself (the ball is hit from the tangent position of the point) ) , the ball hits the ellipse group and hits B times. Finally, it falls on a point of the ellipse group. It also needs to do another mapping on the point, with a point C on the ellipse group. C is the public key and B is the private key.

This is the famous elliptic curve algorithm , used to generate public and private keys, and is the first cryptographic method in the bitcoin system.

The elliptic curve algorithm is difficult to crack (based on "discrete logarithm difficult problem") , but it can't be cracked. The powerful quantum calculation can find the polynomial algorithm, and calculate B through A and C, that is, the private key can be calculated by public key. . Therefore, if you really enter the era of quantum computing, the elliptic curve algorithm needs to be replaced by a new anti-quantum computing algorithm.

Quantum Computation and Elliptic Curve Algorithm

The security of the elliptic curve digital signature algorithm used by Bitcoin is 2^128 (the order of the secp256-k1 curve group is close to 2^256, and the complexity of the elliptic curve attack algorithm is about O(sqrt(N)), for 2 ^256 squares, get 2^128). This is an astronomical number.

In the case of quantum computing, using the Shor algorithm proposed by Peter Shor, the complexity of attacking an elliptic curve is probably O(log(N)^3). For bitcoin, the theoretical computational magnitude is 128^3. Times.

Related papers show that constructing a quantum computer that attacks the secp256-k1 curve, assuming that the computer can reduce the bit error rate to 10^-4, then hopefully within 1.7 days with 1.7 million qubits Complete the calculation.

In the Bitcoin system, there is another cryptographic method, the hash function SHA-256 , which is used to generate the wallet address corresponding to the public key. The algorithm is well understood by converting an input into an output in an irreversible manner. It has a very strong unidirectionality and it is impossible to calculate the input through the output.

Therefore, the hash function can only be cracked by violent means, that is, transforming the input value and trying again and again, until the target output value can be calculated with an input value.

Compared to classic computers, quantum computers have considerable advantages in brute force search, but they are still a polynomial level of performance optimization. We can maintain security by doubling the number of security bits, such as SHA-512.

The bitcoin wallet address is obtained by two hash calculations of the public key, one is SHA-256 , and the other is RIPEMD-160 (another hash function) . It is difficult for quantum computing to break through two hash passes through the wallet address. "Bumped" the public key. Quantum Computation and SHA-256 The current acceleration of SHA-256 in quantum algorithms is the Grover algorithm proposed by Lov Grover in 1996, which can improve the performance of brute force search to square times. Suppose we want to find a pin in a huge N × N square. Classic computers need to search each square one by one. In the worst case, we need to search N×N times; but the Grover algorithm is even in the worst case. Also only need to search N times. To sum up: There are two basic cryptographic algorithms in Bitcoin, one is the elliptic curve algorithm, and the other is the hash function SHA-256. At present, the efficient quantum computing method of the former can be found and cracked; but the latter's efficient quantum computing method is not found. Of course, the premise of cracking is that quantum computing is really strong enough to know that Google's latest quantum chip has only 54 qubits.

Is our bitcoin safe?

If we enter the era of quantum computing, we only need to generate the public key, private key, and wallet address using the cryptographic algorithm against quantum computing. But if the user fails to upgrade the public key private key, will the bitcoin in their wallet be stolen? the answer is negative.

There are roughly the following situations:

1. If the bitcoin in the wallet address has never been used, then the public key of the address is not known, and everyone knows only the wallet address (only when we spend bitcoin on an address) The public key is given, but even if it has only been spent once, the public key will be broadcast to the entire network). As mentioned earlier, SHA-256 is difficult to crack by quantum computing, which means that other people cannot calculate the public key through the wallet address. Therefore, even if the private key can be calculated by the public key, the wallet addresses that have not exposed the public key are safe.

2. If there is a good bitcoin usage habit, a wallet address is used only once, then the same is true, the public key of the new address is not known, and the bitcoin in the new address is safe.

3. If the user reuses a wallet address, the public key corresponding to the address is exposed; if the quantum calculation breaks the elliptic curve algorithm, the bitcoin in the address is in danger of being stolen.

According to statistics, nearly 5 million bitcoins are stored in the address exposed by the public key, and there are nearly 1.77 million bitcoins using P2PK addresses. This is the earliest bitcoin account format. The key is public, including the account that is considered to be Nakamoto. If these bitcoins do not change addresses, they are within the scope of quantum computing attacks. (Source: Ambi Lab)

In addition to the wallet address, there is another important place in the Bitcoin system that uses SHA-256, which is mining. Mining is the process of violently cracking the hash function. By adjusting the input value, it collides with the output value of the target interval.

As mentioned above, in theory, quantum computer chips can "crush" classic computer chips in violent search, but we also need to consider its technological development level and chip manufacturing process. In addition, the chip is constantly upgrading with the development of technology. The impact of quantum computing on mining is more of an economic issue of chip upgrade than security.

Security under quantum computing: lattice password

At the same time as the development of quantum computing, quantum security cryptography is also developing rapidly. The most representative one is the " lattice code ", which is a lattice-based cryptography .

"Grid" is a vector space with a coefficient of integer. It can be understood as a high-dimensional space. It has two basic "difficult problems", one is the shortest vector problem, and the other is the nearest vector problem. The complexity of exponential time is needed. If the factor is polynomial, there is no polynomial time algorithm for this kind of problem, and it is also a computational impossibility for quantum computing.

This sounds a bit abstract, maybe you can understand it by: draw a lot of black dots on a piece of A4 paper with a pen, then change the pen to draw a red dot on the paper. What we need to do is find the distance red dot. The nearest black dot, this is easy; now from the 2D space of A4 paper to a 3D space, imagine a lot of black dots floating in the space, then put a red dot into it, also find the nearest red dot The black point, this is not very difficult, but compared to the two-dimensional space, its difficulty is no longer at a level.

Now, we turn the three-dimensional space into a three-dimensional space. Given a red dot to find the black point closest to it, this black spot must exist, but think about it, is it almost impossible to find out? This is a difficult problem.

The grid space is similar to the elliptic curve. On the elliptic curve, there can be a mathematical formula (elliptic curve algorithm) to put the public and private keys at the ends of an equation. In the grid space, there are also mathematical formulas (such as the LLL algorithm) that can be similar to black and red dots. Things are placed at both ends of an equation, then we can use this formula to generate public and private keys.

In the elliptic curve algorithm, the traditional computer cannot calculate the private key through the public key because of the "difficult logarithm problem" . In the algorithm of the lattice cipher, the quantum computer cannot calculate the private key through the public key because of the "difficult problem" . .

The lattice password develops very fast. Based on the grid, we not only have public and private keys against quantum computing, but also a series of cryptographic algorithms or protocols that are resistant to quantum computing and correspond to the concept of classical cryptography. They can be used for digital signatures and secrets. Key exchange, zero-knowledge proof, and other application areas.

The universe believes in encryption. Encryption is easy and decryption is difficult. "

In the foreseeable future, this is still the case. So don't worry, it's the same for Bitcoin, and for blockchains. Reference material

[1] Arute, Frank, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Rupak Biswas et al. "Quantumsupremacy using a programmable superconducting processor." Nature 574, no. 7779 (2019): 505- 510.

[2] Andreas M. Antonopoulos answers questions about quantum computing: www.youtube.com/watch?v=eo7mwcsUbdo;www.youtube.com/watch?v=wlzJyp3Qm7s

[3] Gentry, Craig. "Fully homomorphic encryption using ideallattices." In Stoc, vol. 9, no. 2009, pp. 169-178. 2009.

[4] Aggarwal, Divesh, Gavin K. Brennen, Troy Lee, Miklos Santha, and Marco Tomamichel. "Quantum attacks on Bitcoin, and how to protect against them." arXivpreprint arXiv: 1710.10377 (2017).

[5]Stewart, I., D. Ilie, Alexei Zamyatin, Sam Werner, MF Torshizi, and William J. Knottenbelt. "Committing to quantum resistance: a slow defence for Bitcoin against a fast quantum computing attack." Royal Society openscience 5, no . 6 (2018): 180410.

[6] Regev, Oded. "Lattice-based cryptography." In Annual International Cryptology Conference, pp. 131-141. Springer, Berlin, Heidelberg, 2006.

We will continue to update Blocking; if you have any questions or suggestions, please contact us!