Paper 2023/119

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

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, while 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$ is large. If $F$ is of constant locality $d$ and $q$ is constant, we construct a second attack that has a space and time complexity of $n^{O(\log(n)^{\frac{1}{(q-1)d-1}} \cdot n^{1 - \frac{e}{(q-1)d-1}})}$ and noticeable advantage $1-O((\log(n)/n^e)^{\frac{1}{(q-1)d-1}})$.

Note: Full Version. 29.03.2023: In the previous version of this text, I wrongfully claimed to give faster baseline algorithms for random local functions. As has been pointed out to me, the fastest known distinguishing attacks for poly-stretch local PRGs are given by shrinking sets, whose runtime complexities are smaller than the time complexities of the attack I give in this text against PRGs of constant locality and constant modulus. Further, I added a discussion of Lior Zichron's master thesis to the related work of this text. Zichron introduces in his thesis algorithms for finding annihilating polynomials of polynomial PRGs, which are very close to the algorithms in this text.