Hacker News Reader

Comment by gjsman-1000 | Hacker News Reader

Post-quantum cryptography is not necessarily secure either. One of the four finalists in a NIST competition for post-quantum cryptography [SIDH] was suddenly, out of the blue, shattered with an algorithm that could break it in hours on a laptop. Turns out it was secure against quantum computers but insecure against classical computers.

If you want to be safe, you might almost consider standard cryptography on one of the three-remaining post-quantum algorithms to be (hopefully) safer. Also this might be bad news for Bitcoin in the ultra-long-term...

View on HN

There are open questions about whether any PQ algorithm is truly quantum-safe, given the limits of our knowledge about QC.

But it's also just the case that any "new" (for values of "new" that include "old but never deployed at a scale sufficient to attract scrutiny") encryption primitive, PQ or not, stands a decent change of being breakable by a laptop, at least in its initial implementation parameters. That's what happened with the supersingular isogenies you're referring to. That's just to say: there's nothing special about the "PQ-ness" of these protocols that makes them risky; all cryptography is risky. It took a surprisingly long time --- well into the 2000s --- to figure out how to safely deploy RSA.

Virtually every serious PQ implementation proposal pairs the PQ key exchange with a "conventional" key exchange, for this reason.

If you believe that QC is going to break "conventional" cryptography, Bitcoin is toast; I don't think there aren't a lot of extra "ifs" to that. Smarter people than me think there might be a window of time where RSA falls and ECC survives; maybe you could hope that Bitcoin would react quickly enough inside that window.

My understanding is that Bitcoin, used correctly, is effectively quantum safe.

Since the "recipient" address of a UTXO is expressed as a hash, a user does not broadcast their public key until after they spend the funds. If you follow good practice, you make a single transaction, sending funds to the recipient, and the "change" to yourself, in a new wallet address (addressed by the hash of its public key). This means the public key is never visible to an attacker until its balance is zero.

Therefore, to attack this and steal funds through false transactions, you effectively need both a pre-image attack on SHA256 (so you have a valid public key to match the UTXO address), and a way to solve the discrete logarithm problem, breaking ECDSA (on the Secp256k1 curve), so you can sign using the private key corresponding to that public key.

SHA256 would come under Grover's algorithm, I believe, which would give you 128 bits of security under a quantum attack. That is still pretty good going.

> This means the public key is never visible to an attacker until its balance is zero.

This part is just a tad questionable. To spend funds, you have to get the transaction recorded in a block. The usual way to do that is to broadcast it through the whole network until a miner picks it up.

So there's more than a bit of wiggle room between "I broadcast everything about this tx" until "the money is already spent and I'm safe.

It certainly does (in the usual case where the vast majority of the network and your connection to it is not under the attacker's control) limit the time an attacker has to compute, but it's not exactly pretty or reassuring.

It's worth noting that BTC could be quantum-resistant if enough of the network decided they wanted it to be. Unfortunately the BTC community is famously resistant to change so it wouldn't happen until it's too late, but in a rational world the problem could be fixed.

Alright. Who gets to confiscate the pre-quantum keyed Bitcoin? Miners or codebreakers?

SHA2 is not under threat from post-quantum computing. Only the signatures used.

And as long as you don't re-use wallet addresses, your public key is effectively not revealed until the balance is zero.

Since your wallet address is a sha256 hash of the public key, you would need to meaningfully break sha256 to be able to go after a public key or generate a false signature.

Once the public key is broadcast to spend the funds, that wallet shouldn't be reused, and a new wallet address should receive the change.

Yes, but the signatures are what's keeping your funds secure, not the hash.

To explain why, we need to talk about a type of nonstandard transaction people used to do as a sort of puzzle: hash-only outputs. This is a Bitcoin transaction whose outputs can only be spent by someone who knows the input that gives a particular SHA-256 output. Cute, right?

Problem is, this is a proof of knowledge, not a proof of identity. Anyone else can replicate it once the problem is solved and the solution does not restrict itself to whoever is identified as the first solver. Which means that the only thing that keeps people from claiming THEY were the first to solve it is the Sybil-resistance that keeps the blockchain from being reorg'd.

In Ethereum we call this the "dark forest" problem[0] - anything in the mempool that is not cryptographically locked down can and will be manipulated to the benefit of others. Smart contracts make it way more lucrative to scan the mempool for manipulable transactions, because instead of looking for the one guy solving old SHA-256 puzzles you now have potentially millions of arbitrage opportunities to find. But this isn't limited to Ethereum. It's whoever mines[1] the block wins.

So if quantum computing breaks RSA, that turns all existing coins into SHA-256 puzzles on a blockchain whose users haven't internalized the maximal extent of transaction malleability. The only way to avoid having your coins stolen would be to coordinate with trustworthy miners to include your signature transition transaction into a block - almost certainly with a very large fee, effectively a cooperative confiscation[2]. Those who rely on the kindness of strangers (read: the mempool) will find quantum computer owners and miners fighting to see who can steal their coins first. And the only protocol-level change to fix this would be to just invalidate all RSA signatures and treat all old wallets as burned.

[0] https://www.paradigm.xyz/2020/08/ethereum-is-a-dark-forest

[1] The Ethereum term for this is Miner Extractable Value, which reportedly has even incentivized miners to reorg blocks (i.e. a short-term 51% attack) if and when they can get away with it.

[2] This is, again, another thing Ethereum's ecosystem already thought of; they call it Flashbots.

Tangentially to secant, BTC community resistance is in the spirit of maintaining a solid base layer that is not perpetually in startup mode given stakeholder motives. Use other coins for that purpose.

Regarding changes that still maintain or even enhance this goal of long-lived store of value, I bet they'd be fine with that, even if the work effort of BTC transactions increased.

> Tangentially to secant

I see what you did there. And I approve.

> If you want to be safe

You use post-quantum with a vetted algorithm in a hybrid scheme, usually this just involves concatenation or hashing.

Reply on news.ycombinator.com