3 ms·

Post-quantum cryptography is not necessarily secure either. One of the four finalists in a NIST competition for post-quantum cryptography [SIDH] was suddenly, o

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

Grimburger 4y ago
> 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.
g_p 4y ago
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.
- kadoban 4y ago
  > 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.
idiotsecant 4y ago
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.
- kmeisthax 4y ago
  Alright. Who gets to confiscate the pre-quantum keyed Bitcoin? Miners or codebreakers?
  - Grimburger 4y ago
    SHA2 is not under threat from post-quantum computing. Only the signatures used.
    - g_p 4y ago
      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.
    - kmeisthax 4y ago
      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 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.
tptacek 4y ago
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.

Grimburger 4y ago

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

g_p 4y ago

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.

kadoban 4y ago
> 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.

idiotsecant 4y ago

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.

kmeisthax 4y ago
Alright. Who gets to confiscate the pre-quantum keyed Bitcoin? Miners or codebreakers?
- Grimburger 4y ago
  SHA2 is not under threat from post-quantum computing. Only the signatures used.
  - g_p 4y ago
    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.
  - kmeisthax 4y ago
    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 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.

tptacek 4y ago

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.