CryptoDB
Worst-Case Subexponential Attacks on PRGs of Constant Degree or Constant Locality
| Authors: |
|
|---|---|
| Download: |
|
| Presentation: | Slides |
| Conference: | EUROCRYPT 2023 |
| Award: | Early Career Best Paper Award |
| 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$ lies in $O(n^{1 - \frac{e}{d-1}})$, we give a second attack with the same space and time complexities whose advantage is at least $q^{-O(n^{1 - \frac{e}{d-1}})}$. If $F$ is of constant \emph{locality} $d$ and $q$ is constant, we construct a third attack that has a space and time complexity of $\exp(O(n^{1 - \frac{e'}{(q-1)d-1}}))$ and noticeable advantage $1-O(n^{-\frac{e'}{(q-1)d-1}})$ for every constant $e' < e$. |
BibTeX
@inproceedings{eurocrypt-2023-32855,
title={Worst-Case Subexponential Attacks on PRGs of Constant Degree or Constant Locality},
publisher={Springer-Verlag},
doi={10.1007/978-3-031-30545-0_2},
author={Akın Ünal},
year=2023
}