6 ms·
If I remember correctly, it takes a quantum computer with roughly 2N qubits to break N-bit RSA. So we should be ok until thousand-qubit systems are being develo
by Zaak 9y ago
If I remember correctly, it takes a quantum computer with roughly 2N qubits to break N-bit RSA. So we should be ok until thousand-qubit systems are being developed.
Increasing key lengths is a short-term workaround, but the real solution is post-quantum public key encryption, which is currently an area of active research.
- gnode 9y agoDo you know what the implications are for symmetric ciphers or [elliptic curve] Diffie-Hellman key exchange? I.e. will forward secrecy still hold up against such future quantum computing?
- Zaak 9y agoThe implication for symmetric ciphers is that key lengths will need to be doubled. 128-bit ciphers like standard AES have 64-bit security against a quantum attack. I expect to see 256-bit keys adopted widely in the not-too-distant future. I don't know off the top of my head what the implication for key exchange would be, but I know that anything that depends on the discrete logarithm problem for security is vulnerable to a quantum attack. I believe that includes all forms of Diffie-Hellman.
- sampo 9y agoWith a quantum computer and Grover's algorithm, 128-bit AES is breakable in 2^64 steps. But the quantum computer still needs to have a 128-bit quantum memory.
- dsacco 9y agoI’m not sure if you mean to be disagreeing here or simply adding color, but what you’re saying is the same as the parent comment. Grover’s algorithm allows symmetric key recovery for n bits in 2^(n/2) steps; as the parent commenter said, symmetric algorithm key sizes need to be doubled. A break in 2^64 steps is the same as 64-bit security, so changing the key size to 256-bit will offer 128 bits of security.
- sampo 9y agoJust wanted to clarify that in this case, 64-bit quantum computer is not enough to break said 64-bit security, still need 128 bits of memory.
- jd007 9y agoSIDH (https://en.wikipedia.org/wiki/Supersingular_isogeny_key_exchange https://en.wikipedia.org/wiki/Supersingular_isogeny_key_exch...) is one of the few popular post-quantum variants of DH key exchange, and it supports forward secrecy as well.
- the8472 9y agoOne nice property of ECC pubkeys is that they easily fit into UDP packets, URIs and other very compact data structures. Currently all post-quantum schemes have fairly bulky pubkeys.
- Zaak 9y agoSIDH keys are 330 bytes long when compression is used, so they too will fit nicely into network packets.