Expander graphs based on GRH and some cryptographic applications

Add to your list(s) Download to your calendar using vCal

• Ramarathnam Venkatesan (Microsoft Research)
• Friday 16 January 2009, 12:00-13:00
• MR11.

If you have a question about this talk, please contact Andrew Thomason.

CANCELLED due to illness

We present a construction of expander graphs obtained from Cayley graphs of narrow ray class groups, whose eigenvalue bounds follow from the Generalized Riemann Hypothesis. Our result implies that the Cayley graph of (Z/qZ)* with respect to small prime generators is an expander.

As another application, we show that the graph of small prime degree isogenies between ordinary elliptic curves achieves non-negligible eigenvalue separation, and explain the relationship between the expansion properties of these graphs and the security of the elliptic curve discrete logarithm problem. Finally we show that the least significant bit of $x(abP)$ is pseudo-random given $(aP,bP,P)$, using these results and a refinement of Lenstra’s result on distribution of orders of elliptic curves.

Based on works with Stephen D Miller (Rutgers) David Jao (Waterloo) and Dimitar Jetchev (UC Berkeley).

This talk is part of the Combinatorics Seminar series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• Combinatorics Seminar
• DPMMS Lists
• DPMMS Pure Maths Seminar
• DPMMS info aggregator
• DPMMS lists
• Hanchen DaDaDash
• Interested Talks
• MR11
• School of Physical Sciences
• bld31

Note that ex-directory lists are not shown.