Welcome to the resource topic for 2023/550
Title:
New Baselines for Local Pseudorandom Number Generators by Field Extensions
Authors: Akın Ünal
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, against PRGs F : \{0,1\}^n\rightarrow \{0,1\}^{n^{1+e}} we will give an algebraic attack 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.
ePrint: https://eprint.iacr.org/2023/550
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .