ExpanderGraphs,GRH,andtheEllipticCurveDiscrete.pptVIP

Expander Graphs, GRH, and the Elliptic Curve Discrete Logarithm Stephen D. Miller Rutgers University Brief Overview 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 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. The computer 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: Pre-computer 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 against foreseen attacks. Leave no trace. Example of a difficult underlying problem: Discrete Logarithm on