Paper 2023/550

New Baselines for Local Pseudorandom Number Generators by Field Extensions

Akin Ünal, ETH Zurich
Abstract

We will revisit recent techniques and results on the cryptoanalysis of local pseudorandom number generators (PRGs). By doing so, we will achieve a new attack on PRGs whose time complexity only depends on the algebraic degree of the PRG. Concretely, for PRGs $F : \{0,1\}^n\rightarrow \{0,1\}^{n^{1+e}}$, we will give an algebraic algorithm that distinguishes between random points and image points of $F$, whose time complexity is bounded by \[\exp(O(\log(n)^{\deg F /(\deg F - 1)} \cdot n^{1-e/(\deg F -1)} ))\] and whose advantage is at least $1 - o(1)$ in the worst case. To the best of the author's knowledge, this attack outperforms current attacks on the pseudorandomness of local random functions with guaranteed noticeable advantage and gives a new baseline algorithm for local PRGs. Furthermore, this is the first subexponential attack that is applicable to polynomial PRGs of constant degree over fields of any size with a guaranteed noticeable advantage. We will extend this distinguishing attack further to achieve a search algorithm that can invert a uniformly random constant-degree map $F : \{0,1\}^n\rightarrow \{0,1\}^{n^{1+e}}$ with high advantage in the average case. This algorithm has the same runtime complexity as the distinguishing algorithm.

Note: Added two new small results: Search algorithm for PRGs/polynomial maps with high advantage in the average case, and reductions for LPN over different fields of same characteristic.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
PRGsNC0Local Random FunctionsPolynomial Equation SystemsAlgebraic AttacksSubexponentialLower Bounds
Contact author(s)
akin uenal @ inf ethz ch
History
2023-05-26: last of 2 revisions
2023-04-18: received
See all versions
Short URL
https://ia.cr/2023/550
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/550,
      author = {Akin Ünal},
      title = {New Baselines for Local Pseudorandom Number Generators by Field Extensions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/550},
      year = {2023},
      url = {https://eprint.iacr.org/2023/550}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.