文档介绍：Expander Graphs, GRH, and the Elliptic Curve Discrete Logarithm
Stephen D. Miller
Rutgers University
Joint work with
David Jao and Ramarathnam Venkatesan
Microsoft Research Cryptography and Anti-Piracy Group
.edu/~sdmiller
Many cryptographic applications are based on the discrete logarithm.
Important example: DLOG on elliptic curves.
Is it always equally hard? Are there “good curves” and “bad curves”?
Main result: in some situations curves have equivalent difficulty.
Mathematical content: proof/techniques use
Elliptic Curves
Expander Graphs
Modular Forms
L-functions
Generalized Riemann Hypothesis
Brief Overview
Motivating Example: Microsoft Product Key
When Windows or Microsoft office are installed, the user is required to enter a 25-digit alphanumeric antipiracy code.
This code (“key”) must be short.
puter must be able to quickly recognize whether or not this is a valid key, without giving away any clue as to how to manufacture additional valid keys.
Otherwise thieves would copy the software CDs and illegally resell them with new codes. Key=CA$H.
Future attacks will be faster. How can one keep the key short, yet still keep up with the attackers?
This requires new methods and cryptosystems. Serious mathematics involved in design.
Cryptography
Mathematical Methods to hide information.
Based on the difficulty of some underlying mathematical problem.
Well-known problems include:
puter age: guessing keys, inverting ax+b (mod n).
Factoring (RSA).
Discrete Logarithm.
Braid group conjugacy problem.
….. But a good problem is just the start – implementation matters, too!
Other factors
A good cryptosystem needs more than just a hard problem behind it.
It’s rare to reduce the cryptosystem directly to the underlying problem, for example…
Hypothetically: RSA might be easier than factoring.
Some desired attributes:
Speed of encryption and decryption.
Use of a large state space – without having to store it all.
Short “keys”(passwords).
Stability agai