Bitcoin Forum

The world’s best cryptographers meet this week to compete in a U.S.-sponsored challenge to create a quantum-resistant standard.

Want to steal some Bitcoin? All you need to do is find your victim’s 16-character public key and calculate their private key by solving something called an “elliptic curve discrete logarithm problem.” No sweat! With a regular computer, that’ll take you around 50 million times the amount of time the universe itself has left—around 0.65 billion billion years.

Ah, but with the right quantum computer, able to process information at speeds exponentially faster than today’s supercomputers? Suddenly, what seems uncrackable becomes child’s play, able to be broken in under 10 minutes.

The quantum-computing problem is nothing new to crypto, and many experts believe we have at least a decade or more to come up with quantum-resistant cryptography. However, some observers say that recent and unexpectedly fast advances are causing the time horizon to dramatically shrink. The most aggressive estimate says that bitcoin will be hackable by 2027, according to Fact Based Insights.

“We moved the state of the art more in the last two years than it has progressed in the last 15 or 20,” says Stewart Allen, Chief Operating Officer at IonQ, a company that claims to make some of the most powerful quantum computers in the world, in an interview with Decrypt.

On Thursday, top cryptographers will meet in Santa Barbara at the University of California for the National Institute of Standards and Technology (NIST) Post Quantum Cryptography semi finals. The finalists of the NIST competition will be announced in the months after the conference, though it might take years before the winner is annointed. Cryptographers say the standards that result represent blockchain’s best hope for resisting the rapidly encroaching power of quantum computers.

”If someone cracked your key, they could do anything they wanted,” Rob Campbell, President at Baltimore,Maryland-based Med Cybersecurity, told Decrypt. Anyone with sensitive information on the blockchain—cash, personal data, medical records—is at risk. With that sort of information, quantum hackers could “forge your name, take your assets,” and, if there’s medical data to be found, maliciously “triple your dose,” said Campbell. “It’s an open door.”

Take the Bitcoin blockchain: an unencrypted public key is sent along with every bitcoin transaction, and left unencrypted during the time it takes for the network to confirm the block, around ten minutes. That’s theoretically more than enough time for a quantum-equipped hacker to calculate a private key from the public key and replace the recipient’s address with his own.

Que Quantum?  

Transistors in conventional computers capture data in terms of 1s and 0s. Is the sky blue today? If it is, 1. If not, 0. Computing is essentially combinations of these calculations: have enough transistors, you can compute almost anything.

With quantum computers, it’s possible for the same input, called a qubit, to represent both 0 and 1 at the same time, a non-binary state known as “quantum superposition”—think Schrödinger's dead-and-alive cat. This makes quantum computers exponentially more powerful; one lone, superpositioned qubit can handle the processing load of at least two full-sized transistors on a regular computer.

Using modified versions of “Shor’s algorithm,” a quantum algorithm that rapidly turns large numbers into prime factors, hackers could reverse the process that makes private keys so difficult to crack.

But at the moment, the best quantum computer is probably Google's Bristlecone quantum computer, which has 72 qubits. Miruna Rosca, a PhD student in post-quantum cryptography, tells Decrypt you’d probably need around 4000 qubits to break current cryptographic algorithms.

So how long do we have?
IonQ’s Allan, who creates quantum computers for a living, speculates it’ll take about a decade for post-quantum cryptography to become an issue. By then, he reckons, someone will probably have developed a quantum-resistant blockchain. Danny Ryan, a core researcher at Ethereum, thinks the same: “This isn't really a meaningful problem in the next 10 years and likely not for 20 to 30. That said, we tend to be bad at estimating things like this so we should be ready to transition sooner rather than later.”

But others say the problem requires immediate attention, and that—beyond the threat to Bitcoin—quantum computing could pose a major cybersecurity threat. Med Cybersecurity’s Rob Campbell says that a government armed with quantum decryption software could read all the world’s secrets.

A U.S. Navy signal officer by training, Campbell’s time in the classified research and development world has taught him that secret government technologies often outpace commercially available technology. “We were decades ahead of the commercial world,” he said. “We didn’t want any potential adversaries to know what our capabilities are.”

Even if Campbell’s claims seem ambitious, he points out that if an enemy security agency scrape all of your encrypted data today—which they certainly could—they’ll be able to decrypt all that data once they’ve built a powerful enough quantum computer. That’s enough to make developing quantum-resistant cryptographic techniques an issue of national security.

