Hacker News Reader

Comment by tptacek | Hacker News Reader

A reason, and not the best one, to stop using RSA and conventional DH and switch to elliptic curves.

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.

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?

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.

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.

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.

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. :)

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.

Unfortunately, the growth of elliptic curve use has bumped up against the fact of continued progress in the research on quantum computing, necessitating a re-evaluation of our cryptographic strategy. [1]

Even the NSA is wary of elliptic curve public key crypto; isn't ECC significantly more vulnerable to Shor's algorithm?

[1] https://www.nsa.gov/ia/programs/suiteb_cryptography/index.sh...

edit: formatting, spelling

I'm not sure why I'm meant to care about NSA's recommendations.

Meanwhile: everything you can reasonably use today is broken in post-quantum world.

By everything you mean every public key scheme? Aren't symmetric crypto schemes based on strong shared secrets secure from quantum computers?

With Optalysys and D-Wave, I expect quantum computing to become mainstream within the next ten years.

Every real-world cryptosystem in current use, possibly excepting some experimental pq systems like the RingLWE that Google's playing with.

Symmetric encryption is weakened; namely, a quantum computer can search through a space of size 2n in time 2n/2. This means that a 128-bit AES key would be demoted back to the strength of a 64-bit key ...

[1] http://security.stackexchange.com/questions/48022/what-kinds...

I'm really not interested in how well PSK AES schemes fare post-quantum, because PSK isn't a realistic solution to any of the problems we use cryptography to address.

I suggested, upthread, not using RSA (which depends on the hardness of factoring) and using ECC instead. How AES does post-quantum is not responsive to that advice.

You suggested ECC over RSA, implying that ECC offers greater security than RSA in the context of easy prime factorization. ECC's security relies on the hardness of the discrete logarithm. Yet, both prime factorization and the discrete logarithm are both special cases of the hidden subgroup problem over an Abelian group. In short, cracking RSA means cracking ECC, too.

Am I wrong? Were you just joking?

If I understand your argument properly, then I believe you to be wrong about the idea that tenably factoring 1024 or 2048 bit moduli implies a solution to the elliptic curve discrete modulus problem, yes.

@tptacek

> I believe you to be wrong about the idea that tenably factoring 1024 or 2048 bit moduli implies a solution to the elliptic curve discrete modulus problem

Probably. This mathy stuff is way over my head. I'm just repeating what I read in Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer [1] published by Peter W. Shor on behalf of AT&T Research in 1995. Supposedly his proof is valid, predicated on the existence of quantum computers. Quantum computers actually exist [insert epistemological joke here].

[1] https://arxiv.org/abs/quant-ph/9508027v2

You are talking about quantum attacks, whereas tptacek is talking about classical attacks.

So we'll take a performance hit, but it's fairly straightforward (relatively, very relatively) to extend the key sizes for symmetric crypto.

The lack of any usable asymmetric algorithms is a much greater concern.

Reply on news.ycombinator.com