University of Cambridge > > Combinatorics Seminar > Expander graphs based on GRH and some cryptographic applications

Expander graphs based on GRH and some cryptographic applications

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

  • UserRamarathnam Venkatesan (Microsoft Research)
  • ClockFriday 16 January 2009, 12:00-13:00
  • HouseMR11.

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2019, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity