3 ms·

None that can reliably factor numbers bigger than 21. https://en.wikipedia.org/wiki/Integer_factorization_records#Records_for_efforts_by_quantum_computers http

by tromp 4y ago

None that can reliably factor numbers bigger than 21. https://en.wikipedia.org/wiki/Integer_factorization_records#Records_for_efforts_by_quantum_computers https://en.wikipedia.org/wiki/Integer_factorization_records#...

kadoban 4y ago
That we know of. Machines that can would quickly become important to national security though.
- api 4y ago
  Not for long: https://csrc.nist.gov/Projects/post-quantum-cryptography https://csrc.nist.gov/Projects/post-quantum-cryptography The cryptographic implications of QC are absurdly exaggerated. QC has no practical impact on symmetric (AES, ChaCha) or hash (SHA2, SHA3, Blake) algorithms. Impact is isolated to number-theoretic asymmetric ciphers of certain types (DH, ECDH, ECDSA, EDDSA, etc.) and even there practical attacks would require very large, fast, low-noise quantum computers. The link I posted above is to a project to create the first NIST-certified asymmetric algorithms believed to not be vulnerable to quantum attack, rendering the whole thing pretty much moot.
  - pseudo0 4y ago
    Yeah, the hype has been extremely excessive. Putting some investment into quantum-resistant public key cryptography now is a reasonable hedge against the possibility of an surprise breakthrough in the next 10-30 years, but that should be about all we need to future-proof things. Unfortunately "quantum" is still a hot buzzword for managers and non-technical leadership, so it will be diverting resources and attention for the foreseeable future.
  - kadoban 4y ago
    > The cryptographic implications of QC are absurdly exaggerated. Every(?) current TLS session is vulnerable. _Many many_ auth sessions of other types are vulnerable. At least petabytes of stored sessions can be decoded (though not all). It's hard to say how it's exaggerated at all. It's pretty much the device from Sneakers, but real. That it won't break every possible thing for all time is true, but it's still about as huge as any practical thing can be.
  - tromp 4y ago
    > QC has no practical impact on symmetric or hash algorithms It would require a doubling of key lengths to maintain security against quantum Grover search attacks. > to create the first NIST-certified asymmetric algorithms believed to not be vulnerable to quantum attack That will likely lead to much more than a doubling of key sizes; perhaps two orders of magnitude bigger. It will severely impact resource constrained cryptographic devices such as credit card chips.
    - api 4y ago
      > It would require a doubling of key lengths to maintain security against quantum Grover search attacks. Grover could in theory reduce a 256-bit cipher like AES-256 or ChaCha to a 128-bit cipher. 128 bits is still far beyond what can be brute forced with any sane or practical amount of resources or time. It would mean 128-bit keys would be unsafe, but 256-bit or higher has been recommended for years anyway for reasons beyond QC like birthday attacks. Also keep in mind that this is a theoretical (as in big-O notation) speedup. Real world performance would depend a ton on the speed of the quantum computer. If a QC running Grover's algorithm isn't at least as fast as e.g. a conventional CPU then it might not be much faster in practice than a custom ASIC brute forcing a full strength key. That would make it pretty much an academic demo, not even useful in practice against 128-bit keys.
dspillett 4y ago
How reliably can they factor large numbers? Once false positive and complete failure rates are low enough, using one of them to do most of the legwork with traditional electronics to check the result and rerun as needed becomes a potentially useful combination.
upofadown 4y ago
... and without having the answer baked in to the implementation...
baby 4y ago
I think even the factorization of 21 was somewhat cheating no? It seems like we’re really a long way off being able to use a QC for anything practical, if ever. And that’s not even talking about cracking crypto.
- tromp 4y ago
  I agree that a proper demonstration should be of factoring any product of an m-bit prime by an n-bit prime. So if it only worked for 3*7 and not (with the exact same setup) for 3*5 then it shouldn't count. It's sad that no-one has demonstrated a factorization of 4+4 bits (which should include factorizing 55,65,77,91, and 143). That would be an important milestone I think.
  - tengwar2 4y ago
    That's a possible demonstration, but bear in mind that they are also used for more analogue problems such as predicting chemical bond angles, where there is no discrete pass/fail, but rather a measure of how close they got to reality.
    - tromp 4y ago
      True; but those other useful applications of quantum computers are much messier to define and qualify, so factoring is still the ideal application for setting a milestone to be achieved.

