5 ms·

cperciva vindicated? edit: For context, Colin has maintained a conservative position regarding ECC for quite some time now.

tptacek 11y ago
No. The crypto Colin advocates for also falls to QC.
- sdevlin 11y ago
  The post talks about hypothetical improvements in non-QC approaches to the ECDLP.
  - tptacek 11y ago
    Didn't it read dismissive about that to you?
    - sdevlin 11y ago
      The paper or the post? I think the paper is maybe slightly dismissive, closer to neutral: "it is conceivable the NSA has found ...". The post seems more enthusiastic: "the most intriguing hypotheses in the paper" "Beginning with the smallest of the standard curves, P-256, which would now provide less than the required 128-bit security. Did I mention that as part of the recent announcement, NSA also deprecated P-256?" He backtracks a little in the following paragraph ("Of course, there’s no reason to believe ..."), but I think the conspiratorial tone is pretty well established by then. It's also just the fact that he spends about a third of the post talking about this explanation without really covering any of the others. If I hadn't read the paper, I'd come away with the impression that this is the main theory they put forth.
- vox_mollis 11y ago
  The article discusses the hypothesis that the NSA has broken ECC classically, and is lying to us. But conspiracy theories aside, does 3072 bit RSA fall along with 256 bit ECC with the same quantum difficulty? Don't you have to have coherence of substantially more qubits in the former case?
  - sdevlin 11y ago
    The paper discusses the quantum case: > However, it will require major advances in physics and engineering before quantum computing can scale significantly. When that happens, of course P-256 and P-384 will fall first. But, as the head of cybersecurity research at a major corporation put it, “after that it’s just a matter of money” before RSA-3072 is broken. At the point when P-384 is broken it would be unwise to use either ECC or RSA. It is not likely that the gap between quantum cryptanalysis of a 384-bit key and a 3072-bit key will be great enough to serve as a basis for a cryptographic strategy.
    - vox_mollis 11y ago
      Is it really just a matter of money, though? My understanding is that the coherence window (timewise) decreases exponentially as you add more qubits. "Just a matter of money" implies linear scalability.
  - pbsd 11y ago
    Loosely speaking, you need n + epsilon qubits and 4n^3 operations to break RSA-n, whereas you need ~6n qubits and 360n^3 operations to break ECC-n. For n = 256, you need around 1536 qubits, whereas you need at least 3072 for RSA-3072. This suggests a criterion to reject P-256: it needs fewer than 2048 qubits to break. P-384 is above this threshold, at around 2.5k qubits. Hey, it's as good speculation as any.
    - api 11y ago
      Does this mean that barring a quantum-hard alternative we could get effectively quantum-hard crypto by using crazy key sizes like RSA-131072 or ECC-4096?
      - pbsd 11y ago
        Yes, though it would be quite impractical. See for example http://cr.yp.to/talks/2010.05.28/slides.pdf http://cr.yp.to/talks/2010.05.28/slides.pdf

tptacek 11y ago

No. The crypto Colin advocates for also falls to QC.

sdevlin 11y ago
The post talks about hypothetical improvements in non-QC approaches to the ECDLP.
- tptacek 11y ago
  Didn't it read dismissive about that to you?
  - sdevlin 11y ago
    The paper or the post? I think the paper is maybe slightly dismissive, closer to neutral: "it is conceivable the NSA has found ...". The post seems more enthusiastic: "the most intriguing hypotheses in the paper" "Beginning with the smallest of the standard curves, P-256, which would now provide less than the required 128-bit security. Did I mention that as part of the recent announcement, NSA also deprecated P-256?" He backtracks a little in the following paragraph ("Of course, there’s no reason to believe ..."), but I think the conspiratorial tone is pretty well established by then. It's also just the fact that he spends about a third of the post talking about this explanation without really covering any of the others. If I hadn't read the paper, I'd come away with the impression that this is the main theory they put forth.
vox_mollis 11y ago
The article discusses the hypothesis that the NSA has broken ECC classically, and is lying to us. But conspiracy theories aside, does 3072 bit RSA fall along with 256 bit ECC with the same quantum difficulty? Don't you have to have coherence of substantially more qubits in the former case?
- sdevlin 11y ago
  The paper discusses the quantum case: > However, it will require major advances in physics and engineering before quantum computing can scale significantly. When that happens, of course P-256 and P-384 will fall first. But, as the head of cybersecurity research at a major corporation put it, “after that it’s just a matter of money” before RSA-3072 is broken. At the point when P-384 is broken it would be unwise to use either ECC or RSA. It is not likely that the gap between quantum cryptanalysis of a 384-bit key and a 3072-bit key will be great enough to serve as a basis for a cryptographic strategy.
  - vox_mollis 11y ago
    Is it really just a matter of money, though? My understanding is that the coherence window (timewise) decreases exponentially as you add more qubits. "Just a matter of money" implies linear scalability.
- pbsd 11y ago
  Loosely speaking, you need n + epsilon qubits and 4n^3 operations to break RSA-n, whereas you need ~6n qubits and 360n^3 operations to break ECC-n. For n = 256, you need around 1536 qubits, whereas you need at least 3072 for RSA-3072. This suggests a criterion to reject P-256: it needs fewer than 2048 qubits to break. P-384 is above this threshold, at around 2.5k qubits. Hey, it's as good speculation as any.
  - api 11y ago
    Does this mean that barring a quantum-hard alternative we could get effectively quantum-hard crypto by using crazy key sizes like RSA-131072 or ECC-4096?
    - pbsd 11y ago
      Yes, though it would be quite impractical. See for example http://cr.yp.to/talks/2010.05.28/slides.pdf http://cr.yp.to/talks/2010.05.28/slides.pdf