Hacker News Reader

Comment by torcete | Hacker News Reader

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

View on HN

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

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.

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.

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?

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

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.

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.

Try actually reading it's aplication to eliptix curve cryptography. No really. Come back when all the bitcoin are belong to you.

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.

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

What cryptocurrencies are currently using post-quantum cryptography?

Only one I'm aware of is QRL ("quantum-resistant ledger").

https://www.theqrl.org/

No need for a hard fork. A soft fork like Taproot is doing this year would be sufficient.

While not implemented I think there are "lattice based" forms of cryptography that are believed to QC resistant that blockchains could migrate over to if QCs begin to show signs of increased fault tolerance and size.

Just don't re-use addresses. Bitcoin does not expose your public key until you spend from it.

> Bitcoin does not expose your public key until you spend from it.

Are you sure, what about when someone sends to it?

They're correct. The blockchain just records that the funds were sent to your address. To spend the funds you have to show the public key which hashes to that address, in another transaction signed by the private key.

If the sender wanted to send you a private message, they would need your public key, but that's not what transactions do.

Fair enough, thank you.

Sending to an address means sending it to a "hash" of a public key (or a more complex script) on all modern formats. Then such script and data is revealed on spend.

If the QC can crack your private key within a few minutes, it would still have a decent chance to steal your money.

The first entities that are likely to achieve practical quantum computers will either be governments or big tech companies like Google. And it will be a big deal, so there would likely be several years of warning before it could be at the point where it would make sense to use it to steal someone's bitcoins (I guess the original Satoshi coin address would be the biggest bounty). And in the time period between when the big development is first announced and before it's practical, Bitcoin and other cryptocurrency projects can do a fork to a new digital signature scheme that is quantum proof (such as LegRoast) so that anyone who is concerned can move their coins to a new secure address. So while it would certainly be disruptive, it wouldn't necessarily spell the doom of Bitcoin.

Depends on the incentives. If the only interest in quantum computing is to break classically hard encryption then I think the time between poc and widespread availability could be relatively short.

> 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_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.

> I wish this were talked about more.

This is talked about all the time in Bitcoin dev circles.

We already have a solution (https://en.wikipedia.org/wiki/Lamport_signature) but there’s no reason to deploy it yet since it reduces scalability.

The problem with "yet", in security, is that by the time you realize that "yet" is here, it's already too late.

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.

Reply on news.ycombinator.com