Try our Free Online Math Solver!

Donuts and Cubic Function Fields
Overview
* Motivation
* Brief History of Public Key Crypto
* Must Go Faster
* Real vs . Imaginary Curves
* Infrastructure
* Function Fields
* Computational Stuff
* Won't You Be my iNeighbor?
* Finding Two Fundamental Units
* Examples
* Two Fundamental Units
* The Donut
Motivation
The goal of my research is to study cubic function
fields as a new setting for cryptography.
We never know if or when existing cryptosystems
are going to be broken or weakened, so
it's wise to have some uncracked ones laying
around.
Even if cubic function fields are never used or
their use is found to be insecure, we can always
take of the cryptographer's hat and put
on the computational number theorist 's hat.
There are interesting theoretical questions that
arise in studying these fields, many of which are
needed for crypto.
Crypto Needs:
* Group, efficient representation and arithmetic
* Group order with large prime divisor
* Efficient computation of the group order
* Security based on a \hard problem"
History
* RSA published (publicly) in 1977
* 129 digit challenge problem
* Estimated over 40 quadrillion years to break.
* 1991: Quadratic Sieve  subexponential time
factoring: L[1/2; 1]
* 1994: Actual time to solve the challenge : 8
months
* "The magic words are squeamish ossifrage."
* 1993: Number Field Sieve  asymptotically
much faster than QS: L[1/3, 1.92…]
* 1985: Elliptic Curve Cryptography
* ECC based on the Discrete Log Problem :
* Given two points P and Q, find k such that
kP = Q.
* Fastest known algorithm to solve it, Pollard's
Rho, runs in exponential time .
Must Go Faster
* Since the ECDLP is harder than factoring ,
key sizes for ECC are smaller than for RSA.
* Smaller keys mean faster arithmetic.
* Elliptic curves are genus 1; they are donuts.
*
* 1989: Hyperelliptic Curve Cryptography
*
* Group law is different . Look at the Jacobian.
* For a curve C of genus g over F_{q}:
*
* A large genus means a small q and small
keys!
* Genus of C is g if deg f = 2g +1 or 2g +2.
* The DLP is faster than Rho for g ≥ 4.
* Can cubic, y^{3} = f(x), curves run faster?
Real vs. Imaginary Curves
Huh?
* Consider real and imaginary number fields
* What are some differences?
Ideal class groups:
* Small (usually 1) for real fields.
* Large
for imaginary fields.
This makes the class group of an imaginary
field a good setting in which to do crypto.
Unit groups:
* Rank 0 for imaginary number fields.
* Maximal rank for real number fields.
* Degree d = r +2s, unit rank = r +s  1
* The unit group is the best distinction.
* Function fields, extensions of F_{q}(x), not Q,
can have unit rank 0, 1, ..., d 1 depending on
how the point at infinity splits.
If real fields have a tiny ideal class group, what
good are they for cryptography?
Infrastructure
* Like railroads , interstates, and airports, right?
* Nope.
* For the class group of an imaginary quadratic
field, each ideal has a unique reduced representation ,
which makes things nice.
* In a real quadratic field, the principal class
(i.e. the ideal (1) = OK) does not have a
unique reduced form.
* Shanks noticed that the reduced principal
ideals had a grouplike structure inside, a cycle
of reduced principal ideals which he called the
infrastructure.
* Arithmetic is via baby steps (like adding 1 in
F_{q}) and giant steps (multiplying two ideals).
* The infrastructure can be used to compute
the fundamental unit of OK.
Function Fields
*
* A quadratic function field adjoins y, where
y^{2} = f(x) and is thus an elliptic or hyperelliptic
function field.
* If deg(f) is even, then the function field is
real, and there is an infrastructure and fundamental
unit.
* Else, arithmetic in the ideal class group corresponds
to arithmetic in the Jacobian.
* By adjoining y where y^{3} = f(x), we have
a (purely) cubic function field.
* If q ≡ 1 mod 3, deg f = 6, f has a double
root , then the function field is real of genus 3,
so it has 2 units.
* The curve y^{3} = f(x) is a real Picard curve.
Computational Stuff
* The group order of Jacobians and such is
important to find and find quickly.
* Can search the interval of the range of Jacobians:
exponential time.
* In function fields
h = ideal class number = #Cl(K)
R = Regulator  which is based on the units.
* If
and
are the two fundamental units
and
denotes a nontrivial real embedding of
, then
* Other approaches to finding the size of the
Jacobian involve the L polynomial of the curve :
and
where p is a prime ideal in OK.
Prev  Next 