International Association for Cryptologic Research

International Association
for Cryptologic Research


Worst-Case Subexponential Attacks on PRGs of Constant Degree or Constant Locality

Akın Ünal , ETH Zurich
DOI: 10.1007/978-3-031-30545-0_2 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2023
Award: Early Career Best Paper Award
Abstract: In this work, we will give new attacks on the pseudorandomness of algebraic pseudorandom number generators (PRGs) of polynomial stretch. Our algorithms apply to a broad class of PRGs and are in the case of general local PRGs faster than currently known attacks. At the same time, in contrast to most algebraic attacks, subexponential time and space bounds will be proven for our attacks without making any assumptions of the PRGs or assuming any further conjectures. Therefore, we yield in this text the first subexponential distinguishing attacks on PRGs from constant-degree polynomials and close current gaps in the subexponential cryptoanalysis of lightweight PRGs. Concretely, against PRGs $F : \mathbb{Z}_q^{n} \rightarrow \mathbb{Z}_q^{m}$ that are computed by polynomials of degree $d$ over a field $\mathbb{Z}_q$ and have a stretch of $m = n^{1+e}$ we give an attack with space and time complexities $n^{O(n^{1 - \frac{e}{d-1}})}$ and noticeable advantage $1 - {O(n^{1 - \frac{e}{d-1}}/{q})}$. If $q$ lies in $O(n^{1 - \frac{e}{d-1}})$, we give a second attack with the same space and time complexities whose advantage is at least $q^{-O(n^{1 - \frac{e}{d-1}})}$. If $F$ is of constant \emph{locality} $d$ and $q$ is constant, we construct a third attack that has a space and time complexity of $\exp(O(n^{1 - \frac{e'}{(q-1)d-1}}))$ and noticeable advantage $1-O(n^{-\frac{e'}{(q-1)d-1}})$ for every constant $e' < e$.
  title={Worst-Case Subexponential Attacks on PRGs of Constant Degree or Constant Locality},
  author={Akın Ünal},