4 ms·

I wonder how strong would Elliptic Curve Cryptography be compared to other methods if there is a major breakthrough in quantum computing.

IncRnd 5y ago
Shor's algorithm, which runs partially on a classical computer and a portion on a quantum computer, breaks elliptic-curve cryptography.
- plebianRube 5y ago
  Yes, with major caveats - knowing the public key and having 100s of messages signed by corresponding private key. Nowadays people only expose their public key one time per transaction, and never reuse their address. So to steal coins, not only do you have only ~10 mins between blocks to find the private key, currently Shor's algorithm is unfeasible with only 1 signed message.
  - tromp 5y ago
    Not only do many people still reuse keys, but there is also still a huge amount of bitcoin in P2PK outputs, i.e. with exposed public keys.
  - deleted 5y ago
    [deleted]
  - erostrate 5y ago
    Sorry if that's a naive question but why do you need several signed messages? If you have a quantum computer and a quantum period finding function don't you get immediately the discrete log? Assuming you have one public key (not hashed) doesn't that give you the private key immediately?
    - plebianRube 5y ago
      Broadly speaking, more signed messages can get you more points on the curve you're trying to guess. https://www.cs.umd.edu/~amchilds/teaching/w08/l03.pdf https://www.cs.umd.edu/~amchilds/teaching/w08/l03.pdf May help if you're actually interested. Edit: More signed transactions help with the classical and not the quantum part of schor. Edit2: Schor has not yet even been able to factor the integer 35 with current quantum hardware, too much interference.
  - IncRnd 5y ago
    Shor's integer factorization algorithm needs a single number or key to factor, not hundreds of transactions. I've certainly sent money to old addresses, which exist in perpetuity on the blockchain. I can also use web searches to find hundreds of current public keys in a matter of minutes. > currently Shor's algorithm is unfeasible with only 1 signed message. The algorithm is currently unfeasible with 100s of messages. Shor's algorithm uses a quantum computer to reduce the complexity of integer factorization from sub-exponential to polynomial-time. It is not an attack that fine-tunes the output according to the amount of network traffic.
    - plebianRube 5y ago
      Try actually reading it's aplication to eliptix curve cryptography. No really. Come back when all the bitcoin are belong to you.
chadhutchins10 5y ago
I wish this were talked about more. Quantum computing is the biggest long-term threat to crypto imo. What's the plan once elliptic curve cryptography can be broken? There will be a point in time where there are just a few quantum computers that can break everything before the general public has access to quantum computing. Can crypto work in that scenario? Normal computers wouldn't be able to work with the beastly algorithms a quantum computer could handle.
- G3rn0ti 5y ago
  > What's the plan once elliptic curve cryptography can be broken? A likely drop-in replacement for elliptic curve cryptography (ECC) currently used by Bitcoin could be https://en.wikipedia.org/wiki/Supersingular_isogeny_key_exchange https://en.wikipedia.org/wiki/Supersingular_isogeny_key_exch... I am not a Mathematician, but what I understood, it's basically an extension of ECC using multiple elliptic curves, allows to re-use the Diffie–Hellman key exchange protocol (private keys kept secret, public keys exchanged) and memory requirements are small. So it would be a perfect replacement in wallets and validation nodes. But I can not explain why it is safe against an attack using quantum computers.
- exdsq 5y ago
  There's a lot of research and practical work on quantum-proof cryptography which is already in use in some cryptocurrencies - 'just' need to hardfork and update it when it's ready for Bitcoin
  - 21eleven 5y ago
    What cryptocurrencies are currently using post-quantum cryptography?
    - DennisP 5y ago
      Only one I'm aware of is QRL ("quantum-resistant ledger"). https://www.theqrl.org/ https://www.theqrl.org/
  - anonporridge 5y ago
SuchAnonMuchWow 5y ago
In theory, it is also broken. It practice, it appears to be slightly harder to break than RSA for the same security level as we define it in non-quantum computing, but not by much.

IncRnd 5y ago

Shor's algorithm, which runs partially on a classical computer and a portion on a quantum computer, breaks elliptic-curve cryptography.

plebianRube 5y ago
Yes, with major caveats - knowing the public key and having 100s of messages signed by corresponding private key. Nowadays people only expose their public key one time per transaction, and never reuse their address. So to steal coins, not only do you have only ~10 mins between blocks to find the private key, currently Shor's algorithm is unfeasible with only 1 signed message.
- tromp 5y ago
  Not only do many people still reuse keys, but there is also still a huge amount of bitcoin in P2PK outputs, i.e. with exposed public keys.
- deleted 5y ago
  [deleted]
- erostrate 5y ago
  Sorry if that's a naive question but why do you need several signed messages? If you have a quantum computer and a quantum period finding function don't you get immediately the discrete log? Assuming you have one public key (not hashed) doesn't that give you the private key immediately?
  - plebianRube 5y ago
    Broadly speaking, more signed messages can get you more points on the curve you're trying to guess. https://www.cs.umd.edu/~amchilds/teaching/w08/l03.pdf https://www.cs.umd.edu/~amchilds/teaching/w08/l03.pdf May help if you're actually interested. Edit: More signed transactions help with the classical and not the quantum part of schor. Edit2: Schor has not yet even been able to factor the integer 35 with current quantum hardware, too much interference.
- IncRnd 5y ago
  Shor's integer factorization algorithm needs a single number or key to factor, not hundreds of transactions. I've certainly sent money to old addresses, which exist in perpetuity on the blockchain. I can also use web searches to find hundreds of current public keys in a matter of minutes. > currently Shor's algorithm is unfeasible with only 1 signed message. The algorithm is currently unfeasible with 100s of messages. Shor's algorithm uses a quantum computer to reduce the complexity of integer factorization from sub-exponential to polynomial-time. It is not an attack that fine-tunes the output according to the amount of network traffic.
  - plebianRube 5y ago
    Try actually reading it's aplication to eliptix curve cryptography. No really. Come back when all the bitcoin are belong to you.

chadhutchins10 5y ago

I wish this were talked about more. Quantum computing is the biggest long-term threat to crypto imo. What's the plan once elliptic curve cryptography can be broken? There will be a point in time where there are just a few quantum computers that can break everything before the general public has access to quantum computing. Can crypto work in that scenario? Normal computers wouldn't be able to work with the beastly algorithms a quantum computer could handle.

G3rn0ti 5y ago
> What's the plan once elliptic curve cryptography can be broken? A likely drop-in replacement for elliptic curve cryptography (ECC) currently used by Bitcoin could be https://en.wikipedia.org/wiki/Supersingular_isogeny_key_exchange https://en.wikipedia.org/wiki/Supersingular_isogeny_key_exch... I am not a Mathematician, but what I understood, it's basically an extension of ECC using multiple elliptic curves, allows to re-use the Diffie–Hellman key exchange protocol (private keys kept secret, public keys exchanged) and memory requirements are small. So it would be a perfect replacement in wallets and validation nodes. But I can not explain why it is safe against an attack using quantum computers.
exdsq 5y ago
There's a lot of research and practical work on quantum-proof cryptography which is already in use in some cryptocurrencies - 'just' need to hardfork and update it when it's ready for Bitcoin
- 21eleven 5y ago
  What cryptocurrencies are currently using post-quantum cryptography?
  - DennisP 5y ago
    Only one I'm aware of is QRL ("quantum-resistant ledger"). https://www.theqrl.org/ https://www.theqrl.org/
- anonporridge 5y ago

SuchAnonMuchWow 5y ago

In theory, it is also broken. It practice, it appears to be slightly harder to break than RSA for the same security level as we define it in non-quantum computing, but not by much.