Paper 2023/550
New Baselines for Local Pseudorandom Number Generators by Field Extensions
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^{1e/(\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 constantdegree 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)
 Category
 Foundations
 Publication info
 Preprint.
 Keywords
 PRGsNC0Local Random FunctionsPolynomial Equation SystemsAlgebraic AttacksSubexponentialLower Bounds
 Contact author(s)
 akin uenal @ inf ethz ch
 History
 20230526: last of 2 revisions
 20230418: received
 See all versions
 Short URL
 https://ia.cr/2023/550
 License

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}, note = {\url{https://eprint.iacr.org/2023/550}}, url = {https://eprint.iacr.org/2023/550} }