Doesn’t this mean crypto has a major problem ?
Subtext: This is about quantum computers, which have been known to break RSA and ECC for the order of 30-ish years now.
You mean "theoretically known"
How to compute a 256 bit elliptic curve key with 50M Toffoli gates
21–30 of 46 posts
Re: How to compute a 256 bit elliptic curve key with 50M Toffoli gates
#22Doesn’t this mean crypto has a major problem ?
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.
Re: How to compute a 256 bit elliptic curve key with 50M Toffoli gates
#23"At 10% threshold, assuming a 10-μs code cycle and non-local connections, one key can be generated every 10 minutes using 6000 modules with 1152 physical qubits each." 1152 qubits sounds like the D-Wave chips. So does that mean 6000 D-wave chips ? Even if you reverse the calculation, that would be 60000 minutes on 1 chip, which is about 42 days only, so. Quantum Too Good
The paper is about digital gate-based quantum computers. These have almost nothing in common with D-Wave's analogue quantum annealers. They certainly cannot run Shor's algorithm (they don't run algorithms at all).
Re: How to compute a 256 bit elliptic curve key with 50M Toffoli gates
#24RIP Passkeys.
I'm sure if Passkeys are found to be susceptible to quantum cracking, they will move on post-quantum encryption.
Re: How to compute a 256 bit elliptic curve key with 50M Toffoli gates
#25Earlier 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.
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.
Re: How to compute a 256 bit elliptic curve key with 50M Toffoli gates
#26Earlier quoted context omitted.
*known to be able to No quantum computer has ever been used for that purpose in real life, however.
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
Re: How to compute a 256 bit elliptic curve key with 50M Toffoli gates
#27Earlier 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
I don't think that machine was either general-purpose or error-corrected though. IIUC we can build at most a few error-corrected gates right now.
Re: How to compute a 256 bit elliptic curve key with 50M Toffoli gates
#28Earlier quoted context omitted.
Being able to crack present-day communications in the future is still a concern.
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 secret key material.
* They can then decrypt their archive.
The session keys are exchanged by the asymmetrical systems that the imagined quantum computer would be able to break. So the attacker gets the session keys directly. So for, say, signal, they only have to break a new key exchange which doesn't happen all that often. They can just run the hash ratchet after that. Even for TLS that does a new session key per connection, that connection might last a fair time. The 10 min can be spread over multiple connections for this proposal. We are hardly talking about a massive increase of difficulty.
Re: How to compute a 256 bit elliptic curve key with 50M Toffoli gates
#29Earlier 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.
I'd imagine that's exactly why the NSA hoards the (rumored) absurd amount of data in the Utah data center
Re: How to compute a 256 bit elliptic curve key with 50M Toffoli gates
#30I 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.