Hacker News Reader

Comment by IncRnd | Hacker News Reader

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

View on HN

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.

Reply on news.ycombinator.com