4 ms·

Layperson question: if modern cryptography is broken at some point in the future, would this also lead to the collapse of any cryptographic system that only dep

Layperson question: if modern cryptography is broken at some point in the future, would this also lead to the collapse of any cryptographic system that only depends on one-way functions? In other words, would the code-breaker be able to access any bitcoin wallet, de-anonymize any transaction? Is this risk built in to cryptocurrency? Edit: https://avs.scitation.org/doi/10.1116/5.0073075 https://avs.scitation.org/doi/10.1116/5.0073075 > Finally, we calculate the number of physical qubits required to break the 256-bit elliptic curve encryption of keys in the Bitcoin network within the small available time frame in which it would actually pose a threat to do so. It would require 317 × 10 ^ 6 physical qubits to break the encryption within one hour using the surface code, a code cycle time of 1 μs, a reaction time of 10 μs, and a physical gate error of 10−3. To instead break the encryption within one day, it would require 13 × 10 ^ 6 physical qubits

Someone 4y ago
Not necessarily. A mathematical proof that one-way functions do not exist need not say anything about non-one-way functions, so it need not say anything about how hard it is to invert what we now think might be one-way functions. But yes, the risk that we don’t know whether encryption is mathematically possible hangs above every use of cryptography, using hashes to verify that data didn’t get tampered with, etc.
dibujante 4y ago
Yes, I believe so, although millions of qubits are still many orders of magnitude away from the largest quantum computers currently in existence. If Moore's Law applies to quantum computers (big if) then it will take about 50 years for quantum computers to crack 256-bit encryption within a day. Maybe this will spark a cryptography arms race where keys just get larger for a while to postpone that day.
- SAI_Peregrinus 4y ago
  There also seem to be some fundamental limits on computation in physical systems. The Landauer limit is a famous one. Even with quantum computers, you quickly start needing ridiculous amounts of energy, on the order of "build a dyson swarm". Any symmetric system with a 512-bit key will be secure against solar-system sized quantum computers for many human lifetimes.
- macksd 4y ago
  The arms race already exists: hash sizes and standard key sizes have increased. Because Moore's Law already applies to classical computers: you effectively lose 1 bit of entropy / security every year.
  - upofadown 4y ago
    I think that would be a bit every 2 years based on Moore's law after the 80's and actual progress has been slower than that for something like a decade now. There are looming fundamental physical limits. Moore's law refers to hardware capacity and not speed. If you can't figure out how to completely parallelize your attack then that is important. And things are not getting significantly faster. So a lot of stuff is likely to be safe indefinitely under current technological conditions. A complete breakthrough like quantum computing would be required. Makes it hard to predict things.
