[amluto]

One thing I find rather amazing about all of this is the degree to which the Bitcoin community has tried, for years, to claim that quantum computers will be another other than a complete break.

Sure, it takes a pretty nice quantum computer or a pretty good algorithm or a degree of malice on the part of miners to break pay-to-script-hash if your wallet has the right properties, but that seems like a pretty weak excuse for the fact that the entire scheme is broken, completely, by QC.

Does there even exist a credible post-quantum proof protocol that could be used to “rescue” P2SH wallets?

[Strilanc]

The best proposal I have heard for rescuing P2SH wallets after cryptographically relevant quantum computers exist is to require vulnerable wallets to precommit to transactions a day ahead of time. The precommitment doesn't reveal the public key. When the public key must be exposed as part of the actual transaction, an attacker cannot redirect the transaction for at least one day because they don't have a valid precommitment to point to yet.

[amluto]

That’s kind of adorable. Would you need to pay to record a commitment? If so, how? If not, what stops someone from DoSing the whole scheme?

[dumbfoundded]

I don't think you're understanding how cryptography works. A commitment is basically a hash that is both binding and hiding. In this example it's probably easiest to think of it as a hash. So you hash your post-quantum public key (something like falcon-512) and then sign that hash with your actual bitcoin private key (ecdsa, discrete-log, not quantum safe) and then publish that message to the bitcoin network. Then quantum happens at some point and bitcoin needs to migrate but where do funds go? Well you reveal the post-quantum public key and then you can prove that funds from the ecdsa key should go there. From a technical perspective, this is a complete and fool proof system. DoSing isn't really a concern if you publish to the actual bitcoin network and it's impossible for someone to use up the key space (2^108 combinations at least).

The reason this is a dumb idea is because coordination and timing. When does the cutover happen? Who decides which transactions no longer count as they were "broken" b/c of quantum computing? The idea is broken but not from technical fundamentals.

[Strilanc]

The DoS attack in this scenario is someone just submitting reasonable-looking but ultimately bad precommitments as fast as possible. The intuition is that precommitments must be hard to validate because, if there was an easy validation mechanism, you would have just used that mechanism as the transaction mechanism. And so all these junk random precommitments look potentially legitimate and end up being stored for later verification. So all you have to do to take down the system is fill up the available storage with junk, which (given the size of bot networks and the cost of storing something for a day) seems very doable.

[dumbfoundded]

If the question is storage, bitcoin itself provides a perfectly good mechanism. idk the exact costs but it'd be in the range of ~$0.45 to store a commitment. That's cheap enough to enable good users with small numbers of keys but also expensive enough to prevent spam. It's kind of the whole point of blockchains.

As for verification being expensive, it sounds like you don't know the actual costs. It's basically a hash. Finding the pre-image of a hash is very expensive to the point of being impossible. Verifying a pre-image + hash function = a hash is extremely cheap. That's the whole point of 1-way functions. Bitcoin itself is at ~1000 EH/s (exahashes per second)

Again, this isn't a technical problem. It's a coordination problem.

[amluto]

Commitment validation would indeed be trivial.

This whole scheme fails if an attacker can manage to delay a transaction for a day, and if the commitment also commits to a particular transaction fee, then the user trying to rescue their funds can’t easily offer a larger transaction fee if their transaction is delayed. But if the commitment does not commit to a transaction fee, then an attacker could force the transaction fee to increase arbitrarily.

Maybe the right strategy would be commit, separately, to multiple different choices of transaction fee.

[Strilanc]

Yes, that would be a concern. You could require a proof of work to submit a precommitment, so that DoSing was at least expensive to do. You could have some sort of deposit mechanism, where a precommitment would lock down 0.1 bitcoins (from a quantum-secure wallet) until the precommitment was used. I admit I'm glad I don't have to figure out those details.

[warkdarrior]

24-hour latency to make a payment? What is this, the 20th century?

[Strilanc]

This is for rescue, not for payment. Once you've moved the coins to quantum-secure wallet, the delay would no longer be needed.

...probably some people would be very inconvenienced by this. But not as inconvenienced as having the coins stolen or declared forever inaccessible.

[daveguy]

> ...probably some people would be very inconvenienced by this. But not as inconvenienced as having the coins stolen or declared forever inaccessible.

I don't know why anyone f's around with crypto anymore. So many caveats, such a scammy ecosystem. It just doesn't seem worth the trouble to support a ransomware and money laundering tool.

[int32_64]

