Survey on Use of Computational Complexity to Protect Crypto-currency Against Quantum Threat

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. Quantum-safe 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.

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 effi- 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 q-bit, or quantum bit. Q-bit 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 inde﬿nite 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 D-Wave. Despite the fact that many specialists doubted its functionality, the Google representa- tives con﬿rmed that this computer is extremely effective 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 scienti﬿c work .[VSDN15].

1

Figure 1: shows relationship with BQP to other classes.

2.2Crypto currency and how they use cryptography

SHA-256(256-bit Secure Hash algorithm) extensively used by Bitcoin for several operation/ RIPEMD- 160 used in address creation. Original bitcoin wallet used AES-256-CBC for encrypting all pri- vate keys using a master key, and the master key was encrypted by a SHA-512 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 difficult 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 peer-to-peer 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 difficult 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 speci﬿c 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 effecting in digital signature , we need to know some basics of shor’s algorithm . It is in BQP class . In computational complexity theory, BQP (bounded-error 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 efficient algorithm to solve it. But Shor’s algorithm

.[Sho99] shows that in Quantum computer it is possible to solve.

2

3Post-Quantum Security Concerns

3.1Effect 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 SHA-512 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.2Effect 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.3Effect 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 efficient 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, different quantum algorithm might have different 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

Proof-of-work need to have two basic property one is difficulty 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 proof-of 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 hash-cash style proof-of-work [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 different post quantum public keys, here type 1 are lattice based, type 2 are multivibrate polyno- mials , hashing based are classi﬿ed 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 difficult to implement [DA17].

4.3Query Complexity and Cryptographic Lower Bounds

In 2017 it was introduced [HY17] ,a new total search problem called End-of-Metered-Line (EOML) for order to study hardness of continuous local search, which is similar in spirit to the End-of-Line problem. This could extend Cryptographic ability to work on quantum computer.

5Open Questions

As proof-of-work 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] Siun-Chuon Mau Scott Alexander Eric van den Berg Artur Scherer, Benoˆıt Valiron and Thomas E. Chapuran. Concrete resource analysis of the quantum linear-system 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 Post-Quantum 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 graph-theoretic proof-of-work. 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 Twenty-Eighth Annual ACM-

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

Applied Mathematics, 2017.

[Kho17]

Alex Biryukov Dmitry Khovratovich. Equihash: Asymmetric proof-of-work 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/ the-future-of-

bitcoin.html.

[Neo]

NEO White Paper A distributed network for the Smart Economy.

[PK17]

Pierre-Alain 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]

quantum-computers-will-kill-crypto-currencies

http://coinews.io/en/category/5-

blokchejn/article/104-quantum-computers-will-kill-crypto-currencies.

[Sat]

Satoshi Nakamoto: Bitcoin QT, the original and

the most prominent bitcoin soft-

ware distribution which implements a full peer-to-peer network node. Originally de-

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

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

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

https://github.com/bitcoin/bitcoi.

[Sho99]

Peter W. Shor. Polynomial-time 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

 

 

Advertisements

About kishor datta gupta

Graduate Research Assistant at University of Memphis Software Engineer at Silicon Orchard LTD. Former Research Assistant at Lamar University Former Software Engineer at Samsung R&D Institute Bangladesh Studies Ph.D. Computer Science at University of Memphis Studied Masters of Science in Computer Sciences at Lamar University Studied BSC in CSE at Khulna University of Engineering and Technology Studied HSC (completed) at Chittagang college 04-06 Studied High school at ST. Placid's High School'04 Studied Junior Secondary School at Saint Mary's School Lives in Memphis, Tennessee
This entry was posted in C#. Bookmark the permalink.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s