  This paper shows several connections between data structure problems and
cryptography against preprocessing attacks. Our results span data structure
upper bounds, cryptographic applications, and data structure lower bounds, as
summarized next.
  First, we apply Fiat--Naor inversion, a technique with cryptographic origins,
to obtain a data structure upper bound. In particular, our technique yields a
suite of algorithms with space $S$ and (online) time $T$ for a preprocessing
version of the $N$-input 3SUM problem where $S^3\cdot T = \widetilde{O}(N^6)$.
This disproves a strong conjecture (Goldstein et al., WADS 2017) that there is
no data structure that solves this problem for $S=N^{2-\delta}$ and $T =
N^{1-\delta}$ for any constant $\delta>0$.
  Secondly, we show equivalence between lower bounds for a broad class of
(static) data structure problems and one-way functions in the random oracle
model that resist a very strong form of preprocessing attack. Concretely, given
a random function $F: [N] \to [N]$ (accessed as an oracle) we show how to
compile it into a function $G^F: [N^2] \to [N^2]$ which resists $S$-bit
preprocessing attacks that run in query time $T$ where
$ST=O(N^{2-\varepsilon})$ (assuming a corresponding data structure lower bound
on 3SUM). In contrast, a classical result of Hellman tells us that $F$ itself
can be more easily inverted, say with $N^{2/3}$-bit preprocessing in $N^{2/3}$
time. We also show that much stronger lower bounds follow from the hardness of
kSUM. Our results can be equivalently interpreted as security against
adversaries that are very non-uniform, or have large auxiliary input, or as
security in the face of a powerfully backdoored random oracle.
  Thirdly, we give non-adaptive lower bounds for 3SUM and a range of geometric
problems which match the best known lower bounds for static data structure
problems.