politelemon 4y ago
(Also layperson, so this is based on my understanding of reading other people's material). Yes that is the case, our current one-ways, especially RSA, are considered broken by quantum computers and will be proper broken once more qubits are a reality. https://en.wikipedia.org/wiki/Shor%27s_algorithm https://en.wikipedia.org/wiki/Shor%27s_algorithm There are already efforts underway to replace it with something quantum safe. It's believed that lattice based cryptography will help us. https://en.wikipedia.org/wiki/Lattice-based_cryptography https://en.wikipedia.org/wiki/Lattice-based_cryptography. There will be updates required to a lot of infrastructure and digital assets to secure them. Some things will be simple updates, some will require moving to new wallets.
abhv 4y ago
"if modern cryptography is broken": this statement has many interpretations. In the context of the OP paper, approximately solving the t-bounded Kolmogorov complexity (in a precise technical sense described in that paper) is akin to breaking one-way functions. A method to breaking one-way functions would in fact break all of the cryptographic schemes (enc, signatures, prgs, hashing, zero-knowledge, mpc, bitcoin...) that rely on computational assumptions that we know. There is then no hope for doing things like we do on the internet today. A secondary interpretation relates to breaking a specific widespread cryptosystem like ECDSA or Ed25519 (which can both be broken with suitably large generic circuit quantum computers). In this context, maybe some important things break, but in principle, we can rebuild them using lattice-based schemes or something else.
- l33t2328 4y ago
  Hashing would be generally be fine. AES would still be totally okay.
  - thiagoharry 4y ago
    No and no. If a hash function is not an one-way function, it cannot be collision-resistant. And the security in AES assumes that it is an one-way function. Otherwise, anyone could decrypt reversing the function.
    - l33t2328 4y ago
      You have some slight misunderstanding. AES does not need to be a one way function. It’s trivial to compute the preimage of a ciphertext. Just choose any key and decrypt it.
  - mdoms 4y ago
    I'm a layperson, but isn't hashing the quintessential one way function? (at least for industry software engineers).
    - denton-scratch 4y ago

Someone 4y ago

Not necessarily. A mathematical proof that one-way functions do not exist need not say anything about non-one-way functions, so it need not say anything about how hard it is to invert what we now think might be one-way functions. But yes, the risk that we don’t know whether encryption is mathematically possible hangs above every use of cryptography, using hashes to verify that data didn’t get tampered with, etc.

dibujante 4y ago

Yes, I believe so, although millions of qubits are still many orders of magnitude away from the largest quantum computers currently in existence. If Moore's Law applies to quantum computers (big if) then it will take about 50 years for quantum computers to crack 256-bit encryption within a day. Maybe this will spark a cryptography arms race where keys just get larger for a while to postpone that day.

SAI_Peregrinus 4y ago
There also seem to be some fundamental limits on computation in physical systems. The Landauer limit is a famous one. Even with quantum computers, you quickly start needing ridiculous amounts of energy, on the order of "build a dyson swarm". Any symmetric system with a 512-bit key will be secure against solar-system sized quantum computers for many human lifetimes.
macksd 4y ago
The arms race already exists: hash sizes and standard key sizes have increased. Because Moore's Law already applies to classical computers: you effectively lose 1 bit of entropy / security every year.
- upofadown 4y ago
  I think that would be a bit every 2 years based on Moore's law after the 80's and actual progress has been slower than that for something like a decade now. There are looming fundamental physical limits. Moore's law refers to hardware capacity and not speed. If you can't figure out how to completely parallelize your attack then that is important. And things are not getting significantly faster. So a lot of stuff is likely to be safe indefinitely under current technological conditions. A complete breakthrough like quantum computing would be required. Makes it hard to predict things.

politelemon 4y ago

(Also layperson, so this is based on my understanding of reading other people's material). Yes that is the case, our current one-ways, especially RSA, are considered broken by quantum computers and will be proper broken once more qubits are a reality. https://en.wikipedia.org/wiki/Shor%27s_algorithm https://en.wikipedia.org/wiki/Shor%27s_algorithm There are already efforts underway to replace it with something quantum safe. It's believed that lattice based cryptography will help us. https://en.wikipedia.org/wiki/Lattice-based_cryptography https://en.wikipedia.org/wiki/Lattice-based_cryptography. There will be updates required to a lot of infrastructure and digital assets to secure them. Some things will be simple updates, some will require moving to new wallets.

abhv 4y ago

"if modern cryptography is broken": this statement has many interpretations. In the context of the OP paper, approximately solving the t-bounded Kolmogorov complexity (in a precise technical sense described in that paper) is akin to breaking one-way functions. A method to breaking one-way functions would in fact break all of the cryptographic schemes (enc, signatures, prgs, hashing, zero-knowledge, mpc, bitcoin...) that rely on computational assumptions that we know. There is then no hope for doing things like we do on the internet today. A secondary interpretation relates to breaking a specific widespread cryptosystem like ECDSA or Ed25519 (which can both be broken with suitably large generic circuit quantum computers). In this context, maybe some important things break, but in principle, we can rebuild them using lattice-based schemes or something else.

l33t2328 4y ago
Hashing would be generally be fine. AES would still be totally okay.
- thiagoharry 4y ago
  No and no. If a hash function is not an one-way function, it cannot be collision-resistant. And the security in AES assumes that it is an one-way function. Otherwise, anyone could decrypt reversing the function.
  - l33t2328 4y ago
    You have some slight misunderstanding. AES does not need to be a one way function. It’s trivial to compute the preimage of a ciphertext. Just choose any key and decrypt it.
- mdoms 4y ago
  I'm a layperson, but isn't hashing the quintessential one way function? (at least for industry software engineers).
  - denton-scratch 4y ago