In any case, the arms race for quantum supremacy is well underway: China just spent $10 billion on a research center for quantum computers, and the U.S. has pumped hundreds of millions of dollars into the field.

Quantum-resistant techniques
Quantum computing can be just as effective for cryptographers as it is for hackers. Unobserved, superpositioned particles exist in multiple states, but when detected, they “collapse” to one point in space-time. Quantum cryptography has the same properties; because the protons that make up an encoded transaction shift upon observation, a successful attacker would have to break the laws of physics to intercept it.

This makes information encoded at the quantum level resistant to, among other things, so-called “man in the middle attacks,” where attackers intercept the transmission itself without having to decrypt the key.

A few blockchains claim to apply quantum-resistant techniques to ensure signatures and hashes remain encrypted, including QRL, IOTA, HyperCash, and Starkware. But with quantum computing still in its formative years, it’s difficult to determine the strength of these claims.

Until a quantum-resistant algorithm is tested and accepted by the wider academic community, there’s no assurance that any of these blockchains will be resilient enough against quantum computers. Scientists like Campbell are waiting on the results of next week’s NIST competition at UCAL-Santa Barbara; the final winners might not be announced for a few years, however. NIST tentatively expects drafts for standardisation will be completed around 2022.

“These winners are considered to be the best candidates on Earth and will likely go on to be standard cryptography and will be used by most of the planet,” says Campbell.

But developing the algorithm might not be the difficult part for large blockchains like Ethereum or Bitcoin. Whereas owners of centralized protocols can update the system as they please, blockchains, democratic by nature, require broad consensus among many thousands of miners to pass an upgrade.

In the case of an upgrade, all wallets that aren’t quantum-resistant become vulnerable to attack. That includes the 1 million bitcoins mined by Bitcoin’s pseudonymous inventor, Satoshi Nakamoto—if those aren’t migrated to a new, quantum-resistant wallet, they’re treasure for the first person with a powerful enough quantum computer.

“If high powered quantum computers appeared tomorrow,” said Ethereum’s Ryan, “we'd have many more problems than just the security of our blockchains.”

A 2019 National Academy of Sciences report concludes that, even if quantum computing is about a decade off, prioritising research is necessary to minimize “the chance of a potential security and privacy disaster.” Best get cracking, then.

https://decrypt.co/8498/bitcoins-race-to-outrun-the-quantum-computer

Scientists like Campbell are waiting on the results of next week’s NIST competition at UCAL-Santa Barbara; the final winners might not be announced for a few years, however. NIST tentatively expects drafts for standardisation will be completed around 2022.

“These winners are considered to be the best candidates on Earth and will likely go on to be standard cryptography and will be used by most of the planet,” says Campbell.

Maybe this competition is intended to create encryption standards utilized by the entire world that have backdoors or vulnerabilities specifically engineered into them?

It could be a decent security practice to avoid whatever encryption standards are produced as a result of this?

In any case there's no real reason to worry about any of this, quantum computing as it is today it's just a meme. I would stick to SHA256 and plan for a NIST alternative in the future if necessary.. and non-US stuff doesn't necessarily mean safer anyway. It just has to be peer reviewed by as many independent and widespread people as possible.

victim’s 16-character public key

Maybe this competition is intended to create encryption standards utilized by the entire world that have backdoors or vulnerabilities specifically engineered into them?

If you are paranoid about the outcome of this US sponsored competition to come up with encryption standards, then you should be paranoid about Bitcoin's SHA256, Tor or anything else that came out of US related activity.

In any case there's no real reason to worry about any of this, quantum computing as it is today it's just a meme. I would stick to SHA256 and plan for a NIST alternative in the future if necessary.. and non-US stuff doesn't necessarily mean safer anyway. It just has to be peer reviewed by as many independent and widespread people as possible.

Satoshi most likely did the right thing at not using something more exotic, it could have backfired, SHA256 was the most widespread with hardware support and timetested, peer-reviewed by cryptographers.

Will the change from SHA256 to SHA512 necessitate a whole Bitcoin fork or can this just be done with a normal node update? I am not a developer, so I might be asking a stupid question... sorry.  ::)

Well, I think the solution is already out there in the form of SHA512.  ::)  Most processors today can handle SHA512 much easier today, so it is not unlikely that they would switch to SHA512 in the future.  ???  They are obviously not just doing this to protect Crypto currencies, because most secure sites and even some Banking services use SHA256 today.  :D

