5 ms·

Even if this particular scheme doesn't work at scale, the writing is on the wall for conventional crypto. If you are encrypting data that will be at rest for mo

Even if this particular scheme doesn't work at scale, the writing is on the wall for conventional crypto. If you are encrypting data that will be at rest for more many years it's time to start think about migrating to post-quantum crypto so you don't end up one day discovering you're entire corpus is vulnerable.

gjsman-1000 4y ago
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.
zzz345345 4y ago
> If you are encrypting data that will be at rest for more many years it's time to start think about migrating to post-quantum crypto so you don't end up one day discovering you're entire corpus is vulnerable Because Bitcoin is centralized, if it would get cracked tomorrow, the major miners could decide to save everyone.
A4ET8a8uTh0 4y ago
I will admit that I have no idea how that would look like. If quantum computer can be as capable as one envisioned in Jormungand, I am not sure if anything short of declaring them a weapon is needed.
- advisedwang 4y ago
  Quantum computers aren't magic, they have specific capabilities that can be planned around. Google 'post-quantum cryptography' for current work on quantum resistent algorithms, some of which are already being deployed to production.
  - A4ET8a8uTh0 4y ago
    Any sufficiently advanced technology is indistinguishable from magic. I will openly say that I not understand it beyond knowing that, in a very general sense, it is not based on ones and zeroes. If I do not understand it, it is difficult for me to wrap my head around it and what it can and cannot do. It might not be magic, but it might as well be ( and may end up being next hype train ).
deleted 4y ago
[deleted]
version_five 4y ago
No practical quantum supremacy or anything like it has been demonstrated has it? Is it sort of expected that will co-occur with QC breaking encryption? I'm just trying to gauge how "almost here" this actually is, or if it's still talk
- bawolff 4y ago
  Quantum supremacy is a much much much lower bar than breaking rsa (at normal key strength)
- advisedwang 4y ago
  Cloudflare estimates 15-40 years[1]. Cloudflare, Google [2], Amazon [3] and others are all at various phases of moving to post-quantum algorithms. My own lesson from the Snowden revelations is that if we're close enough to a security break that the possibility is well understood, there's a very high chance someone is already doing it. [1] https://blog.cloudflare.com/post-quantum-for-all/ https://blog.cloudflare.com/post-quantum-for-all/ [2] https://cloud.google.com/blog/products/identity-security/why-google-now-uses-post-quantum-cryptography-for-internal-comms https://cloud.google.com/blog/products/identity-security/why... [3] https://www.amazon.science/blog/preparing-today-for-a-post-quantum-cryptographic-future https://www.amazon.science/blog/preparing-today-for-a-post-q...
spydum 4y ago
I would think most encryption at rest done using AES128/256, which is already quantum-resistant. It's mostly the key management which is at risk due to more heavily used RSA for asymmetric wrapping of keys.
- brobinson 4y ago
  AES-128 is effectively AES-64 when quantum computers exist which can run Grover's algorithm. That's not a huge exponent.
  - adgjlsfhk1 4y ago
    for the time being it's fine (we're a long way away from having fast quantum computers where 2^64 is a significant problem), and AES-256 is already widely used
  - upofadown 4y ago
    It's been pointed out that Grover's algorithm parallelizes very badly. So not AES-64. It probably will turn out that AES-128 bit is perfectly fine as it has a tremendous amount of margin to start with
Strilanc 4y ago
Another use case where you should be seriously considering using post-quantum techniques is update verification. If a piece of hardware needs to work 10 years from now, and it uses RSA or ECC public key crypto to verify proposed software updates, it may live long enough to see quantum computers break that.

gjsman-1000 4y ago

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.

zzz345345 4y ago

> If you are encrypting data that will be at rest for more many years it's time to start think about migrating to post-quantum crypto so you don't end up one day discovering you're entire corpus is vulnerable Because Bitcoin is centralized, if it would get cracked tomorrow, the major miners could decide to save everyone.

A4ET8a8uTh0 4y ago

I will admit that I have no idea how that would look like. If quantum computer can be as capable as one envisioned in Jormungand, I am not sure if anything short of declaring them a weapon is needed.

advisedwang 4y ago
Quantum computers aren't magic, they have specific capabilities that can be planned around. Google 'post-quantum cryptography' for current work on quantum resistent algorithms, some of which are already being deployed to production.
- A4ET8a8uTh0 4y ago
  Any sufficiently advanced technology is indistinguishable from magic. I will openly say that I not understand it beyond knowing that, in a very general sense, it is not based on ones and zeroes. If I do not understand it, it is difficult for me to wrap my head around it and what it can and cannot do. It might not be magic, but it might as well be ( and may end up being next hype train ).

deleted 4y ago

[deleted]

version_five 4y ago

No practical quantum supremacy or anything like it has been demonstrated has it? Is it sort of expected that will co-occur with QC breaking encryption? I'm just trying to gauge how "almost here" this actually is, or if it's still talk

bawolff 4y ago
Quantum supremacy is a much much much lower bar than breaking rsa (at normal key strength)
advisedwang 4y ago
Cloudflare estimates 15-40 years[1]. Cloudflare, Google [2], Amazon [3] and others are all at various phases of moving to post-quantum algorithms. My own lesson from the Snowden revelations is that if we're close enough to a security break that the possibility is well understood, there's a very high chance someone is already doing it. [1] https://blog.cloudflare.com/post-quantum-for-all/ https://blog.cloudflare.com/post-quantum-for-all/ [2] https://cloud.google.com/blog/products/identity-security/why-google-now-uses-post-quantum-cryptography-for-internal-comms https://cloud.google.com/blog/products/identity-security/why... [3] https://www.amazon.science/blog/preparing-today-for-a-post-quantum-cryptographic-future https://www.amazon.science/blog/preparing-today-for-a-post-q...

spydum 4y ago

I would think most encryption at rest done using AES128/256, which is already quantum-resistant. It's mostly the key management which is at risk due to more heavily used RSA for asymmetric wrapping of keys.

brobinson 4y ago
AES-128 is effectively AES-64 when quantum computers exist which can run Grover's algorithm. That's not a huge exponent.
- adgjlsfhk1 4y ago
  for the time being it's fine (we're a long way away from having fast quantum computers where 2^64 is a significant problem), and AES-256 is already widely used
- upofadown 4y ago
  It's been pointed out that Grover's algorithm parallelizes very badly. So not AES-64. It probably will turn out that AES-128 bit is perfectly fine as it has a tremendous amount of margin to start with

Strilanc 4y ago

Another use case where you should be seriously considering using post-quantum techniques is update verification. If a piece of hardware needs to work 10 years from now, and it uses RSA or ECC public key crypto to verify proposed software updates, it may live long enough to see quantum computers break that.