Digital currency built on cryptographic algorithms, But these algorithms are vulnerable to quantum computer computation ability. For post quantum computing era we have to prepare to reinvent digital security. Quantumsafe cryptographic algorithms can be answer for that. In this paper, we survey on how computational complexity could protect current digital currency from future quantum threat.
1 Motivation
Cryptocurrency such as bitcoin, etherium, and others are taking the world by the storm. It is a decentralized digital currency which is free from any government or institutional interferences and can operate in an open, peer to peer networks. The mining of these coins and transaction heavily relied on cryptographic computational complexity.Cryptographic protocols provide the founda tion for securing all blockchain operations like Tamper Resistance, Equivocation Prevention and Creation of new cryptocurrency units . Hash functions make it possible to represent data eﬃ ciently and formulate cryptographic puzzles for PoW schemes. Digital signature algorithms based on public key cryptography allow assurances of identity and origin for blockchain transactions. Now upcoming quantum Computer could threaten the whole mining and transaction procedure by breaking the cryptographic barrier. As quantum computer will be able to solve a large number of decomposition problems and the elliptic curve discrete logarithm in a very short time, it will going to make RSA and ECC based security worthless armor.[Neo].
As industry was searching to nd out quantum proof computational complexity , such as the Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP), which are considered to be the most reliable algorithm for resisting quantum computers[Neo]. But still these are not enough convincing to protect crypto currency.
2Background
2.1Quantum computer
The basic unit of quantum calculation is qbit, or quantum bit. Qbit can have two conditions (0 and 1) same as ordinary bit, but this is only the calculation of physical condition which forms this bit. But before this, a bit is in these two states simultaneously, and in the indenite number of conditions that is formed by its superposition. To put it simply, this allows quantum computers to process calculations that largely excess the potential of classic computers [qua].
The rst quantum computer has appeared in 2013, it was developed by the Canadian company DWave. Despite the fact that many specialists doubted its functionality, the Google representa tives conrmed that this computer is extremely eﬀective for the particular type of calculations[qua]. Technological giant has purchased a working prototype and tested it during a long period of time. The results of the testing were released in the form of scientic work .[VSDN15].
1
Figure 1: shows relationship with BQP to other classes.
2.2Crypto currency and how they use cryptography
SHA256(256bit Secure Hash algorithm) extensively used by Bitcoin for several operation/ RIPEMD 160 used in address creation. Original bitcoin wallet used AES256CBC for encrypting all pri vate keys using a master key, and the master key was encrypted by a SHA512 hash from the user passphrase. and Eliptic Curve DSA used to generate “Wallet” addresses and sign transac tions.ECDSA, especially secp256k1, not rarely used outside of Bitcoin, though it is an international standard that is generally accepted as secure.
Bitcoins use the concept of so called “Proofs or Work‿ which are solutions to certain very hard cryptographic puzzles based on hash functions. These solutions are NOT actually bitcoins. The puzzles are more of a part of the bitcoin trust architecture. In reality the puzzles are joint together to make a chain and as the length of this chain extend , so does the level of security . Bitcoins are handover to those people who produce these “Proofs or Work‿ which is a very diﬃcult computational complex task[CGN13].In a nutshell, bitcoin miners make money when they nd a 32 bit value which, when hashed together with the data from other transactions with a standard hash function gives a hash with a certain number of 60 or more zeros. This is an extremely rare event. It is in general believed that there is no way to produce these data otherwise than by engaging in very long and costly computation[Mar]. After the mine coin ownership of bitcoins is achieved through digital signatures: the owner of a certain private key is the owner of a certain quantity of bitcoins. This private key is the unique way to transfer the bitcoin to another computer or person. Cryptographic computations get executed by a peertopeer network of a growing network of currently some twenty thousand independent nodes[Mar] are the heart of the security assurance provided by this virtual currency system. It would be very diﬃcult and extremely costly for one entity to corrupt all these independent people. The sum of all this collective computational work provides some sort of solid cryptographic proof and prevents attacks on this system.There is a specic sort of distributed and decentralized electronic notary system without a central authority [Sat],
We can devide Quantum attack on cryptocurrency in three part
Attack on proof of work
Attack on signature schemes
Other unforeseeable attack
2.3Basics of Shors algorithm
To understand how Quantum eﬀecting in digital signature , we need to know some basics of shor’s algorithm . It is in BQP class . In computational complexity theory, BQP (boundederror quantum polynomial time) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances. It is the quantum analogue of the complexity class BPP [Wik], . Figure 1 shows relationship with BQP to other classes. A decision problem is a member of BQP if there exists an algorithm for a quantum computer (a quantum algorithm) that solves the decision problem with high probability and is guaranteed to run in polynomial time. A run of the algorithm will correctly solve the decision problem with a probability of at least 2/3.
In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these integers are further restricted to prime numbers, the process is called prime factorization. This was base of many Cryptographic algorithm. such as elliptic curves. When number was large there was no eﬃcient algorithm to solve it. But Shor’s algorithm
.[Sho99] shows that in Quantum computer it is possible to solve.
2
3PostQuantum Security Concerns
3.1Eﬀect of Grover’s algorithm
Grover’s algorithm [Gro96] shows in a quantum computer, If there is a M words in a dictionary, p
nd a word in that dictionary will take 2 M. So if a miner with a Quantum computer can mine a coin than other miner without quantum computer more faster[BLHI16].
One of the Way around of it is to move to SHA512 and increase the amount of proof of work. So for quantum computer it also take time. But it does not solve the problem entirely rather than delay it.
3.2Eﬀect of Shor’s algorithm
Shor’s algorithm changes the landscape of post quantum computation entirely, it shows that if shor’s algorithm implemented , digital signatures such as elliptic curve and RSA will be broken. Which means we cannot continue using signatures based on the factorization problem and discrete logarithm problem. Anyone with quantum computer can nd the private key if it have the public key. So cryptocurrency that means it can let anyone impersonate other users, thus open the way to steal money. which will bring the whole nancial system down [BLHI16]
3.3Eﬀect of error correction speedup
Classical error correction code need overhead for state distillation, error syndrome extraction, and correction.But this slowdown wont be needed in Quantum computer. It could be given advantage to design more complex cryptographic algorithm and help to secure the system. Also , reductions in logical gate counts of the quantum circuits are possible as more eﬃcient advanced quantum computation techniques are being developed.[DA17] .In a recent work .[ASC17] showed several orders of magnitude improvement between old and new linear systems solving quantum algorithms. Also, diﬀerent quantum algorithm might have diﬀerent speedup, and the overhead for quantum error correction is likely reduced as the phased in the quantum Fourier transform part of the circuit need not be as accurate as in the original Shor algorithm [DA17].
4Computational Complexity Against Quantum Threat
4.1Improving Proof of work
Proofofwork need to have two basic property one is diﬃculty of the problem have to be must harder and can be increase or decrease based on computing powers available in the network, but verifying this proofof work should be much easier than the nd the solution. And our discussion in section 3 establish that it also need to make sure there is no quantum advantage.
Currently some algorithm proposed which consider this such as Cuckoo Cycle[cyc15], which is based on nding constant sized subgraphs in a random graphs. Another one is Equihash .[Kho17] which basically founded on the generalized birthday problem. Also we can consider the Momentum [Lar14] focusing on collision nding in a hash functions.
Mostly all of them build on hashcash style proofofwork [DA17]. Which shows that even with use the Grover search , we have to also has necessity to a extra query of additional time by the quantum query lower bound. If this extra minimum time is S . All quantum computer have to consider this extra S time, whatever the quantum algorithm they used.[DA17]
4.2Improving Digital Signature
In the blockchain most important thing in signature key is length of public keys .Figure 2 shows diﬀerent post quantum public keys, here type 1 are lattice based, type 2 are multivibrate polyno mials , hashing based are classied as type 3 and type 4 is normally code based and its become clear that we should select type 1 and type 3 as respect to their sum of signature and public key length[DA17].
In XMSS it was assumed that the chosen hash function is a random oracle, and quantum computer can use Grover’s algorithm , and as we know that means half of the time needed in quantum computer than the classical computer. But if we see the lattice based signature scheme,
3
Figure 2: Post quantum public keys [DA17]
we can see that it has better advantage than hash based. As example DILITHIUM at 138but provide same level security in both classical and quantum computer.
From above discussion it seems Lattice based encryption is answer but some of the lattice based scheme such as BLISS which relied on the NP hardness of the NTRU problem and the assumption is , to solve this problem is equal to getting a short vector in a so called NTRU lattice. Recently it was proved [PK17] that it not suitable for large parameters also it is diﬃcult to implement [DA17].
4.3Query Complexity and Cryptographic Lower Bounds
In 2017 it was introduced [HY17] ,a new total search problem called EndofMeteredLine (EOML) for order to study hardness of continuous local search, which is similar in spirit to the EndofLine problem. This could extend Cryptographic ability to work on quantum computer.
5Open Questions
As proofofwork can change its hardness based on entire network computation power, there is many work around to adjust Qbit for that, but more of a concern is security of digital signature over the network. Lattice based Signature scheme are subject to Cache attacks such as CDT sampling and rejection sampling [BLHI16]. There were several counter measure proposed, but yet we are not able to establish a Quantum level signature scheme which is equivalent to its classical part. We need nd out more complex class problem to use which will have same hardness for both Quantum and classical computer.
6Summary
There are lots of research going on to prepare for post quantum era, Currently it seems further extension of lattice based signature schemes will be the answer and age of RSA and ECDSA is going to over. Although the Shamir who is one of the RSA inventor suggested that, noting could prevent cryptographic death , so we should prepare for open cryptographic world. However many other scientist rebutted him and lots of counter measure is being developed.
References
[ASC17] SiunChuon Mau Scott Alexander Eric van den Berg Artur Scherer, Benoˆıt Valiron and Thomas E. Chapuran. Concrete resource analysis of the quantum linearsystem algorithm used to compute the electromagnetic scattering cross section of a 2d target. Quantum Information Processing, 2017.
[BLHI16] Leon Groot Bruinderink, Tanja Lange, Andreas Hülsing, and Lodewijk Bonebakker ING. Towards PostQuantum Bitcoin. PhD thesis, Master’s thesis, Eindhoven Univer sity of Technology, 2016. http://repository. tue. nl/844305, 2016.
4
[CGN13] 
Nicolas T Courtois, Marek Grajek, and Rahul Naik. The unreasonable fundamental 