by tromp 4y ago

kadoban 4y ago

That we know of. Machines that can would quickly become important to national security though.

api 4y ago
Not for long: https://csrc.nist.gov/Projects/post-quantum-cryptography https://csrc.nist.gov/Projects/post-quantum-cryptography The cryptographic implications of QC are absurdly exaggerated. QC has no practical impact on symmetric (AES, ChaCha) or hash (SHA2, SHA3, Blake) algorithms. Impact is isolated to number-theoretic asymmetric ciphers of certain types (DH, ECDH, ECDSA, EDDSA, etc.) and even there practical attacks would require very large, fast, low-noise quantum computers. The link I posted above is to a project to create the first NIST-certified asymmetric algorithms believed to not be vulnerable to quantum attack, rendering the whole thing pretty much moot.
- pseudo0 4y ago
  Yeah, the hype has been extremely excessive. Putting some investment into quantum-resistant public key cryptography now is a reasonable hedge against the possibility of an surprise breakthrough in the next 10-30 years, but that should be about all we need to future-proof things. Unfortunately "quantum" is still a hot buzzword for managers and non-technical leadership, so it will be diverting resources and attention for the foreseeable future.
- kadoban 4y ago
  > The cryptographic implications of QC are absurdly exaggerated. Every(?) current TLS session is vulnerable. _Many many_ auth sessions of other types are vulnerable. At least petabytes of stored sessions can be decoded (though not all). It's hard to say how it's exaggerated at all. It's pretty much the device from Sneakers, but real. That it won't break every possible thing for all time is true, but it's still about as huge as any practical thing can be.
- tromp 4y ago
  > QC has no practical impact on symmetric or hash algorithms It would require a doubling of key lengths to maintain security against quantum Grover search attacks. > to create the first NIST-certified asymmetric algorithms believed to not be vulnerable to quantum attack That will likely lead to much more than a doubling of key sizes; perhaps two orders of magnitude bigger. It will severely impact resource constrained cryptographic devices such as credit card chips.
  - api 4y ago
    > It would require a doubling of key lengths to maintain security against quantum Grover search attacks. Grover could in theory reduce a 256-bit cipher like AES-256 or ChaCha to a 128-bit cipher. 128 bits is still far beyond what can be brute forced with any sane or practical amount of resources or time. It would mean 128-bit keys would be unsafe, but 256-bit or higher has been recommended for years anyway for reasons beyond QC like birthday attacks. Also keep in mind that this is a theoretical (as in big-O notation) speedup. Real world performance would depend a ton on the speed of the quantum computer. If a QC running Grover's algorithm isn't at least as fast as e.g. a conventional CPU then it might not be much faster in practice than a custom ASIC brute forcing a full strength key. That would make it pretty much an academic demo, not even useful in practice against 128-bit keys.

dspillett 4y ago

How reliably can they factor large numbers? Once false positive and complete failure rates are low enough, using one of them to do most of the legwork with traditional electronics to check the result and rerun as needed becomes a potentially useful combination.

upofadown 4y ago

... and without having the answer baked in to the implementation...

baby 4y ago

I think even the factorization of 21 was somewhat cheating no? It seems like we’re really a long way off being able to use a QC for anything practical, if ever. And that’s not even talking about cracking crypto.

tromp 4y ago
I agree that a proper demonstration should be of factoring any product of an m-bit prime by an n-bit prime. So if it only worked for 3*7 and not (with the exact same setup) for 3*5 then it shouldn't count. It's sad that no-one has demonstrated a factorization of 4+4 bits (which should include factorizing 55,65,77,91, and 143). That would be an important milestone I think.
- tengwar2 4y ago
  That's a possible demonstration, but bear in mind that they are also used for more analogue problems such as predicting chemical bond angles, where there is no discrete pass/fail, but rather a measure of how close they got to reality.
  - tromp 4y ago
    True; but those other useful applications of quantum computers are much messier to define and qualify, so factoring is still the ideal application for setting a milestone to be achieved.