Quantum chip solves travelling salesman problem for 22 cities
https://www.electronicsweekly.com/news/research-news/quantum-chip-solves-travelling-salesman-problem-22-cities-2020-01/'''According to the university, this is something that would take about 1,200 years for a high-performance von Neumann CPU, but the chip can solve the travelling salesman problem for 22 cities instantly until now using quantum processing it has only been able to solve the travelling salesman problem involving a maximum of 16 cities.
A quantum annealing computer is not a full-blown quantum computer, of the type that could crack encryption for example, which no one has yet made or if they have, they are keeping quiet about it.'''
It's an interesting development, but yes, a quantum annealing computer can't be used to break cryptography, and will never threaten bitcoin. The annealing approach is more for problems where there are a huge number of possible solutions, and we're just looking for one that is sufficient out of that multitude of possibilities.
The biggest threat to bitcoin from quantum computing, as I've
outlined previously, is the use of Shor's algorithm against re-used addresses:
Re-used BTC addresses are 100% vulnerable to QCs.
Address Re-Use. Simply, any address that is re-used is 100% vulnerable because a QC can use Shors algorithm to break public-key cryptography. This is a quantum algorithm designed specifically to solve for prime factors. As with Grovers algorithm, the key is in dramatically reducing the number of computational steps required to solve the problem. The upshot is that for any known public key, a QC can use Shors approach to derive the private key. The vulnerability cannot be overstated here. Any re-used address is utterly insecure.
... but a quantum annealing computer (the type that is used above for the Travelling Salesman problem), is not going to run Shor. For that you need a universal gate QC, which is generally what we mean when we refer to a 'quantum computer'. I remember all the fuss about D-Wave, but the mainstream media tended to overlook the fact that D-Wave is an annealer, not a fully-fledged UG-QC.
My opinion:
Quantum computers will surprise the Bitcoin community..
My opinion is actually the exact opposite. I think that crypto developers, certainly for the big coins, and most definitely for bitcoin, are well aware of potential threats from quantum computers, and are actively developing safeguards.
We've covered previously and in considerable depth what QCs can and can't do. Asymmetric cryptography is massively vulnerable, but symmetric cryptography far less so -particularly AES256, as discussed above. It's a common misconception, perpetuated by mainstream media, that QCs instantly break all types of cryptography in all circumstances, when that is clearly not the case. QCs are great for certain specific types of problem, but it's technology, not magic, and it has limitations.
I am some random uninformed idiot posting opinions on a web forum, and even I am aware of what QCs can and can't do, and of the nature of their potential threat to cryptocurrencies in certain situations. People far smarter than me are developing these coins, and I'm absolutely certain that they are on top of the QC question. This is why I am convinced that the threat of QCs will not come as a surprise.
----------------------------
What exactly are the dangers of quantum computing today, which is not there now, but can be tomorrow?
It's very simple and consistent.
My answer is this.
I'll talk about global danger, the danger to most cases, not to one person.
All protection protocols, we will talk only about cryptographic methods of protection, built on a principle:
1. Asymmetric cryptography is the first step in any protocol to agree on a common session key for symmetric cryptography.
2. The second step is symmetric cryptography encryption, where secrets are encrypted securely (AES).
Why is a quantum computer dangerous today that will work far tomorrow?
Because all of our encrypted messages are stored.
Details:
- those encryptions that are very interesting - stored many times, it's communication between interesting and big people of our time;
- all other messages are also stored, just in case, they can be interesting, probably.
Now how quantum cheaters will work:
1) they will only crack the first stage of the encryption protocol - only asymmetric cryptography, where the shared session encryption key was encrypted. That's it.
2) They use the resulting key to quietly read the AES cipher, the second step of the encryption protocol.
And now, everything falls into place: AES-256, the symmetric system, is not cracked, and RSA (with any length of key) or ECC (with any length of key), the asymmetric system is cracked without a doubt, even by very weak, first quantum computers.
That's why everyone is so concerned, that's why post quantum asymmetric encryption systems are already needed.
Yes, not all people encrypt good messages, there are so many that lead two lives at once and one of those lives is very bad.
But the bad thing is to read and decide what's bad and what's good will be guys with the same questionable reputation as the first ones.
Here is the real vulnerability of all the key encryption methods: everything secret, sooner or later, becomes known and not secret.
This vulnerability is completely devoid of new keyless encryption systems.