Geometria Curves over Finite Fields and Cryptography Gerhard Frey
13-12-2018 - 14:30
Largo San Leonardo Murialdo,1 - Pal.C - Aula 211
In this lecture we shall explain in more detail the topics mentioned in the colloqui-
um talk, in particular we shall discuss how curves over finite fields can be applied
to public key cryptography.
After recalling the principles of a Diffie-Hellman key exchange scheme we shall dis-
cuss algorithms for addition in divisor class groups Pic^0(C), where C is a projective
curve over a finite field Fq. Of special interest are elliptic and hyperelliptic cur-
ves, and as consequence of the results one can try to use their Picard groups for
cryptographic schemes based on discrete logarithms. For this, we have to test the
hardness of the computation of the discrete logarithm, and it turns out that a ve-
ry efficient attack based on index-calculus eliminates all curves of genus ≤ 4 and
non-hyperelliptic curves of genus 3. Going further and using an explicit isogeny of
Jacobians of hyperelliptic curves of genus 3 we have to exclude “many” hyperelliptic
curves of genus 3.
The good news is that the remaining curves (including nearly all curves of genus
1 and 2) are till today “exponentially secure” against all known attacks based on
conventional computer algorithms, and since one can solve the point counting task
for these curves in cryptographically relevant ranges we have a rather satisfying
situation of cryptography based on elliptic and hyperelliptic curves–as long as we
restrict the algorithms to classical bit-operations. But the possibility of the existence of quantum computers in a not too far future forces to look for alternatives
since the discrete logarithm will have only polynomial complexity (key word “Shor’s
algorithm”).
This opens a new and very interesting area of research. Amongst other proposals
the idea of using isogeny graphs of elliptic curves and the hardness to compute
explicitly isogenies between elliptic curves (known to be isogenous) leads to key
exchange schemes away from discrete logarithms.
We shall present such schemes using ordinary elliptic curves (Couveignes-Stolbunov
et.al) (rather slow) and supersingular elliptic curves over prime fields Fp (W. Ca-
stryck et. al) (very fast), which are both of subexponential security. Going to super-
singular curves over Fp2 we explain the scheme of De Feo, Jao et.al which is not so
fast as Castryck’s scheme but has, at our present knowledge, exponential security.
org: VIVIANI Filippo
|