incertitudes behind bitcoin mining. arXiv preprint arXiv:1310.7935, 2013. 

[cyc15] 
John Tromp. Cuckoo cycle. a memory bound graphtheoretic proofofwork. BITCOIN, 


2015. 

[DA17] 
Troy Lee Miklos Santha Marco Tomamichel Divesh Aggarwal, Gavin K. Brennen. Quan 


tum attacks on bitcoin, and how to protect against them. arXiv, 2017. 

[Gro96] 
Lov K. Grover. A fast quantum mechanical algorithm for database search. in gary l. 


STOC, 1996. 

[HY17] 
Pavel HubáĿek and Eylon Yogev. Hardness of continuous local search: Query complexity 


and cryptographic lower bounds. In Proceedings of the TwentyEighth Annual ACM 


SIAM Symposium on Discrete Algorithms, pages 1352–1371. Society for Industrial and 


Applied Mathematics, 2017. 

[Kho17] 
Alex Biryukov Dmitry Khovratovich. Equihash: Asymmetric proofofwork based on 


the generalized birthday problem. Ledger, 2017. 

[Lar14] 
Daniel Larimer. Momentam. : http://www.hashcash.org/papers/momentum.pdf., 2014. 

[Mar] 
Maria Bustillos: The Bitcoin Boom, Appears in the New Yorker magazine online blog, 2 