Will the change from SHA256 to SHA512 necessitate a whole Bitcoin fork or can this just be done with a normal node update? I am not a developer, so I might be asking a stupid question... sorry.  ::)

not only switching to SHA512 is unlikely, i would say it is stupid.
for starters it would make everything twice as big and that is while we are trying so hard to compress everything and make them smaller to keep it manageable (for storage and scaling).
on top of that you can't just stop there, you have to change the curve too. with a 256 bit curve it is not useful to use a 512 bit hash function. you have to also switch to a 512+ bit curve like secp521r1. i am also sure that switch to SHA512 would break 90% of bitcoin implementations because they either don't have the functionality to calculate "e" during ECDSA since they never needed it or they have a false one in place.

~
I  agree that it is stupid right now because you would be doubling the storage requirements when they are not even needed yet. In the future SHA512 will be an option however I think that there's already more promising solutions than SHA152 but concerning the storage issues that you mention because of the way technology is evolving at an exponential rate we can estimate that storage issues will not be an issue even for people with low budget within the next 5-10 years.

Don't worry about Bitcoin, a small niche. The world will have BIGGER problems to worry about with the arrival of quantum computers. Hahaha.

The original chain will remain the strongest chain. If some groups can reproduce the privatekeys of 'shalecoins', coins with no owner https://bitcointalk.org/index.php?topic=5134441.0, it's their reward. They are trying to build a computer in the near future, that wouldn't be built so fast without that incentive. That opportunity accelerates the technology. If there are still some BTC owners -incl. Satoshi- with old addresses and remove their coins now, they will be secure. So it's a fair game. And nobody can change that game: Bitcoin rewards the best technology.

The Bitcoin network is a pure competition network. Only the best technology will be successful here and make it secure. A Bitcoin fork without the old coins would be like another s**tcoin, because it would avoid real competition.

Computing, security, encryption, and hacking has always been and will likely always be a cat and mouse game.  It's not like we all woke up one day and found all of our security that was based on SHA-1 encryption was hosed by every hacker on the planet, it was a gradual shift.  As computers get faster, encryption will need to become stronger, and it's the faster computers that will enable stronger encryption.

The world will be able to fix the quantum issue and implement a quantum secure mode through rewinding, freezing, correcting accounts. But Bitcoin can't and that will lead to forks.

Title: Spreading light over quantum computers
-snip- They have constructed a simulation tool, Quantum Simulation Logic, QSL, that enables them to simulate the operation of a quantum computer in a classical computer.
-snip-

I'm confident that the community will come into consensus to hard fork, if the threat of quantum computers will be the "death of Bitcoin". It will not be close to a debate.

1. what happens to quantum-vulnerable outputs? like p2pk and spent addresses that still hold coins. the answer dictates whether lost coins are actually a donation to bitcoin holders as satoshi said. if we do nothing, then he was obviously wrong about that.

2. the logistics of a fork. take lamport signatures for example. wouldn't it be optimal to do it years before it's a real concern = less people reusing keys as the threat approaches?

i wouldn't be so sure about that!
we are talking about a major change with a hard fork and it is not like there is only one solution that everyone could jump on board. there is a ton of different things that will cause a ton of drama. for starters which algorithm to choose? and worst of all what to do with coins that won't move such as outputs that were made in early years such as 2009 (naively referred to as Satoshi's coins). should we burn them? you see there is a lot of room for debates.

~
But it's "fork or die". This isn't a mere "scaling debate", in which Jihan Wu, his cartel of miners, and Silbert's cartel of merchants can play their games. They their play games, then all of us lose.

i wouldn't be so sure about that!
we are talking about a major change with a hard fork and it is not like there is only one solution that everyone could jump on board. there is a ton of different things that will cause a ton of drama. for starters which algorithm to choose? and worst of all what to do with coins that won't move such as outputs that were made in early years such as 2009 (naively referred to as Satoshi's coins). should we burn them? you see there is a lot of room for debates.

What do mean satoshi coins ( Are BTC Test Coins) ?

PUSHDATA(65)[04fcc2888ca91cf0103d8c5797c256bf976e81f280205d002d85b9b622ed1a6f820866c7b5fe12285cfa78c035355d752fc94a398b67597dc4fbb5b386816425dd] CHECKSIG

