7 ms·
How to compute a 256 bit elliptic curve key with 50M Toffoli gates
- unsolved73 3y agoRIP Passkeys.
- rhn_mk1 3y agoI'm sure if Passkeys are found to be susceptible to quantum cracking, they will move on post-quantum encryption.
- phas0ruk 3y agoDoesn’t this mean crypto has a major problem ?
- was_a_dev 3y agoIn the realm of quantum computing, it always has
- aleph_minus_one 3y ago> In the realm of quantum computing, it always has No: https://en.wikipedia.org/wiki/Post-quantum_cryptography https://en.wikipedia.org/wiki/Post-quantum_cryptography
- adastra22 3y agoPQC is very immature.
- red_admiral 3y agoGenerally true, but Google has started using the stuff in production: https://cloud.google.com/blog/products/identity-security/why-google-now-uses-post-quantum-cryptography-for-internal-comms https://cloud.google.com/blog/products/identity-security/why...
- bawolff 3y agoBut 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.
- survirtual 3y agoYes, which is what google is doing if you read the blog post. They wrap PQC encrypted message with x25519.
- Aachen 3y agoI 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.
- was_a_dev 3y agoThank you, I did However I was also unaware of PQC, which has been an interesting rabbit hole for the day
- some_furry 3y agoSubtext: This is about quantum computers, which have been known to break RSA and ECC for the order of 30-ish years now.
- adastra22 3y ago*known to be able to No quantum computer has ever been used for that purpose in real life, however.
- bawolff 3y agoKind 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.
- Aachen 3y agoI don't think that's common knowledge. It's commonly accepted truth in the industry, but particularly when most people think of military/spies as secretly X years ahead (pick a number) of what the public knows is possible, the tech sector in general can't be expected to know this. It's good to add this in a thread with a headline that sounds like anyone using ecc keys might have a big problem.
- flangola7 3y ago>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 https://arxiv.org/abs/2012.01625
- less_less 3y agoI 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.
- 3y ago
- NavinF 3y agohttps://pqcrypto.org/ https://pqcrypto.org/
- bawolff 3y agoSo 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.
- wahahah 3y agoBeing able to crack present-day communications in the future is still a concern.
- its-summertime 3y agoHence https://en.wikipedia.org/wiki/Forward_secrecy 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.
- upofadown 3y agoForward 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.
- bawolff 3y agoI 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.
- survirtual 3y agoEncrypted 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.
- genr8 3y ago"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
- consp 3y agoCan those even perform shor's? I've read somewhere those are not suitable but I'm limited by a lack of actual knowledge here.
- htourweoi4324 3y agoThe 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).
- adastra22 3y agoThat 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.
- tromp 3y ago> 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#Records_for_efforts_by_quantum_computers https://en.wikipedia.org/wiki/Integer_factorization_records#...
- bob1029 3y agoI 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.
- Escapado 3y agoAbout 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.
- upofadown 3y agoRelated: https://arxiv.org/abs/1905.09749 https://arxiv.org/abs/1905.09749 | How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits