4 ms·

"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

by _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.
        Dylan16807 6y ago
        > Considering there's overhead for the rest of the application, there's no way to use such keys on such a device. If you wait a small number of years you'll be able to get twice the ram at the same price. So "it would barely fit in ram if nothing else is running" doesn't seem like a significant barrier to me. > 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. Your trusted proxy would be using one of the secure multi-megabyte keys, of course. Am I missing something about that arrangement? If signatures would also be enormous then we have a more significant problem to deal with than key size.
        SAI_Peregrinus 6y ago
        The trusted proxy in your scheme exists to avoid needing to deal with the multi-megabyte keys on a device with only a few kilobytes of RAM. It CAN'T use such keys to secure the connection with the embedded device. If it could, it wouldn't be needed.

by _hl_ 6y ago

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.
      - Dylan16807 6y ago
        > Considering there's overhead for the rest of the application, there's no way to use such keys on such a device. If you wait a small number of years you'll be able to get twice the ram at the same price. So "it would barely fit in ram if nothing else is running" doesn't seem like a significant barrier to me. > 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. Your trusted proxy would be using one of the secure multi-megabyte keys, of course. Am I missing something about that arrangement? If signatures would also be enormous then we have a more significant problem to deal with than key size.
        SAI_Peregrinus 6y ago
        The trusted proxy in your scheme exists to avoid needing to deal with the multi-megabyte keys on a device with only a few kilobytes of RAM. It CAN'T use such keys to secure the connection with the embedded device. If it could, it wouldn't be needed.