> the Bitcoin community has tried, for years, to claim that quantum computers will be another other than a complete break.

Who specifically is claiming this? Satoshi literally mentioned the need to upgrade if QC is viable on bitcointalk in 2010.

[ViscountPenguin]

Call me crazy, but I think if bitcoin is ever broken they're more likely to move to a centralized ledger than a more secure decentralized ledger. Roughly nobody invested in bitcoin cares about the original mission, they just care about their asset prices.

[eru]

And the asset prices (at least partially) depend on true believers in the mission.

[bawolff]

On the brightside at least we'll have a clear indicator for when quantum computers actually arrive.

[Mistletoe]

If Bitcoin is broken then your bank encryption and everything else is broken also.

As far as I know quantum computers still can't even honestly factor 7x3=21, so you are good. And the 5x3=15 is iffy about how honest that was either.

https://news.ycombinator.com/item?id=45082587

Bitcoin uses 256-bit encryption, it's a universe away from 5x3=15.

[Strilanc]

You are assuming that progress on factoring will be smooth, but this is unlikely to be true. The scaling challenges of quantum computers are very front-loaded. I know this sounds crazy, but there is a sense in which the step from 15 to 21 is larger than the step from 21 to 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139 (the RSA100 challenge number).

Consider the neutral atom proposal from TFA. They say they need tens of thousands of qubits to attack 256 bit keys. Existing machines have demonstrated six thousand atom qubits [1]. Since the size is ~halfway there, why haven't the existing machines broken 128 bit keys yet? Basically: because they need to improve gate fidelity and do system integration to combine together various pieces that have so far only been demonstrated separately and solve some other problems. These dense block codes have minimum sizes and minimum qubit qualities you must satisfy in order for the code to function. In that kind of situation, gradual improvement can take you surprisingly suddenly from "the dense code isn't working yet so I can't factor 21" to "the dense code is working great now, so I can factor RSA100". Probably things won't play out quite like that... but if your job is to be prepared for quantum attacks then you really need to worry about those kinds of scenarios.

[1]: https://www.nature.com/articles/s41586-025-09641-4

[honzaik]

1) yes, everything is affected, but everything else is being migrated to PQC as we speak

2) "256-bit encryption" has different meanings in different contexts. "256-bit security" generally refers to cryptosystem for which an attack takes roughly 2^256 operations. this is true for AES-256 (symmetric encryption) assuming classical adversaries. this is not true for elliptic curve-based algorithms even though the standard curves are "256-bit curves", but that refers to the size of the group and consequently to the size of the private key. the best general attacks use Pollard's rho algorithm which takes roughly 2^128 operations, i.e., 256-bit curves have 128-bit security.

in the context of quantum attackers, AES-256 is still fine although theoretically QCs halve the security; however its not that big of a deal in practice and ultimately AES-128 is still fine, because doing 2^64 "quantum operations" is presumed to be difficult to do in practice due to parallelization issues etc.

the elliptic curve signatures (used in Bitcoin) are attacked using Shor's algorithm where the big deal is that it is asymptotically polynomial (about O(n^3)) meaning that factoring a 256-bit number is only 256^3/4^3 = 262144x more difficult compared to factoring 15. this is a big difference from "standard" exponential complexity where the difficulty increases exponentially by factors of 2^n. (+ lets ignore that elliptic curve signatures dont rely on factoring but the problem is essentially the same because Shor does both because those are hidden subgroup problems)

the analysis is more complex but most of it is essentially in that paper and explains it nicely.

[ozim]

Your bank doesn’t depend only on cryptography. It would be still a lot of effort to simply make transfer from a bank account. Quantum computer will not magically give an answer for a password of a hash you don’t have. TLS is moving to post quantum as we speak.

For crypto currency you have all the data you need to break whole system ready in your hands as you will be able to produce private key from public keys of wallets. Cryptocurrency depends only on cryptography.

[timbowhite]

In Bitcoin's case, public keys are only revealed during a transaction.

And every transaction completely spends the source keypairs' funds.

So the only attack vector a quantum computer could use is:

1. Observing newly broadcast/unconfirmed transactions

2. Deriving the private key(s) from the public key(s)

3. Creating and broadcasting its own transaction using the stolen keypairs before the original transaction confirms (presumably with a higher fee to win the confirmation race).

Please correct me if I'm wrong.

EDIT: correction: every transaction completely spends any selected UTXO of an associated keypair, not all of the "source keypairs' funds". Thus the attack vector also includes being able to steal from any keypair that has ever made a transaction and also has UTXOs.

