3 ms·

The quantum algorithm that would break certain kinds of public key cryptography schemes (not even the core part of Bitcoin blockchains, which are not vulnerable

The quantum algorithm that would break certain kinds of public key cryptography schemes (not even the core part of Bitcoin blockchains, which are not vulnerable to quantum computers) will take days to weeks to break a single key [0]. This is another reason why we will have plenty of warning before quantum computing causes any major disruptions to daily life. What I would start worrying about is the security of things like messages sent via end-to-end encrypted services like WhatsApp and Signal. Intercepted messages can be saved now and decrypted any time in the future, so it's better to switch to more robust cryptography sooner rather than later. Signal has taken steps in this direction recently: https://arstechnica.com/security/2025/10/why-signals-post-quantum-makeover-is-an-amazing-engineering-achievement/ https://arstechnica.com/security/2025/10/why-signals-post-qu.... [0] https://arxiv.org/pdf/2505.15917 https://arxiv.org/pdf/2505.15917

twothreeone 1y ago
Usually, the crypto should have Forward Secrecy already even without being PQ-safe (e.g., via https://en.wikipedia.org/wiki/Double_Ratchet_Algorithm https://en.wikipedia.org/wiki/Double_Ratchet_Algorithm) so in practice the attacker would need to break many successive session keys - which rotates every time a new message is sent.
dweekly 1y ago
Meta has been rolling out PQC: https://engineering.fb.com/2024/05/22/security/post-quantum-readiness-tls-pqr-meta/ https://engineering.fb.com/2024/05/22/security/post-quantum-... And Apple: https://security.apple.com/blog/imessage-pq3/ https://security.apple.com/blog/imessage-pq3/ Cloudflare started rolling it out three years ago! https://developers.cloudflare.com/ssl/post-quantum-cryptography/ https://developers.cloudflare.com/ssl/post-quantum-cryptogra...
johncolanduoni 1y ago
> not even the core part of Bitcoin blockchains, which are not vulnerable to quantum computers Um, what? Shor’s algorithm can take the public key of a wallet (present on any outgoing transaction in the ledger) and produce its private key. So now you can hijack any wallet that has transferred any Bitcoin. Notably only one successful run of the algorithm is needed per wallet, so you could just pick a big one if it takes weeks. It probably wouldn’t help you mine in practice, sure. Technically it would give you better asymptotic mining performance (via Grover’s algorithm) but almost certainly worse in practice for the foreseeable future.
- tczMUFlmoNk 1y ago
  > public key of a wallet (present on any outgoing transaction in the ledger) Genuine question: is this true? I only know a little bit about Bitcoin, but I thought there was a notion of an "extended public key" that's not exposed to the ledger, where each individual public key on the ledger is only used once, or something like that. I'm not at all confident in my understanding, so I'd love if you or someone else knowledgeable could help fill in the gaps.
  - johncolanduoni 1y ago
    Extended public keys can be used to generate a family of addresses, but each transaction still needs the public key for any address that has sent money. Someone who uses it religiously can keep most of their money in addresses with no outgoing transactions, meaning their public key is actually secret and therefore cannot be attacked. But there’s so many addresses that have outgoing transactions and huge balances that it wouldn’t make a difference to an attacker - they could skim a fortune and cash out from wallets that are not so well protected.
    - tczMUFlmoNk 1y ago
      Thanks for explaining!
    - andy_ppp 1y ago
      The real issue is as soon as this is done once Bitcoin's value plummets to a fraction of what it was today while people scramble to fix the algorithms.

twothreeone 1y ago

Usually, the crypto should have Forward Secrecy already even without being PQ-safe (e.g., via https://en.wikipedia.org/wiki/Double_Ratchet_Algorithm https://en.wikipedia.org/wiki/Double_Ratchet_Algorithm) so in practice the attacker would need to break many successive session keys - which rotates every time a new message is sent.

dweekly 1y ago

Meta has been rolling out PQC: https://engineering.fb.com/2024/05/22/security/post-quantum-readiness-tls-pqr-meta/ https://engineering.fb.com/2024/05/22/security/post-quantum-... And Apple: https://security.apple.com/blog/imessage-pq3/ https://security.apple.com/blog/imessage-pq3/ Cloudflare started rolling it out three years ago! https://developers.cloudflare.com/ssl/post-quantum-cryptography/ https://developers.cloudflare.com/ssl/post-quantum-cryptogra...

johncolanduoni 1y ago

> not even the core part of Bitcoin blockchains, which are not vulnerable to quantum computers Um, what? Shor’s algorithm can take the public key of a wallet (present on any outgoing transaction in the ledger) and produce its private key. So now you can hijack any wallet that has transferred any Bitcoin. Notably only one successful run of the algorithm is needed per wallet, so you could just pick a big one if it takes weeks. It probably wouldn’t help you mine in practice, sure. Technically it would give you better asymptotic mining performance (via Grover’s algorithm) but almost certainly worse in practice for the foreseeable future.

tczMUFlmoNk 1y ago
> public key of a wallet (present on any outgoing transaction in the ledger) Genuine question: is this true? I only know a little bit about Bitcoin, but I thought there was a notion of an "extended public key" that's not exposed to the ledger, where each individual public key on the ledger is only used once, or something like that. I'm not at all confident in my understanding, so I'd love if you or someone else knowledgeable could help fill in the gaps.
- johncolanduoni 1y ago
  Extended public keys can be used to generate a family of addresses, but each transaction still needs the public key for any address that has sent money. Someone who uses it religiously can keep most of their money in addresses with no outgoing transactions, meaning their public key is actually secret and therefore cannot be attacked. But there’s so many addresses that have outgoing transactions and huge balances that it wouldn’t make a difference to an attacker - they could skim a fortune and cash out from wallets that are not so well protected.
  - tczMUFlmoNk 1y ago
    Thanks for explaining!
  - andy_ppp 1y ago
    The real issue is as soon as this is done once Bitcoin's value plummets to a fraction of what it was today while people scramble to fix the algorithms.