5 ms·

After watching the latest Veritasium video about how Newton figured out a novel approach to solving PI which was dramatically simpler than the previous thousand

After watching the latest Veritasium video about how Newton figured out a novel approach to solving PI which was dramatically simpler than the previous thousand-year old methods, I wonder if someone will come along and figure out a simple mathematical way to break these encryptions. That would be horrifying of course, but also really cool.

jhardy54 6y ago
They will! This is called cryptanalysis, and it's very common for ciphers to be weakened over time.
chrispeel 6y ago
Peter Shor did this in the 90s. Lotsa people are working on quantum computers and hoping to, among other things, crack these codes https://en.wikipedia.org/wiki/Elliptic-curve_cryptography#Quantum_computing_attacks https://en.wikipedia.org/wiki/Elliptic-curve_cryptography#Qu...
- ben_w 6y ago
  I thought the cryptographic basis for BTC was supposed to not be susceptible to Shor’s algorithm, or indeed any known quantum speedup?
  - chrispeel 6y ago
    https://medium.com/drive-insider/the-quantum-attack-on-bitcoin-d676017024bc https://medium.com/drive-insider/the-quantum-attack-on-bitco... Not just Bitcoin, and not just all other popular cryptocurrencies, but all your web traffic and more are all susceptible to quantum attack.
    - ben_w 6y ago
      Conversely: https://crypto.stackexchange.com/questions/59375/are-hash-functions-strong-against-quantum-cryptanalysis-and-or-independent-enoug https://crypto.stackexchange.com/questions/59375/are-hash-fu... Indicates the best known quantum speedup square roots the search space, and the search space in SHA256 is still too big to search exhaustively.
undefined1 6y ago
if that happens, how far and fast would Bitcoin fall?
- O5vYtytb 6y ago
  Just as fast as the rest of society in which no message has a guarantee of privacy.
  - mxscho 6y ago
    Strictly speaking, you could still use one-time pads. So it's not "no" message.
- meowkit 6y ago
  As the other guy points out, we have a lot bigger problems than Bitcoin falling. But it likely won't happen at all. Lots of work is being done on quantum proof cryptography[1]. IT systems and crypto can be upgraded to use it. The real problem is going to be all the stashed encrypted data that US and China have stored on each other of a sensitive nature. The encryption on this information could be cracked by a quantum computer. [1] https://en.wikipedia.org/wiki/Post-quantum_cryptography https://en.wikipedia.org/wiki/Post-quantum_cryptography
  - garmaine 6y ago
    Unfortunately the work being done on post quantum cryptography is mostly on the topic of symmetric key agreement (since that is what TLS needs), and cryptocurrencies need digital signature and/ zero knowledge proof systems. There is comparably much less work being done on solving those problems.
    - Ar-Curunir 6y ago
      Er TLS also needs signatures, and there’s a ton of work on PQ signatures
      - 6y ago
sneak 6y ago
That video was one of the best videos on mathematics I have ever seen; the visualizations to aid in the explanation of Newton's "new" algorithm were absolutely top-notch. I'm not sure I could have followed it without them. With them, I feel like I know it well enough now to explain it to someone else. The thing with applied cryptography is that everyone is expecting the attacks to get better over time, sometimes in big and inconvenient bursts. There are several strategies to mitigate this, including oversizing security margins by a certain amount (so that an innovation that improves an attack by an order of magnitude or two isn't an instantaneous shattering of your whole security model), and having what's sometimes termed "algorithm agility" (which has somewhat fallen out of favor recently due to having its own class of bugs due to the implementations around, say, an optional NONE pluggable cipher type).
- willis936 6y ago
  Check out 3brown1blue if you haven’t already. The animations are excellent.
  - dgellow 6y ago
    3brown1blue is also the creator of manim, the library used for his own videos: https://github.com/3b1b/manim https://github.com/3b1b/manim. It's an awesome python library to create math animations, I would highly recommend it.

jhardy54 6y ago

They will! This is called cryptanalysis, and it's very common for ciphers to be weakened over time.

chrispeel 6y ago

Peter Shor did this in the 90s. Lotsa people are working on quantum computers and hoping to, among other things, crack these codes https://en.wikipedia.org/wiki/Elliptic-curve_cryptography#Quantum_computing_attacks https://en.wikipedia.org/wiki/Elliptic-curve_cryptography#Qu...

ben_w 6y ago
I thought the cryptographic basis for BTC was supposed to not be susceptible to Shor’s algorithm, or indeed any known quantum speedup?
- chrispeel 6y ago
  https://medium.com/drive-insider/the-quantum-attack-on-bitcoin-d676017024bc https://medium.com/drive-insider/the-quantum-attack-on-bitco... Not just Bitcoin, and not just all other popular cryptocurrencies, but all your web traffic and more are all susceptible to quantum attack.
  - ben_w 6y ago
    Conversely: https://crypto.stackexchange.com/questions/59375/are-hash-functions-strong-against-quantum-cryptanalysis-and-or-independent-enoug https://crypto.stackexchange.com/questions/59375/are-hash-fu... Indicates the best known quantum speedup square roots the search space, and the search space in SHA256 is still too big to search exhaustively.

undefined1 6y ago

if that happens, how far and fast would Bitcoin fall?

O5vYtytb 6y ago
Just as fast as the rest of society in which no message has a guarantee of privacy.
- mxscho 6y ago
  Strictly speaking, you could still use one-time pads. So it's not "no" message.
meowkit 6y ago
As the other guy points out, we have a lot bigger problems than Bitcoin falling. But it likely won't happen at all. Lots of work is being done on quantum proof cryptography[1]. IT systems and crypto can be upgraded to use it. The real problem is going to be all the stashed encrypted data that US and China have stored on each other of a sensitive nature. The encryption on this information could be cracked by a quantum computer. [1] https://en.wikipedia.org/wiki/Post-quantum_cryptography https://en.wikipedia.org/wiki/Post-quantum_cryptography
- garmaine 6y ago
  Unfortunately the work being done on post quantum cryptography is mostly on the topic of symmetric key agreement (since that is what TLS needs), and cryptocurrencies need digital signature and/ zero knowledge proof systems. There is comparably much less work being done on solving those problems.
  - Ar-Curunir 6y ago
    Er TLS also needs signatures, and there’s a ton of work on PQ signatures
    - 6y ago

sneak 6y ago

That video was one of the best videos on mathematics I have ever seen; the visualizations to aid in the explanation of Newton's "new" algorithm were absolutely top-notch. I'm not sure I could have followed it without them. With them, I feel like I know it well enough now to explain it to someone else. The thing with applied cryptography is that everyone is expecting the attacks to get better over time, sometimes in big and inconvenient bursts. There are several strategies to mitigate this, including oversizing security margins by a certain amount (so that an innovation that improves an attack by an order of magnitude or two isn't an instantaneous shattering of your whole security model), and having what's sometimes termed "algorithm agility" (which has somewhat fallen out of favor recently due to having its own class of bugs due to the implementations around, say, an optional NONE pluggable cipher type).

willis936 6y ago
Check out 3brown1blue if you haven’t already. The animations are excellent.
- dgellow 6y ago
  3brown1blue is also the creator of manim, the library used for his own videos: https://github.com/3b1b/manim https://github.com/3b1b/manim. It's an awesome python library to create math animations, I would highly recommend it.