Implications of Shor's algorithm on $F_{2^m}$ elliptic curves and GHASH

Question

The security of elliptic curves depends on the difficulty of the discrete logarithm problem. Should Shor's Algorithm ever prove viable then elliptic curves would cease to offer any useful security properties, hence the need for post quantum crypto algorithms.

Most discussions of Shor's algorithm are for integers but how applicable is it for polynomials?

This is relevant because SEC2 defines a bunch of elliptic curves over $F_{2^m}$ instead of $F_P$.

I'm also curious about how Shor's Algorithm would impact GCM / GHASH, which operates in $F_{2^m}$.

Answer 1

Most discussions of Shor's algorithm are for integers but how applicable is it for polynomials?

Quite applicable; Shor's algorithm treats the group operation as a blackbox, hence it treats an even characteristic curve just like it does a prime curve. The only practical difference is the cost differential (in terms of qubits, circuit complexity and depth) between the prime curve and the even characteristic curve addition operations.

I'm also curious about how Shor's Algorithm would impact GCM / GHASH, which operates in $F_{2^m}$.

That's a different question (because GCM/GHASH has a secret symmetric key); in terms of standard CPA and CCA attacks, GCM/GHASH (correctly used) is provably secure as long as you cannot distinguish AES (or whatever underlying block cipher you're using) from a random permutation; allowing the adversary to perform Quantum operations doesn't change that (and so unless he can use his Quantum Computer to break AES, there's nothing he can do).

The one exception is if you go outside that model, and go to a Quantum Oracle model (where the attacker is allowed to request entangled queries and get entangled responses), that's different - it's known that GHASH (that is, the authentication piece in GCM) can be broken fairly easily. This does show that it is impossible for a white box GCM implementation to be quantum secure; however it is hard to come up with another realistic scenario where this attack is applicable.