[Strilanc]

The newest transaction mechanism (taproot; P2TR) exposes the public key of the receiver as part of the transaction. If it becomes more commonly used, the supply of bitcoins with exposed public keys would start going up again. See figure 5 of https://arxiv.org/pdf/2603.28846#page=14 .

[lifty]

So everything basically.

[MattPalmer1086]

All serious financial businesses already have a quantum strategy and are actively working on transitioning their cryptography to post-quantum secure algorithms.

Bitcoin doesn't use 256 bit encryption, unless you mean 256-bit hashing. The cryptographic algorithms that are mostly under quantum threat are asymmetric, e.g. digital signatures.

[amluto]

> All serious financial businesses already have a quantum strategy and are actively working on transitioning their cryptography to post-quantum secure algorithms.

That’s hilarious and it’s not even April 1 anymore.

Lots of serious financial businesses still use FTP or use SFTP running some unbelievably bad server implementation on a Windows machine somewhere that uses such outdated cryptography that it doesn’t even interoperate with modern OpenSSH. Operations do not necessarily score highly on the ACID scale. It’s tied together with duct tape and baling wire.

On the other hand, the system works and is really remarkably resilient to various failure modes. You would be hard pressed to cause more than severe annoyance by compromising these crappy old systems.

[MattPalmer1086]

I work in the sector, and I'm responsible in my own organisation for our quantum strategy. Most, if not all, of the serious players are doing this. This doesn't mean we have replaced all our old crypto; far from it.

NIST has defined a timeline for post quantum readiness to be complete by 2035. Crypto migrations historically take a long time; you can't just replace your own stuff, or upgrade just a server. All the clients that interact have to upgrade as well or it all breaks.

[amluto]

If your bank’s encryption is broken in the future, then, to recover, you will need to change your password, and that’s all. Bitcoin does not have that luxury.

Also, your bank can switch to securing TLS with post-quantum key exchange algorithms with little difficulty and with no particular scalability or re-architecting challenges.

As for “256-bit”, the best known quantum attack against symmetric ciphers is Grover’s algorithm, and Grover’s algorithm will never break a targeted 256-bit symmetric key in the lifetime of the universe even if run by a hypothetical alien civilization with a Dyson sphere. (It might plausibly break one of many targeted keys in a multi-key attack run by advanced aliens, but this won’t steal your money and it could be easily mitigated by moving to 384 or 512 bits.)

[bawolff]

> If Bitcoin is broken then your bank encryption and everything else is broken also.

Its a lot easier for your bank to change encryption methods than it is for bitcoin. Presumably you mean TLS here (where else do banks use encryption? Disk encryption?). People are already deploying experiments with quantum-proof TLS.

> As far as I know quantum computers still can't even honestly factor 7x3=21, so you are good. And the 5x3=15 is iffy about how honest that was either.

This is probably the wrong way to look at it. Once you start multiplying numbers together (for real, using error corrected qubits), you are already like 85% there. Like if this was a marathon, the multiplying thing is like a km from the finish line. By the time you start seeing people there the race would already be mostly over.

[cyberpunk]

I still don’t really get the argument, like okay this extremely rich theoretical attacker can obtain the private key for the cert my service uses, and somehow they’re able to sniff my traffic and could then somehow extract creds. But that doesn’t give them my 2fa which is needed to book each transaction, and as soon as these attacks are in the wild anti fraud/surveillance systems will be in much harder mode.

I don’t see QC coming as meaning bank accounts will be emptied.

disclaimer: I work at a bank on such systems

[bawolff]

My bank definitely doesn't require 2FA on every transaction. It only requires it to log in. I guess other people have more security concious banks then me.

Even still, i think there is some benefit to attackers being able to passively monitor connections. Getting the info neccesary to conduct some other type of fraud outside of the system. Lots of frauds live or die on knowing enough about the victim's financial situation.

However it really doesn't matter, when it happens we will just switch to different encryption.

[i2km]

It’s turning into a bit of a grift now. So many crypto agility “consultants “ popping up with their slop graphics. Never mind the fact that even if a relevant quantum computer is built it will still cost the user millions of dollars to break each RSA key pair…

[bawolff]

I dont neccesarily think it would cost millions per key pair. Hard to say with the technology so immature, but it seems like the sort of thing with huge upfront costs but low marginal costs. Once you have a QC you dont have to build a new one for the next key pair.

[zeofig]

The problem here is the word "will". Because they don't exist.