4 ms·

The argument laid out by Cohn also works against elliptic curves: the discrete log is not NP-hard either, and if anything even less people have tried to attack

by pbsd 10y ago

The argument laid out by Cohn also works against elliptic curves: the discrete log is not NP-hard either, and if anything even less people have tried to attack it than factorization (according to Cohn, subexponential factorization only happened in the 1970s, after centuries of trying; elliptic curves are not that old). Some lattice problems, on the other hand, are known to be NP-hard. What does this tell us about their worthiness as cryptographic problems? Not a lot.

tptacek 10y ago
Which do you think is going to happen first: progress against RSA that plausibly threatens 2048 (or 3072) bit keys, or progress against ECC that plausibly threatens Curve25519?
- pbsd 10y ago
  I think progress against RSA is more likely, unless Shor happens first and kills everyone. I also hope to see a O(n^2) matrix multiplication algorithm within my lifetime. My point was not to defend RSA, but to point out that Cohn's argument could be reused for most of our current primitives.
  - tptacek 10y ago
    I figured that'd be your answer. I feel like the idea that you'd use ECC out of concern for advances in factoring or conventional discrete log isn't my own, but I'm not careful enough with this stuff to know the best thing to cite. As always, I comment on crypto stuff principally to see if I can goad you into correcting me. :)
    - pbsd 10y ago
      Well, I suppose you could cite Miller and Koblitz on that (mostly Miller). This was the mid-80s, when progress in index-calculus algorithms was in full force. So they introduce elliptic curves, and basically say 'look, this problem seems to be immune to these classes of algorithms, which seem to be getting better all the time, so let's use it instead'. With some important caveats discovered in the meantime, they have been right so far.
- asd999101 10y ago
  I think progress against ECC happens first. Because quantum computers exist. I'm not sure how large a problem they can work on yet. ECC is used with smaller bit lengths which makes it easier to get a sufficient quantum computer. Of course I may have a fundamental misunderstanding here, and if so, I'd love to be enlightened.
  - tptacek 10y ago
    Quantum computing confuses every thread about RSA and ECC. Shor threatens RSA and ECC. Neither RSA nor ECC are considered post-quantum schemes. If quantum computing is really your threat model, you want to be doing what Google did: run both a pre-quantum and a post-quantum key exchange and mix the results with a KDF. Which post-quantum approach you choose, I don't care. (I'm a quantum computing skeptic). What you do not want to do is build a cryptosystem using solely a post-quantum key exchange algorithm, or, even worse, try to build a cryptosystem without any asymmetric key exchange at all. In both cases, implementation errors --- some of which, in the latter case, are probably inevitable --- will doom your system immediately.
- deleted 10y ago
  [deleted]

by pbsd 10y ago

tptacek 10y ago

Which do you think is going to happen first: progress against RSA that plausibly threatens 2048 (or 3072) bit keys, or progress against ECC that plausibly threatens Curve25519?

pbsd 10y ago
I think progress against RSA is more likely, unless Shor happens first and kills everyone. I also hope to see a O(n^2) matrix multiplication algorithm within my lifetime. My point was not to defend RSA, but to point out that Cohn's argument could be reused for most of our current primitives.
- tptacek 10y ago
  I figured that'd be your answer. I feel like the idea that you'd use ECC out of concern for advances in factoring or conventional discrete log isn't my own, but I'm not careful enough with this stuff to know the best thing to cite. As always, I comment on crypto stuff principally to see if I can goad you into correcting me. :)
  - pbsd 10y ago
    Well, I suppose you could cite Miller and Koblitz on that (mostly Miller). This was the mid-80s, when progress in index-calculus algorithms was in full force. So they introduce elliptic curves, and basically say 'look, this problem seems to be immune to these classes of algorithms, which seem to be getting better all the time, so let's use it instead'. With some important caveats discovered in the meantime, they have been right so far.
asd999101 10y ago
I think progress against ECC happens first. Because quantum computers exist. I'm not sure how large a problem they can work on yet. ECC is used with smaller bit lengths which makes it easier to get a sufficient quantum computer. Of course I may have a fundamental misunderstanding here, and if so, I'd love to be enlightened.
- tptacek 10y ago
  Quantum computing confuses every thread about RSA and ECC. Shor threatens RSA and ECC. Neither RSA nor ECC are considered post-quantum schemes. If quantum computing is really your threat model, you want to be doing what Google did: run both a pre-quantum and a post-quantum key exchange and mix the results with a KDF. Which post-quantum approach you choose, I don't care. (I'm a quantum computing skeptic). What you do not want to do is build a cryptosystem using solely a post-quantum key exchange algorithm, or, even worse, try to build a cryptosystem without any asymmetric key exchange at all. In both cases, implementation errors --- some of which, in the latter case, are probably inevitable --- will doom your system immediately.
deleted 10y ago
[deleted]