How can you even know if somehting is quantum resistant? Seems a computer that powerful will be able to crack anything you put in front of it.

Quantum Computer isn't miracle or magic which can solve any computational problem that exist. Try reading https://www.cs.virginia.edu/~robins/The_Limits_of_Quantum_Computers.pdf (https://www.cs.virginia.edu/~robins/The_Limits_of_Quantum_Computers.pdf).

One often repeated argument in favor is quantum resistance. I believe this is besides the point. We have no idea what the characteristics of a hypothetical machine relying on yet to be invented technology will be. Given the degree of key reuse on the network (so there are addresses with known public keys), the existence of a system that can break ECDSA is likely a death blow to Bitcoin. A real solution to that is to prepare and have real quantum-resistant cryptography in place before it's too late. Relying on a weird hope that those hypothetical machines are somehow too slow to steal from unconfirmed transactions before they're mined is a red herring.

the spirit of what he's saying is important though. for example, there is an assumption often repeated that unspent P2PKH outputs are quantum resistant because they don't expose the public key. but as pieter wuille points out, (https://bitcoin.stackexchange.com/questions/72184/why-is-p2pkh-used-instead-of-the-simpler-p2pk) this is based on little more than the hope that a hypothetical quantum computer is too slow to steal from unconfirmed transactions.

If you are paranoid about the outcome of this US sponsored competition to come up with encryption standards, then you should be paranoid about Bitcoin's SHA256, Tor or anything else that came out of US related activity.

NSA Backdoors and Bitcoin

Many cryptographic standards widely used in commercial applications were developed by the U.S. Government’s National Institute of Standards and Technology (NIST). Normally government involvement in developing ciphers for public use would throw up red flags, however all of the algorithms are part of the public domain and have been analyzed and vetted by professional cryptographers who know what they’re doing. Unless the government has access to some highly advanced math not known to academia, these ciphers should be secure.

We now know, however, that this isn’t the case. Back in 2007, Bruce Schneier reported on a backdoor found in NIST’s Dual_EC_DRBG random number generator:

But today there’s an even bigger stink brewing around Dual_EC_DRBG. In an informal presentation(.pdf) at the CRYPTO 2007 conference in August, Dan Shumow and Niels Ferguson showed that the algorithm contains a weakness that can only be described as a backdoor.

This is how it works: There are a bunch of constants — fixed numbers — in the standard used to define the algorithm’s elliptic curve. These constants are listed in Appendix A of the NIST publication, but nowhere is it explained where they came from.

What Shumow and Ferguson showed is that these numbers have a relationship with a second, secret set of numbers that can act as a kind of skeleton key. If you know the secret numbers, you can predict the output of the random-number generator after collecting just 32 bytes of its output. To put that in real terms, you only need to monitor one TLS internet encryption connection in order to crack the security of that protocol. If you know the secret numbers, you can completely break any instantiation of Dual_EC_DRBG.


This is important because random number generators are widely used in cryptographic protocols. If the random number generator is compromised, so are the ciphers that use it.

Thanks to the heroic work of Edward Snowden we now know that Dual_EC_DRBG was developed by the NSA, with the backdoor, and given to NIST to disseminate. The scary part is that RSA Security, a company that develops widely used commercial encryption applications, continued use of Dual_EC_DRBG all the way up to the Snowden revelations despite the known flaws. Not surprising this brought a lot of heat on RSA which denies they intentionally created a honeypot for the NSA.

UPDATE: RSA was paid $10 million by the NSA to keep the backdoor in there.

All of this has been known for several months. What I didn’t know until reading Vitalik Buterin’s recent article Satoshi’s Genius: Unexpected Ways in which Bitcoin Dodged Some Crytographic Bullets, is that a variant of an algorithm used in Bitcoin likely also contains a NSA backdoor, but miraculously Bitcoin dodged the bullet.

Bitcoin uses the Elliptic Curve Digital Signature Algorithm (ECDSA) for signing transactions. This is how you use your private key to “prove” you own the bitcoins associated with your address. ECDSA keys are derived from elliptic curves that themselves are generated using certain parameters. NIST has been actively recommending that everyone use the secp256r1 parameters because they “are the most secure”. However, there appears to be some funny business with secp256r1 that is eerily similar to the backdoor in Dual_EC_DRBG.

Secp256r1 is supposed to use a random number in generating the curves. The way it allegedly creates this random number is by using a one-way hash function of a “seed” to produce a nothing up my sleeve number. The seed need not be random since the output of the hash function is not predictable. Instead of using a relatively innocuous seed like, say, the number 15, secp256r1 uses the very suspicious looking seed: c49d360886e704936a6678e1139d26b7819f7e90. And like Dual_EC_DRBG, it provides no documentation for how or why this number was chosen.

Now as Vitalik pointed out, even if the NSA knew of a specific elliptic curve with vulnerabilities, it still should have been near impossible for them rig the system due to the fact that brute-forcing a hash function is not feasible. However, if they discovered a flaw that occurred in say, one curve in every billion, then they only need to test one billion numbers to find the exploit.

However, the kicker in all this is that the parameters for secp256r1 were developed by the head of elliptic curve research at the NSA!

The unbelievable thing is that rather than using secp256r1 like nearly all other applications, Bitcoin uses secp256k1 which uses Koblitz curves instead of pseudorandom curves and is still believed to be secure. Now the decision to use secp256k1 instead of secp256r1 was made by Satoshi. It’s a mystery why he chose these parameters instead of the parameters used by everyone else (the core devs even considered changing it!). Dan Brown, Chairman of the Standards for Efficient Cryptography Group, had this to say about it:

I did not know that BitCoin is using secp256k1. Indeed, I am surprised to see anybody use secp256k1 instead of secp256r1.

Just wow! This was either random luck or pure genius on the part of Satoshi. Either way, Bitcoin dodged a huge bullet and now almost seems destined to go on to great things.

https://chrispacia.wordpress.com/2013/10/30/nsa-backdoors-and-bitcoin/

Blockchain latest news: a state-owned quantum computer could break blockchains in as little as three years  https://www.computing.co.uk/ctg/news/3033006/state-owned-quantum-computer-break-blockchains-three-years (https://www.computing.co.uk/ctg/news/3033006/state-owned-quantum-computer-break-blockchains-three-years) 'A commercially viable quantum computer is still probably a decade away but the first rudimentary, state-owned device capable of breaking common one-way encryption algorithms like AES and elliptic curve cryptography could be with us much sooner.'
'Whoever achieves it first - and it could be within as little as three years according to Cheng - don't expect to learn about it in the news.'

I have no idea and I just learned it from this thread. Those coins in Satoshi's wallet will then be activated which sooner there might not have forgotten coins after all. I guess we can all say Bitcoin will live on to be 21M in total. Nothings wasted and SAtoshi has really thought all of these will happen one day.

Quantum computing wont be a problem for Bitcoin anytime soon. Advancements will make quantum obsolete as well.

-----------------
Bitcoins steal without the help of a quantum computer. Anonymity of bitcoin owners is eliminated without quantum helpers.

In new public key cryptographic systems that claim to be post quantum, they find vulnerabilities without the help of a quantum computer and without guessing the key.

The fear of the quantum computer is similar to the fear of the monkey, the new big monkey.

Our main danger is people using their intelligence to cheat, not a stick and brute force.

So I agree that our security won't suffer much from quantum computing.

Computing, security, encryption, and hacking has always been and will likely always be a cat and mouse game.  It's not like we all woke up one day and found all of our security that was based on SHA-1 encryption was hosed by every hacker on the planet, it was a gradual shift.  As computers get faster, encryption will need to become stronger, and it's the faster computers that will enable stronger encryption.

Quantum computers are not as far from life as we think. Look at Amazon's new services. Offer for commercial use. And why is everyone obsessed with these qubit calculators? Cryptography on elliptic curves has compromised itself for a long time, they just don’t write about it.

One thing I don’t understand in the whole discussion; if RSA or ECC are compromised in the future, we can upgrade existing systems of course (and we’ll have to ... whole PKI will come tumbling down), but won’t this make dormant wallets vulnerable? How are we going to prevent someone stealing the funds from there?

What new services offer quantum computers? I'm not sure what you're referring too, but Amazon does not offer anything even near the capabilities of a quantum computer. If the elliptic curves were compromised critically it would be a issue that would likely be put on top of the priority list. Elliptic curves to my knowledge, and many others has not been compromised.

You make some good posts regarding Bitcoin, but a lot of it is scaremongering similar to the scaremongering tactics used by news outlets. Maybe not intentionally, but suggesting that elliptic curves have been compromised, and then later stating they have weaknesses is inaccurate. They have not been compromised, but they do have strengths, and weaknesses just like any other cryptography.

One thing I don’t understand in the whole discussion; if RSA or ECC are compromised in the future, we can upgrade existing systems of course (and we’ll have to ... whole PKI will come tumbling down), but won’t this make dormant wallets vulnerable? How are we going to prevent someone stealing the funds from there? Otherwise that will cause a huge drop in the value of Bitcoin. We can’t put a wrapper or something around those wallets, right?

I am a tech guy, not an economist, so not sure if my reasoning makes sense!

What new services offer quantum computers? I'm not sure what you're referring too, but Amazon does not offer anything even near the capabilities of a quantum computer. If the elliptic curves were compromised critically it would be a issue that would likely be put on top of the priority list. Elliptic curves to my knowledge, and many others has not been compromised.

You make some good posts regarding Bitcoin, but a lot of it is scaremongering similar to the scaremongering tactics used by news outlets. Maybe not intentionally, but suggesting that elliptic curves have been compromised, and then later stating they have weaknesses is inaccurate. They have not been compromised, but they do have strengths, and weaknesses just like any other cryptography.

Quantum cryptography is what?
The transmission of information through the use of quantum states of a particle of light, a photon - it's understandable.
This is a photon Internet, which is proudly called "quantum Internet", although it has nothing to do with "quantum" itself, as elementary particles.
And there is no quantum cryptography, no interaction with quanta, encryption with quanta.

And what's quantum cryptography? I can't figure it out.
There's only post quantum cryptography, math.

What's quantum cryptography?

Hello again! We've discussed this on another thread, so I won't go into it in depth again, but I'll mention China's Micius satellite as an example of quantum cryptography in action. Micius is already enabling a (small) quantum internet. A pair of entangled photons is generated using an interferometer, and one photon is sent to each party in the communication. The quantum entanglement is the vital part of the encryption, the use of the laws of quantum mechanics to create the exchange of information: Quantum Key Distribution.

I will concede that whilst QKD removes some classical vulnerabilities, it does not remove them all: man-in-the-middle as an example.
But Micius is only the start. Other variants of quantum cryptography are also being advanced. Kak's 3 stage protocol (https://en.wikipedia.org/wiki/Three-stage_quantum_cryptography_protocol) for example (a quantum version of double-lock), a multi-photon variant (https://arxiv.org/abs/1503.05793) of which is being developed to protect precisely against man-in-the-middle.

I am certainly not saying that post-quantum cryptography (classical cryptography used as a defence against quantum attack) is useless, it's not, it's extremely important.
But quantum cryptography (using the laws of quantum mechanics to implement cryptography) is important too.

Here's a time-lapse photo of Micius in action. https://cosmosmagazine.com/technology/the-quantum-internet-is-already-being-built
https://cosmos-images2.imgix.net/file/spina/photo/14627/230318_Quantum_Internet_01.jpg?ixlib=rails-2.1.4&auto=format&ch=Width%2CDPR&fit=max&w=1400

What you call "quantum cryptography", and that's what everyone calls it, is only needed to agree on common encryption keys for common symmetric cryptography, such as AES-256.

It's a wordplay - it's not cryptography, it's a way to generate the same keys for 2 people.

But all asymmetric modern systems are unreliable [...] All modern asymmetric systems will collapse at any key length.

You're wrong about the "quantum internet" being afraid of the "man in the middle" attack. This attack is only dangerous when it can be conducted invisibly.
You can't do it inconspicuously on the quantum internet.
This is a huge advantage of this method.

They use AES-256 because it cannot be cracked by any quantum computer.

I agree with all your comments.

Except for one, one.

There is reliable, absolutely reliable cryptography, in the absolute sense. It's Vernam's cipher.
It's the only cipher for which there's evidence of its 100% reliability [...]
The first cryptosystem I did not give a link to, here it is, I really like it:
https://www.nature.com/articles/s41467-019-13740-y

No modern cryptographic system has any proof of its crypto stability, and that proof cannot be, because the principles of encoding them - so to speak, are more cunning than reliable.

Excellent! Finally our discussion across multiple threads reaches a consensus :)

