Threats to BlockChain: Part 4 Quantum Computers

Quantum Computing is a new type of computer chip which promises exponentially faster processing than our current super computers.

BlockChain is secured by a mathematical algorithm that relies on the fact that today’s computers can’t process data quickly enough to ‘hack’ an identity on a BlockChain.

Therefore, if quantum computing becomes real, there is a potential weakness in the cryptography systems that underpin security on a BlockChain – as well as our current banking infrastructure, Internet payments, military and countless other applications.

Instead of using silicon to recognise an ‘on-off’ (1 bit) state to store data, it uses parts of an atom to store multiple states (on, off and a superposition of both).  This results in the number of calculations possible at any one time is significantly greater than today’s possibilities making it ‘faster’ than current computers significantly.

To indicate the improvement in speed, there is an exponential link between the size of a printed circuit and its enhancement.  Today’s smallest Intel chips on the market are around 15nm.  An atom is 0.1nm with its quantum components being tiny fractions of that.

Today, quantum computing is not a practical reality.  There are inherent problems with quantum computers, particularly around the stability of data storage in the quantum realm although companies such as Google are working on error-correction systems on these.

But, some think it’s just a matter of time.

Why does this affect BlockChain?

BlockChain technology relies on a type of mathematics called RSA Cryptography.

In this, a Secret Key is created to ‘sign’ transactions and a Public Key is created to prove that a transaction was ‘signed’ by the Secret Key.  This way if Bob has £10 and wants to pay Alice, he can create a transaction that moves money from his account into Alice’s by ‘signing’ it.  No one can dispute that Bob did this and somebody can tell he did do it by checking the transaction signature against his Public Key.

Therefore, it is critical that secret keys remain secret.

Should a criminal want to access your details or take money from you without your permission, they would need your Secret Key. They wouldn’t need access to your private residence or place of work, they would just need to guess it – no risk involved!  The BlockChain is stored on everybody’s computer, so the criminal wouldn’t even need to be connected to the Internet – they could just do it at home.

How Secure are Secret Keys?

Simplifying it significantly, Secret Keys are created by multiplying large numbers together.  Knowing those 2 large numbers enables you to create the Secret Key.  The Secret Key has something special about it – it is a prime number.

It turns out that trying to determine the Secret Keys is very difficult the bigger the number becomes. You need to find the numbers that are multiplied together to guess it.

Prime numbers aren’t divisible by any number except itself and 1. If the number wasn’t prime, you could guess the secret keys in multiple ways.

Imagine ’16’ was our Secret Key and a criminal has to guess 2 numbers that are multiplied together.  If they multiplied 1 and 16 they would get 16 .  If they multiplied 8 x 2, they would also get 16.  They also could multiply 4 x4 and get 16.  They could find our Secret Key in at least 3 different ways.

If the Secret Key was a prime number – 13 for example, then they can only find it one way – 1 x 13.  Therefore, it’s 3 times more difficult than the non-prime number.

Our secret key is 2 digits. Image if the Secret Key was 617 digits long!  How much time would it take to try every multiplication combination!  Millions of years at current computer speeds as it turns out.

There are optimisations of this sequential guess of multiplications such as the General Number Field Sieve algorithm but it wouldn’t decrease the time to find the Secret Key sufficiently.

How will it manifest?

The real problem to BlockChain technology is that the integers factored that make the Secret Key are quickly found by using a method known as Shor’s algorithm.  This algorithm is particularly suited to number crunching made possible by quantum computing.

Shor’s approach (again, hugely simplified) is to utilise a mathematical feature of factoring which produces patterns of number sequences in the remainders of divided primes.  These patterns can be used to determine the two integers that have been multiplied by seeing where the patterns are replicated when divided by different numbers.

This renders the RSA Cryptography which authenticates ownership and identity much less certain than todays standard.  Obviously, faith in the BlockChain is then undermined and can no longer be relied on as an guaranteed source of truth.

How to solve it?

There are several ways around this problem.

The first is to use a different type of cryptography, possibly McEliece or a lattice-based crypto system.  This removes the effectiveness of Shor’s solution.  However, it may be just a matter of time until mathematic shortcuts are found around these too.

Another option is to limit the speed at which guesses of the correct secret number key can be executed.  This can be done either through creating a speed-limited interface to the BlockChain or requiring a payment in micro-currency per use or guess of the secret key. Both of these are currently not feasible because the data in the BlockChain is stored locally in its entirety on a participating node.

Another option is to change how BlockChain currently works and spread data around the network, possibly in a way MIT’s Engima grid computer works.  This way the computer guessing the Secret Key would need to be connected to the Internet and therefore limited by the speed of networks.

 

Leave a Reply

Your email address will not be published. Required fields are marked *