In this work we observe a tight connection between three topics: $NC^0$ cryptography, $NC^0$ range avoidance, and static data structure lower bounds. Using this connection, we leverage techniques from the cryptanalysis of $NC^0$ PRGs to prove state-of-the-art results in the latter two subjects. Our main result is a quadratic improvement to the best known static data structure lower bounds, breaking a barrier which has stood for several decades. Prior to our work, the best known lower bound for any explicit problem with $M$ inputs and $N$ queries was $S \geq N^{\frac{1}{t}} (\log M)^{1-\frac{1}{t}}$ for any setting of the word length $w$ (where $S=$ space and $t=$ time) (Siegel ‘89). We prove, for the same class of explicit problems considered by Siegel, a quadratically stronger lower bound of the form $S \geq \tilde{\Omega}\Bigl( N^{\frac{2}{t}} \cdot (\log M)^{1-\frac{2}{t}} \cdot 2^{-O(w)} \Bigr)$ for all even $t>0$. Second, for the restricted class of nonadaptive bit probe data structures, we improve on this lower bound polynomially: for all odd constants $t>1$ we give an explicit problem with $N$ queries and $M \leq N^{O(1)}$ inputs and prove a lower bound $S \geq \Omega(N^{\frac{2}{t} + \epsilon_t})$ for some constant $\epsilon_t > 0$. Our results build off of an exciting body of work on refuting semi-random CSPs.

We then utilize our explicit cell probe lower bounds to obtain the best known unconditional algorithms for $NC^0$ range avoidance: we can solve any instance with stretch $n \mapsto m$ in polynomial time once $m >> n^{\frac{t}{2}}$ when $t$ is even; with the aid of an $NP$ oracle we can solve any instance with $m > n^{\frac{t}{2} - \epsilon_t}$ for $\epsilon_t>0$ when $t$ is odd. Finally, using our main correspondence we establish novel barrier results for obtaining significant improvements to our cell probe lower bounds: (i) near-optimal space lower bounds for an explicit problem with $t=4, w=1$ implies $EXP^{NP} \not\subseteq NC^1$; (ii) under the widely-believed assumption that polynomial-stretch $NC^0$ PRGs exist, there is no natural proof of a lower bound of the form $S \geq N^{\Omega(1)}$ when $t = \omega(1)$, $w=1$.