April 2013 http://www.newyorker.com/online/blogs/elements/2013/04/ thefutureof 


bitcoin.html. 

[Neo] 
NEO White Paper A distributed network for the Smart Economy. 

[PK17] 
PierreAlain Fouque. Paul Kirchner. Revisiting lattice attacks on overstretched ntru pa 


rameters. in advances in cryptology. – EUROCRYPT 2017 – 36th Annual International 


Conference on the Theory and Applications of Cryptographic Techniques, 2017. 

[qua] 
quantumcomputerswillkillcryptocurrencies 


blokchejn/article/104quantumcomputerswillkillcryptocurrencies. 

[Sat] 
Satoshi Nakamoto: Bitcoin QT, the original and 
the most prominent bitcoin soft 

ware distribution which implements a full peertopeer network node. Originally de 


veloped by Satoshi Nakamoto, core developers are Satoshi Nakamoto, Gavin An 


dresen, Pieter Wuille, Nils Schneider, Jeﬀ Garzik, Wladimir J. van der Laan and 


Gregory Maxwell. Available at http://bitcoin.org/en/download with source code at 




[Sho99] 
Peter W. Shor. Polynomialtime algorithms for prime factorization and discrete loga 


rithms on a quantum computer. SIAM Journal on Computing, 1999. 
[VSDN15] 1 Sergei V. Isakov 1 Nan Ding 1 Ryan Babbush 1 Vadim Smelyanskiy 1 John Martinis 2 Vasil S. Denchev, 1 Sergio Boixo and Hartmut Neven1. What is the computational value of nite range tunneling? Technical report, Google, 2015.
[Wik] 
Wiki. Bqp. Technical report. 
5