BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Novak Kaluderovic (EPFL)\, Thorsten Kleinjung (EPFL)\, and Dusan K
 ostic (EPFL)
DTSTART:20200703T143000Z
DTEND:20200703T150000Z
DTSTAMP:20260423T195909Z
UID:ANTS14/21
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/ANTS14/21/">
 Cryptanalysis of the generalised Legendre pseudorandom function</a>\nby No
 vak Kaluderovic (EPFL)\, Thorsten Kleinjung (EPFL)\, and Dusan Kostic (EPF
 L) as part of Algorithmic Number Theory Symposium (ANTS XIV)\n\n\nAbstract
 \nLinear Legendre pseudorandom functions were introduced in 1988 by Damgå
 rd\, and higher degree generalisations were introduced by Russell and Shpa
 rlinski in 2004. We present new key recovery methods that improve the stat
 e of the art for both cases. For degree $r\\geq3$ we give an attack that r
 uns (after precomputation) in time $O(p^{r-3})$ for the most relevant high
  degree case\; it is based on an analysis of the actions of the group of M
 öbius transformations on degree $r$ polynomials. For $r< 3$ we give an $O
 (p^{r/2})$ attack with $O(p^{r/4})$ oracle queries. In the linear case we 
 recovered the keys for the $64$\, $74$ and $84$-bit prime Ethereum challen
 ges\, being the first to solve the $84$-bit case.\n\nThe slides used in th
 e pre-recorded video can be found <a href="https://math.mit.edu/~drew/ANTS
 XIV/CryptanalysisVideoSlides.pdf">here</a>.\n\nChairs: Marco Streng and Da
 vid Kohel\n
LOCATION:https://researchseminars.org/talk/ANTS14/21/
END:VEVENT
END:VCALENDAR