Vol. 4, No. 1, 2020

Download this article
Download this article For screen
For printing
Recent Volumes
4: ANTS XIV
3: Hillman: Poincaré Duality
2: ANTS XIII
1: ANTS X
The Open Book Series
All Volumes
 
About the Series
Ethics Statement
Purchase Printed Copies
Author Index
 
MSP Books and Monographs
Other MSP Publications
Cryptanalysis of the generalised Legendre pseudorandom function

Novak Kaluđerović, Thorsten Kleinjung and Dušan Kostić

Vol. 4 (2020), No. 1, 267–282
Abstract

Linear Legendre pseudorandom functions were introduced in 1988 by Damgård, and higher degree generalisations were introduced by Russell and Shparlinski in 2004. We present new key recovery methods that improve the state of the art for both cases. For degree r 3 we give an attack that runs in time O(pr3) after O(p3) precomputation for the most relevant high degree case; it is based on the action of the group of Möbius transformations on degree r polynomials. For r < 3 we give an O(pr2) attack with O(pr4) oracle queries. In the linear case we recovered the keys for the 64, 74 and 84-bit prime Ethereum challenges, being the first to solve the 84-bit case.

Keywords
Legendre symbol, Legendre PRF, cryptanalysis, group action, pseudorandom
Mathematical Subject Classification 2010
Primary: 11T71
Milestones
Received: 27 February 2020
Revised: 31 July 2020
Accepted: 22 August 2020
Published: 29 December 2020
Authors
Novak Kaluđerović
Laboratory for cryptologic algorithms
École Polytechnique Fédérale de Lausanne
Lausanne
Switzerland
Thorsten Kleinjung
Laboratory for cryptologic algorithms
École Polytechnique Fédérale de Lausanne
Lausanne
Switzerland
Dušan Kostić
Laboratory for cryptologic algorithms
École Polytechnique Fédérale de Lausanne
Lausanne
Switzerland