BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Expander graphs based on GRH and some cryptographic applications -
  Ramarathnam Venkatesan (Microsoft Research)
DTSTART:20090116T120000Z
DTEND:20090116T130000Z
UID:TALK16348@talks.cam.ac.uk
CONTACT:Andrew Thomason
DESCRIPTION:CANCELLED due to illness\n\nWe present a construction of expan
 der graphs obtained from Cayley graphs of narrow ray class groups\, whose 
 eigenvalue bounds follow from the Generalized Riemann Hypothesis. Our resu
 lt implies that the Cayley graph of (Z/qZ)* with respect to small prime ge
 nerators is an expander.\n\nAs another application\, we show that the grap
 h of small prime degree isogenies between ordinary elliptic curves achieve
 s non-negligible eigenvalue separation\, and explain the relationship betw
 een the expansion properties of these graphs and the security of the ellip
 tic curve discrete logarithm problem.  Finally we show that the least sign
 ificant bit of $x(abP)$  is  pseudo-random given $(aP\,bP\,P)$\, using the
 se results and a refinement of Lenstra's result on distribution of orders 
 of elliptic curves.\n\nBased on works with Stephen D Miller (Rutgers) Davi
 d Jao (Waterloo) and Dimitar Jetchev (UC Berkeley).\n
LOCATION:MR11
END:VEVENT
END:VCALENDAR