Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How to compute a 256 bit elliptic curve key with 50M Toffoli gates

arxiv.org

Post reply on HN
Print view View original

31–40 of 46 posts

Re: How to compute a 256 bit elliptic curve key with 50M Toffoli gates

#31

Post by SAI_Peregrinus »

flangola7 wrote: post #26
bawolff wrote: post #15

Earlier quoted context omitted.

Kind of goes without saying when nobody has built a quantum computer of the type we are talking about. No general purpose error corrected quantum computer has been used to do anything because they don't exist yet.

>No general purpose error corrected quantum computer has been used to do anything because they don't exist yet. It isn't cryptographically relevant yet, but quantum supremacy was achieved in 2020: https://arxiv.org/abs/2012.01625

That particular demonstration is interesting, but it's not a general-purpose error-corrected quantum computer. It's a single-purpose quantum computer that simulates a quantum process with fewer gate operations than a classical computer needs to simulate the same process.

Re: How to compute a 256 bit elliptic curve key with 50M Toffoli gates

#32

Post by Escapado »

About 5 years ago I wrote my master thesis on quantum computing, specifically on the construction of quantum circuits. As these circuits are generally unitary matrices an interesting question is: Given a set of gates that operate on one qbit or two qubits (controlled gates) and a target unitary matrix (e.g. fourier transform or the hamiltonian of a physical system of interest such as an Ising model), can we find an optimal/minimal arrangement of those gates to approximate or exactly match the target matrix.

Back then I modelled the quantum circuit as a set of unitaries (by parametrizing them through their generator), that operate on one or two qubits, set a limit to the amount of steps and the amount of controlled gates and then threw different optimization algorithms at it. I got the best performance using simple dense neural networks. What's cool is that I could generate a training set really quickly since I could just randomly build tensor products of unitary matricies to create billions of unitaries of up to 7 qubits in minimal time and then just see how close I can get given a fixed length for the quantum circuit and a fixed number of control gates.

I really liked this approach and it was fun to work on. However it was ultimately limited as the size of the matrices scales exponentially with the number of qubits.

Re: How to compute a 256 bit elliptic curve key with 50M Toffoli gates

#33

Post by tromp »

adastra22 wrote: post #14
htourweoi4324 wrote: post #11

Earlier quoted context omitted.

The D-Wave ones surely can't (theoretically unproven if it's doing anything 'useful', even if 'quantum').The ones that others have, theoretically can in the 'awesome future', but as yet can't (too noisy). Hype aside - the largest number factored using Shor on a physical device is 21 (unclear if they actually used the result of the factoring to design the circuits like they did with 15).

That seems like a damning critique, but the reality is that quantum capabilities can and likely will advance as a series of step functions. The quantum machines we can build now are so noisy that we can’t even factor 3 digit numbers. However low nois quantum computers are on the drawing board and would bring many order of magnitude improvements nearly overnight.

> The quantum machines we can build now are so noisy that we can’t even factor 3 digit numbers.

Or most 2-digit numbers, for that matter. After more than a decade, the record still stands at 21=3x7 [1].

[1] https://en.wikipedia.org/wiki/Integer_factorization_records#...

Re: How to compute a 256 bit elliptic curve key with 50M Toffoli gates

#34

Post by adastra22 »

SAI_Peregrinus wrote: post #31
flangola7 wrote: post #26

Earlier quoted context omitted.

>No general purpose error corrected quantum computer has been used to do anything because they don't exist yet. It isn't cryptographically relevant yet, but quantum supremacy was achieved in 2020: https://arxiv.org/abs/2012.01625

That particular demonstration is interesting, but it's not a general-purpose error-corrected quantum computer. It's a single-purpose quantum computer that simulates a quantum process with fewer gate operations than a classical computer needs to simulate the same process.

FYI there is no such thing as a general purpose quantum computer. All quantum computes are special purpose.

Re: How to compute a 256 bit elliptic curve key with 50M Toffoli gates

#36

Post by upofadown »

bob1029 wrote: post #30

I have a feeling the quantum-crypto conversation is going to take off like a rocket after IBM does their Quantum System 2 presentation later this year.

IBM has been on the edge of a major breakthrough for quite some time now...

They like to make larger and larger quantum computers that don't do anything useful. A sort of progress I suppose...

Re: How to compute a 256 bit elliptic curve key with 50M Toffoli gates

#38

Post by survirtual »

bawolff wrote: post #18
red_admiral wrote: post #16

Earlier quoted context omitted.

Generally true, but Google has started using the stuff in production: https://cloud.google.com/blog/products/identity-security/why...

But its still bleeding edge. Its been used for experimental purposes but always in combination with a traditional algorithm (so if its broken the traditional algo still secures things). Its definitely not trusted yet.

Yes, which is what google is doing if you read the blog post. They wrap PQC encrypted message with x25519.

Re: How to compute a 256 bit elliptic curve key with 50M Toffoli gates

#39

Post by survirtual »

phas0ruk wrote: post #3

Doesn’t this mean crypto has a major problem ?

Encrypted comms has a problem.

Crypto does not, for a lot of reasons, but biggest I can think of is that hashing is still one-way, public keys are hidden (until used, which is why it is important to expose your public key only when using funds).

When there is a viable ECC attack vector, it will not be much effort to migrate to a more mature PQC. Better to wait as long as possible, maybe even have a crypto built on PQC to field test it with money on the line -- a few billion in market cap goes a long way to incentivizing breaking the crypto involved.

Re: How to compute a 256 bit elliptic curve key with 50M Toffoli gates

#40

Post by sudosysgen »

adastra22 wrote: post #34
SAI_Peregrinus wrote: post #31

Earlier quoted context omitted.

That particular demonstration is interesting, but it's not a general-purpose error-corrected quantum computer. It's a single-purpose quantum computer that simulates a quantum process with fewer gate operations than a classical computer needs to simulate the same process.

FYI there is no such thing as a general purpose quantum computer. All quantum computes are special purpose.

That's not true. There is such a thing as a completely general set of quantum gates, which combined with qubit memory, would make for a general quantum computer capable of computing any unitary transformation to a certain accuracy.
Post reply on HN