![[Search]](/static/images/search.gif){kind=small}
![[A-Z Index]](/static/images/az.gif){kind=small}
![[Contact]](/static/images/contact.gif){kind=small}
![[University of Cambridge]](/static/images/identifier2.gif){kind=small}
![[Talks.cam]](/static/images/talkslogosmall.gif)
Ramarathnam Venkatesan (Microsoft Research)
Friday 16 January 2009, 12:00-13:00
Expander graphs based on GRH and some cryptographic applications
- đ¤ Speaker: Ramarathnam Venkatesan (Microsoft Research)
- đ Date & Time: Friday 16 January 2009, 12:00 - 13:00
- đ Venue: MR11
Abstract
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).
Series This talk is part of the Combinatorics Seminar series.
Included in Lists
- All CMS events
- All Talks (aka the CURE list)
- bld31
- CMS Events
- Combinatorics Seminar
- DPMMS info aggregator
- DPMMS lists
- DPMMS Lists
- DPMMS Pure Maths Seminar
- Hanchen DaDaDash
- Interested Talks
- MR11
- School of Physical Sciences
Note: Ex-directory lists are not shown.