3 ms·

Those quantum computers can't execute Shor's algorithm, which is required to attack RSA. AFAIK the best relevant factoring result is still 21=3*7 from 2012. Th

Those quantum computers can't execute Shor's algorithm, which is required to attack RSA. AFAIK the best relevant factoring result is still 21=3*7 from 2012. There are claims of bigger factored numbers, but they exploited special cases (e.g. factors differing by only two bits) and have no hope of being extended to attack cryptography. https://crypto.stackexchange.com/questions/59795/largest-integer-factored-by-shors-algorithm https://crypto.stackexchange.com/questions/59795/largest-int... A 2019 paper manged to factor 21 on a 16 qubit ibmqx5, but failed to go up to 35: > the algorithm fails to factor N=35. This is due to the cumulative errors coming from the increasing number of two-qubits gates necessary to implement the more complex MEF needed for this case https://arxiv.org/abs/1903.00768 https://arxiv.org/abs/1903.00768

graderjs 6y ago
Jennifer and Peter Shor wrote a limerick that seems relevant: If computers that you build are quantum, Then spies of all factions will want 'em. Our codes will all fail, And they'll read our email, Till we've crypto that's quantum, and daunt 'em. And Volker Strassen responded at a conference: To read our E-mail, how mean of the spies and their quantum machine; Be comforted though, they do not yet know how to factorize twelve or fifteen. Source: http://www-math.mit.edu/~shor/notapoet.html http://www-math.mit.edu/~shor/notapoet.html
- CodesInChaos 6y ago
  > Till we've crypto that's quantum, and daunt 'em. Luckily there are asymmetric algorithms which are are secure against quantum computers, so we don't have to resort to quantum-key-exchanges.
  - _hl_ 6y ago
    "Secure against quantum" doesn't really mean much because too little is known to make that claim confidently. AFAIK the term generally refers to algorithms that don't rely on factoring being hard, but instead make some different hardness assumptions that we currently don't have classical or quantum algorithms for.
    - CodesInChaos 6y ago
      For practically all computationally secure crypto we use "secure" for "no known attacks faster than we'd like". QCs just extend the set of efficient algorithms.
      - _hl_ 6y ago
        Indeed, but there is a much longer history of people trying and failing to break the schemes, and we have come to understand the hardness assumptions in classical crypto as probably quite reasonable.
        SAI_Peregrinus 6y ago
        There's a similarly long history of people trying and failing to break code-based schemes like Niederreiter and McEliece with binary Goppa codes. Unlike lattice-based schemes they're considered quite secure, but their key sizes are enormous (like, hundreds of KiB to several MiB in size). So they're impractical for embedded security, or any situation where key transfer bandwidth is an issue (IoT, metered data plans, etc).
        Dylan16807 6y ago
        Does IoT need to transfer keys? When it comes to metered data, a few megabytes to access a new site sounds like normal internet to me. And you could use a trusted proxy/VPN; there are present-day apps that more or less fill that niche already.
        SAI_Peregrinus 6y ago
        Transfer is one issue, processing is another. If you're running an IoT device on an STM32F423ZH (chosen because my employer has a cell-enabled IoT device on that MCU) you've got 320k of total RAM. Considering there's overhead for the rest of the application, there's no way to use such keys on such a device. A trusted proxy works if ECC is secure (no quantum computers), but if quantum attacks are practical then there would be no way to verify that the trusted proxy is actually what you think it is.
DebtDeflation 6y ago
>There are claims of bigger factored numbers, but they exploited special cases Also, my understanding is that almost all of these factorizations utilize a "compiled" version of Shor's algorithm. Meaning that you need to know the factors in advance. So it's essentially "confirming" rather than "finding" the factors.
- CodesInChaos 6y ago
  AFAIK factoring 21 is "compiled" Shor, so even that result simplifies the problem a bit. According the first link in my post, the numbers bigger than 21 were chosen to have specific mathematical properties and attacked with algorithms even less realistic that compiled Shor.

graderjs 6y ago

Jennifer and Peter Shor wrote a limerick that seems relevant: If computers that you build are quantum, Then spies of all factions will want 'em. Our codes will all fail, And they'll read our email, Till we've crypto that's quantum, and daunt 'em. And Volker Strassen responded at a conference: To read our E-mail, how mean of the spies and their quantum machine; Be comforted though, they do not yet know how to factorize twelve or fifteen. Source: http://www-math.mit.edu/~shor/notapoet.html http://www-math.mit.edu/~shor/notapoet.html

CodesInChaos 6y ago
> Till we've crypto that's quantum, and daunt 'em. Luckily there are asymmetric algorithms which are are secure against quantum computers, so we don't have to resort to quantum-key-exchanges.
- _hl_ 6y ago
  "Secure against quantum" doesn't really mean much because too little is known to make that claim confidently. AFAIK the term generally refers to algorithms that don't rely on factoring being hard, but instead make some different hardness assumptions that we currently don't have classical or quantum algorithms for.
  - CodesInChaos 6y ago
    For practically all computationally secure crypto we use "secure" for "no known attacks faster than we'd like". QCs just extend the set of efficient algorithms.
    - _hl_ 6y ago
      Indeed, but there is a much longer history of people trying and failing to break the schemes, and we have come to understand the hardness assumptions in classical crypto as probably quite reasonable.
      - SAI_Peregrinus 6y ago
        There's a similarly long history of people trying and failing to break code-based schemes like Niederreiter and McEliece with binary Goppa codes. Unlike lattice-based schemes they're considered quite secure, but their key sizes are enormous (like, hundreds of KiB to several MiB in size). So they're impractical for embedded security, or any situation where key transfer bandwidth is an issue (IoT, metered data plans, etc).
        Dylan16807 6y ago
        Does IoT need to transfer keys? When it comes to metered data, a few megabytes to access a new site sounds like normal internet to me. And you could use a trusted proxy/VPN; there are present-day apps that more or less fill that niche already.
        SAI_Peregrinus 6y ago
        Transfer is one issue, processing is another. If you're running an IoT device on an STM32F423ZH (chosen because my employer has a cell-enabled IoT device on that MCU) you've got 320k of total RAM. Considering there's overhead for the rest of the application, there's no way to use such keys on such a device. A trusted proxy works if ECC is secure (no quantum computers), but if quantum attacks are practical then there would be no way to verify that the trusted proxy is actually what you think it is.

DebtDeflation 6y ago

>There are claims of bigger factored numbers, but they exploited special cases Also, my understanding is that almost all of these factorizations utilize a "compiled" version of Shor's algorithm. Meaning that you need to know the factors in advance. So it's essentially "confirming" rather than "finding" the factors.

CodesInChaos 6y ago
AFAIK factoring 21 is "compiled" Shor, so even that result simplifies the problem a bit. According the first link in my post, the numbers bigger than 21 were chosen to have specific mathematical properties and attacked with algorithms even less realistic that compiled Shor.