Paper 2023/119

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

Akin Ünal, ETH Zurich
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.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
A major revision of an IACR publication in EUROCRYPT 2023
Keywords
Algebraic AttacksPRGsSubexponentialLower BoundsRandom Local Functions
Contact author(s)
akin uenal @ inf ethz ch
History
2023-03-29: revised
2023-02-01: received
See all versions
Short URL
https://ia.cr/2023/119
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/119,
      author = {Akin Ünal},
      title = {Worst-Case Subexponential Attacks on PRGs of Constant Degree or Constant Locality},
      howpublished = {Cryptology ePrint Archive, Paper 2023/119},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/119}},
      url = {https://eprint.iacr.org/2023/119}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.