Damn it.



Aha, yes, one-time pad stuff... which brings us back to quantum cryptography and QKD.

https://media.springernature.com/lw685/springer-static/image/art%3A10.1038%2Fs41467-019-13740-y/MediaObjects/41467_2019_13740_Fig1_HTML.png

It's an inventive approach, but I'm not convinced of how this is better than the quantum alternative, BB84 QKD (https://en.wikipedia.org/wiki/BB84). I don't think OTPs are the answer here. An OTP by itself and used properly is secure, but the key needs to be shared in a 100% safe way. And if you have a means to share the key 100% safely, then you just use that method and there is no need for the OTP. Quantum entanglement is the 100% safe method (sorry, I wanted to focus on PQC and not return to quantum cryptography again!).
But we still have vulnerabilities so long as we have external classical dependencies.


Yes, agreed. AES256 looks secure against a Grover attack, so is likely safe in the medium-term, but longer term, who knows? Longer term the solution I still contend is likely to use some quantum mechanical mechanism such as entanglement to create fundamental 100% security, the big caveat here being that our understanding of quantum mechanics may change, and new possibilities and challenges in physics may present themselves...

"I think I can safely say that nobody understands quantum mechanics." Richard Feynman knew what he was talking about. The maths is one thing, but it's an abstraction, it only helps us so far in understanding QM from a human perspective.

I thought you were in a hurry to jump to conclusions.

This method excludes all the disadvantages of quantum cryptography, which in practice will have a function of key distribution for symmetric encryption systems.

Quantum cryptography is very slow, very capricious, very resource-intensive.

VOLKSWAGEN CARRIED OUT THE WORLD'S FIRST PILOT PROJECT FOR TRAFFIC OPTIMIZATION WITH A QUANTUM COMPUTER
https://www.quantaneo.com/Volkswagen-carried-out-the-world-s-first-pilot-project-for-traffic-optimization-with-a-quantum-computer_a366.html

Ford and Microsoft pilot quantum-inspired routing to reduce congestion
https://www.intelligenttransport.com/transport-news/93711/ford-microsoft-pilot-quantum-inspired-routing-reduce-congestion/

Microsoft and Ford try using quantum-style computing to solve Seattle’s traffic problem
https://www.geekwire.com/2019/microsoft-ford-try-using-quantum-style-computing-solve-seattles-traffic-problems/


In the future: no optimized transportation without quantum computers
Re: Is Elon Musk developing a quantum computer?

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.'''

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 Shor’s algorithm to break public-key cryptography. This is a quantum algorithm designed specifically to solve for prime factors. As with Grover’s 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 Shor’s approach to derive the private key. The vulnerability cannot be overstated here. Any re-used address is utterly insecure.

My opinion:

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 (https://bitcointalk.org/index.php?topic=5157696.msg52025169#msg52025169), is the use of Shor's algorithm against re-used addresses:


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

Edit: To be absolutely clear: I am not proposing (and would never propose) a policy that would have the goal of depriving anyone of his bitcoins. Satoshi's bitcoins (which number far below 1M, I think) rightfully belong to him, and he can do whatever he wants with them. Even if I wanted to destroy Satoshi's bitcoins in particular, it's not possible to identify which bitcoins are Satoshi's. I am talking about destroying presumably-lost coins that are going to be stolen, ideally just moments before the theft would occur.

This issue has been discussed for several years. I think that the very-rough consensus is that old coins should be destroyed before they are stolen to prevent disastrous monetary inflation. People joined Bitcoin with the understanding that coins would be permanently lost at some low rate, leading to long-term monetary deflation. Allowing lost coins to be recovered violates this assumption, and is a systemic security issue.

So if we somehow learn that people will be able to start breaking ECDSA-protected addresses in 5 years (for example), two softforks should be rolled out now:

One softfork, which would activate ASAP, would assign an OP_NOP to OP_LAMPORT (or whatever QC-resistant crypto will be used). Everyone would be urged to send all of their bitcoins to new OP_LAMPORT-protected addresses.

One softfork set to trigger in 5 years would convert OP_CHECKSIG to OP_RETURN, destroying all coins protected by OP_CHECKSIG. People would have until then to move their BTC to secure addresses. Anyone who fails to do so would almost certainly have lost their money due to the ECDSA failure anyway -- the number of people who lose additional BTC would be very low. (There might be a whitelist of UTXOs protected by one-time-use addresses, which would remain secure for a long time.)

I've been looking for later news on the web, but not found much. Presumably (hopefully) the discussion has moved on considerably since 2016. If anyone is familiar with the latest discussions on this topic, please respond in this thread!