IACR News item: 24 April 2023
Akın Ünal
ePrint Report
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.
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.
Additional news items may be found on the IACR news page.