Welcome to the resource topic for 2023/119
Title:
Worst-Case Subexponential Attacks on PRGs of Constant Degree or Constant Locality
Authors: Akin Ünal
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 and are in the case of general local PRGs faster than currently known attacks. 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}}).
ePrint: https://eprint.iacr.org/2023/119
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 .