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

41–46 of 46 posts

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

#41

Post by adastra22 »

sudosysgen wrote: post #40
adastra22 wrote: post #34

Earlier quoted context omitted.

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.

Not fully general, no. There is no such thing like a "Turning machine" for quantum computers. There are classes of algorithms like Shor's, Grover's, and quantum annealing which can be used to solve large many instances of related problems.

This is kinda like how matrix diagonalization can be used to solve any problem which is expressible as a linear system of equations, and to some degree any continuous function can be approximated by a linear system, so a BLAS + LAPACK accelerator is a "universal simulation engine."

You could probably build a generic Shor's algorithm quantum computer that is able to both factor integers and break elliptic curve keys. But the same quantum computer wouldn't be usable for Grover's algorithm to find the presage of a cryptographic hash. This is what I mean by there not being a "universal quantum computer" in the same way a Turing machine is a universal classical computer. Quantum computers by their very nature are ASIC implementations of specific algorithms, even though those algorithms might have some multi-domain applicability.

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

#42

Post by sudosysgen »

adastra22 wrote: post #41
sudosysgen wrote: post #40

Earlier quoted context omitted.

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.

Not fully general, no. There is no such thing like a "Turning machine" for quantum computers. There are classes of algorithms like Shor's, Grover's, and quantum annealing which can be used to solve large many instances of related problems. This is kinda like how matrix diagonalization can be used to solve any problem which is expressible as a linear system of equations, and to some degree any continuous function can…

That really isn't true. If you have the CNOT gate, controlled rotation and phase shift, you can implement any operation on a set of qbits. If you then have quantum registers, you have a truly universal quantum computer, as you can then use registers to chain operation arbitrarily.

This computer would be able to do Shor, Grover, QAOA, as well as any classical algorithm of course. If you're interested, I can try to describe the proof of universality, it's just a bit of linear algebra. Otherwise, you can look up "Solovay-Kitaev theorem".

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

#43

Post by was_a_dev »

Aachen wrote: post #19
aleph_minus_one wrote: post #9

Earlier quoted context omitted.

> In the realm of quantum computing, it always has No: https://en.wikipedia.org/wiki/Post-quantum_cryptography

I agree with you that the statement is overly broad, but the person is referring to asymmetric cryptography in the past tense, making me read it as not about PQC because PQC is indeed the fix for the stated problem but must be applied first and until then, indeed we've always known QC are going to be an issue that needs solving.

Thank you, I did

However I was also unaware of PQC, which has been an interesting rabbit hole for the day

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

#44

Post by bawolff »

upofadown wrote: post #28
its-summertime wrote: post #25

Earlier quoted context omitted.

Hence https://en.wikipedia.org/wiki/Forward_secrecy to make things more difficult Compromising the main keys isn't enough, need to compromise each session key as well in turn, a massive increase.

Forward secrecy does not provide any value against cryptography compromise. Quite the opposite as it depends on the security of the cryptography over the long term to insure old messages stay inaccessible after the key is forgotten. Forward secrecy addresses this specific attack: * Someone builds a archive of your encrypted messages, possibly without your knowledge or consent. * That someone then gets access to your…

I mean, it depends a little bit on what your threat model is. If it takes a week to break a key, and you have hundreds of thousands of tls sessions without knowing which is the relavent one, it is definitely something. But yeah it seems like it would quickly become a minor hurdle once real quantum computers become a thing and presumably have their own moore's law.

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

#45

Post by [deleted] »

wahahah wrote: post #22
bawolff wrote: post #17

Earlier quoted context omitted.

So its mostly just public-key encryption and its been a known issue since about 1994. We are still nowhere near making quantum computers that can crack them so its not an urgent thing. There has been a lot of research into alterantives though.

Being able to crack present-day communications in the future is still a concern.

[deleted]

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

#46

Post by adastra22 »

sudosysgen wrote: post #42
adastra22 wrote: post #41

Earlier quoted context omitted.

Not fully general, no. There is no such thing like a "Turning machine" for quantum computers. There are classes of algorithms like Shor's, Grover's, and quantum annealing which can be used to solve large many instances of related problems. This is kinda like how matrix diagonalization can be used to solve any problem which is expressible as a linear system of equations, and to some degree any continuous function can…

That really isn't true. If you have the CNOT gate, controlled rotation and phase shift, you can implement any operation on a set of qbits. If you then have quantum registers, you have a truly universal quantum computer, as you can then use registers to chain operation arbitrarily. This computer would be able to do Shor, Grover, QAOA, as well as any classical algorithm of course. If you're interested, I can try to des…

I’m still trying to wrap my head around this. Do you have a link to help explain how this would work?

I happen to be working on a commercial product for which manufacturing quantum computers is a real use case, so I should understand this.

Post reply on HN