Show All
The concept of a peer-to-peer internet ledger of value, recorded as a blockchain and secured by proof of work was rst reported in 2008. Bitcoin remains the most widely used cryptocurrency to date. Hundreds of similar cryptocurrency ledgers have been subsequently created but with few exceptions they rely on the same elliptic curve public-key cryptography (ECDSA) to generate digital signatures which allow transactions to be veri ed securely. The most commonly used signature schemes today such as ECDSA, DSA and RSA are theoretically vulnerable to quantum computing attack. It would be valuable to explore the design and construction of a quantum resistant blockchain ledger to counter the potential advent of a sudden non-linear quantum computing advance. It is currently only possible to spend (unspent transaction outputs) from a bitcoin address by creating a transaction containing a valid elliptic curve (secp256k1) signature from the private key (x 2 Njx < 2256) for that speci c bitcoin address. If the truly randomly generated private key is kept secret or lost then no funds can reasonably be expected to move from that address ever. The chance of a speci c bitcoin private key collision is 1 in 2256. The probability of any bitcoin address key collision can be estimated using the Birthday Problem. The number of bitcoin addresses which must be generated to result in a 0.1% chance of a collision is 5.4x1023. However, when a transaction is signed then the ECDSA public key of the sending address is revealed and stored in the blockchain. Best practice is for addresses not to be re-used, but as of November 2016 49.58% of the entire bitcoin ledger balance is held in addresses with exposed public keys. RSA, DSA and ECDSA remain secure based upon the computational diculty of factorisation of large in- tegers, the discrete logarithm problem and the elliptic-curve discrete logarithm problem. Shor's quantum algorithm (1994) solves factorisation of large integers and discrete logarithms in polynomial time. Therefore, a quantum computer could theoretically reconstitute the private key given an ECDSA public key. It is thought ECDSA is more vulnerable to quantum attack than RSA due to the use of smaller keysizes, with a 1300 and 1600 qubit (211) quantum computer able to solve 228 bit ECDSA. Public quantum computer development has not passed beyond 25 qubits or the factorisation of small num- bers (15 or 21). However, in August 2015 the NSA deprecated elliptic curve cryptography ostensibly based 1 upon quantum computing concerns. It is unclear how advanced quantum computing may be presently or that any breakthroughs in this eld will be publicised to allow cryptographic protocols in common usage in the internet to be made post-quantum secure. With somewhat anti-establishment origins, bitcoin could nd itself the earliest target of an adversary with a quantum computer. If a signi cant quantum computing advance were to occur publicly, node developers could implement quantum-resistant cryptographic signature schemes into bitcoin and encourage all users to move their bal- ances from ECDSA-based addresses to new quantum-safe addresses. To mitigate the proportion of e ected addresses it would be reasonable to disable public key recycling at the protocol level. Such a planned up- grade would also result in the possible movement of the 1 million coins belonging to Satoshi Nakamoto - with associated price volatility. A less favourable scenario would be a silent non-linear quantum computing advance followed by a nu- anced quantum computing attack on bitcoin addresses with exposed public keys. Such thefts could have a devastating e ect upon the bitcoin exchange price due to new heavy sell pressure and a complete loss of con dence in the system as the scale of thefts become known. The role of bitcoin as a store of value ('digital gold') would be very badly damaged with extreme consequences for the world. In this context the authors believe it is reasonable to experiment with quantum-resistant cryptographic signatures in a cryptocurrency ledger and potentially create a backup value store in the event of a black swan. There are several important cryptographic systems which are believed to be quantum-resistant: hash-based cryptography, code-based cryptography, lattice-based cryptography, multivariate-quadratic-equations cryp- tography and secret-key cryptography. All these schemes are thought to resist both classical and quantum computing attack given suciently long key sizes. Forward secure hash based digital signature schemes exist with minimal security requirements that rely only upon the collision-resistance of a cryptographic hash function. Changing the chosen hash function produces a new hash-based digital signature scheme. Hash-based digital signatures are well studied and represent the primary candidate for post-quantum signatures in the future. As such they are the chosen class of post-quantum signature for the QRL.
