The $3$SUM-Indexing problem was first defined by Demaine and Vadhan in an
unpublished manuscript [67] and then by Goldstein, Kopelowitz, Lewenstein, and
Porat in [101] and is as follows:

######  Definition 112 ($3$SUM-Indexing).

Let $(\mathcal{G},+)$ be a finite abelian group. Preprocess two sets of group
elements $\mathcal{A}_{1},\mathcal{A}_{2}\subseteq\mathcal{G}$ each of size
$n$ into a data structure of $S$ memory cells of $w$ bits so that given any
query group element $z$, deciding whether there exists
$a_{1}\in\mathcal{A}_{1}$ and $a_{2}\in\mathcal{A}_{2}$ such that
$a_{1}+a_{2}=z$ is done by accessing at most $T$ memory cells.

A number of hardness conjectures were provided together with the definition of
the $3$SUM-Indexing Problem. Combined with reductions, these conjectures allow
establishment of conditional lower bounds for static data structures. To be
consistent with the terminology used for unconditional data structure lower
bounds, which are typically proved in the cell probe model [168], we refer to
accessing a memory cell as _probing_ the cell. The following conjectures were
made regarding the hardness of $3$SUM-Indexing:

######  Conjecture 1 ([101]).

Any data structure for $3$SUM-Indexing with space $S$ and $T=O(1)$ probes must
have $S=\tilde{\Omega}(n^{2})$.

######  Conjecture 2 ([67]).

Any data structure for $3$SUM-Indexing with space $S$ and $T$ probes must have
$ST=\tilde{\Omega}(n^{2})$.

######  Conjecture 3 ([101]).

Any data structure for $3$SUM-Indexing with space $S$ and $T=O(n^{1-\delta})$
probes must have $S=\tilde{\Omega}(n^{2})$.

Clearly the last conjecture is the strongest, and in general, we have the
following implications:

$\textrm{Conjecture~{}\ref{cnj:c}}\Rightarrow\textrm{Conjecture~{}\ref{cnj:b}}\Rightarrow\textrm{Conjecture~{}\ref{cnj:a}}$

These conjectures have been successfully used to prove fine-grained hardness
of several natural static data structure problems ranging from Set
Disjointness, Set Intersection, Histogram Indexing to Forbidden Pattern
Document Retrieval [101]. Furthermore, the security of the aforementioned
construction of one-way function $F^{\prime}$ relies on the hardness of
$3$SUM-Indexing.

Very surprisingly, Golovnev et al. [102] showed that the strongest of these
conjectures, Conjecture 3, is false. Concretely, they gave a data structure
for $3$SUM-Indexing with $T=\tilde{O}(n^{3\delta})$ and
$S=\tilde{O}(n^{2-\delta})$ for any constant $\delta>0$. This refutes
Conjecture 3, but not the remaining two conjectures. Their data structure is
based on an elegant use of Fiat and Naor’s [96] general time-space tradeoff
for function inversion.

The refutation of Conjecture 3 only makes it more urgent that we replace these
conjectured lower bounds by unconditional ones. However, depressingly little
is still known in terms of unconditional hardness of $3$SUM-Indexing. First,
[67] proved Conjecture 1 in the special case of $T=1$. Secondly, in the recent
work by Golovnev et al. [102], the following was proved for _non-adaptive_
data structures:

######  Theorem 113 ([102]).

Any _non-adaptive_ cell probe data structure answering $3$SUM-Indexing queries
for input sets of size $n$ from an abelian group $G$ of size $O(n^{2})$ using
$S$ words of $w$ bits must have query time $T=\Omega(\log n/\log(Sw/n))$.

A non-adaptive data structure is one in which the cells to probe are chosen
beforehand as a function _only_ of the query element $z$. That is, the data
structure is not allowed to choose which memory cells to probe based on the
contents of previously probed cells. Proving lower bounds for non-adaptive
data structures is often easier than allowing adaptivity, see e.g. [46, 40,
149], and Golovnev et al. remark: "_It is crucial for our proof that the input
is chosen at random after the subset of data structure cells, yielding a lower
bound only for non-adaptive algorithms_." [102]. Golovnev et al. explicitly
raised it as an interesting open problem (Open Question 3 in [102]) whether a
similar lower bound can be proved also for adaptive data structures.

####  1 Our Results

Our main contribution is a lower bound for $3$SUM-Indexing that holds also for
adaptive data structures:

######  Theorem 114.

Any cell probe data structure answering $3$SUM-Indexing queries for input sets
of size $n$ for abelian groups $([m],+\mod m)$ with $m=O(n^{2})$ and
$(\\{0,1\\}^{2\log(n)+O(1)},\oplus)$ using $S$ words of $w=\Omega(\lg n)$ bits
must have query time $T=\Omega(\log n/\log(Sw/n))$.

Our lower bound matches the previous bound from [102], this time however
allowing adaptivity. Moreover, it (essentially) matches the strongest known
lower bounds for static data structures (the strongest lower bounds peak at
$T=\Omega(\log n/\log(Sw/n))$ [125]), thus ruling out further progress without
a major breakthrough (also in circuit complexity [165, 86]).

Our proof is based on a novel reduction from Pǎtraşcu’s Reachability Oracles
in the Butterfly graph problem [148]. This problem, while rather abstract, has
been shown to capture the hardness of a wealth of static data structure
problems such as 2D Range Counting, 2D Rectangle Stabbing, 2D Skyline Counting
and Range Mode Queries, see e.g. [158, 45, 106] as well as for dynamic data
structure problems, including Range Selection and Median [128] and recently
also all dynamic problems that the Marked Ancestor Problem reduces to [127,
17], which includes 2D Range Emptiness, Partial Sums and Worst-Case Union-
Find. Our work adds $3$SUM-Indexing and all problems it reduces to, to the
list.

###### Even Smaller Universes.

The reduction from Reachability Oracles in the Butterfly Graph problem gives
lower bounds for abelian groups of size $\Omega(n^{2})$, leaving open the
possibility of more efficient data structures for smaller groups. Indeed,
$\Omega(n^{2})$ cardinality of the groups seems like a natural requirement for
hardness, as there are $n^{2}$ pairs of elements $a_{1}\in\mathcal{A}_{1}$ and
$a_{2}\in\mathcal{A}_{2}$ and thus for smaller groups, one might start to
exploit structures in the sumset $\mathcal{A}_{1}+\mathcal{A}_{2}$ to obtain
more efficient data structures. We therefore investigate whether the lower
bound in Theorem 114 can be generalized to smaller groups. Quite surprisingly,
we show that:

######  Theorem 115.

Any cell probe data structure answering $3$SUM-Indexing queries for input sets
of size $n$ for abelian groups $([m],+\mod m)$, with $m=O(n^{1+\delta})$ and
$(\\{0,1\\}^{(1+\delta)\log(n)+O(1)},\oplus)$ for a constant $\delta>0$, using
$S$ words of $w=\Omega(\lg n)$ bits must have query time $T=\Omega(\log
n/\log(Sw/n))$.

Thus we get logarithmic lower bounds for linear space data structures, even
when the group has size only $n^{1+\delta}$.

To prove Theorem 115, we revisit Pǎtraşcu’s Lopsided Set Disjointness (LSD)
communication game, which he also used to prove his lower bound for
Reachability Oracles in the Butterfly graph problem. We give a careful
reduction from LSD to $3$SUM-Indexing on small universes, thereby establishing
Theorem 115.

###### Non-Adaptive Data Structures.

As another contribution, we revisit the non-adaptive setting considered by
Golovnev et al. [102]. Here we present a significantly shorter proof of their
lower bound and also improve it from $T=\Omega(\lg n/\lg(Sw/n))$ to
$T=\Omega(\lg|G|/\lg(Sw/n))$. Concretely, we prove the following theorem:

######  Theorem 116.

Any non-adaptive cell probe data structure answering $3$SUM-Indexing queries
for input sets of size $n$ for an abelian group $\mathcal{G}$ of size
$\omega(n^{2})$, using $S$ words of $w=\Omega(\lg n)$ bits must have query
time $T=\Omega(\min\\{\log|\mathcal{G}|/\log(Sw/n),n/w\\})$.

We remark that the proof of Golovnev et al. [102] cannot be extended to a
$\lg|\mathcal{G}|$ (technically, they require $|\mathcal{G}|/n$ queries to
survive a cell sampling, whereas we only require $n$ queries to survive).

Our improvement has a subtle, but interesting consequence. Concretely, if the
size of the group grows to sub-exponential in $n$, say
$|\mathcal{G}|=2^{\sqrt{n}}$, then the lower bound becomes
$T=\Omega(\min\\{\sqrt{n}/\log(\frac{Sw}{n}),n/w\\})$. Since it is most
natural to assume the cell size is large enough to store a group element, i.e.
$w=\Omega(\lg|\mathcal{G}|)=\Omega(\sqrt{n})$, the lower bound is still at
least $T=\Omega(\sqrt{n}/\lg S)$. While such large groups are perhaps
unrealistic, one can also interpret the result as saying that if we are non-
adaptive and attempt to design a data structure that does not exploit the size
of the underlying group, then we are doomed to have a slow query time.

###### Non-Adaptive $2$-Bit-Probe Data Structures.

Finally, we consider non-adaptive data structures restricted to $T=2$ probes
in the _bit probe model_ , meaning that each memory cell has $w=1$ bits. The
lower bound from Theorem 113 by [102] in this case is
$S=\tilde{\Omega}(n^{3/2})$ (see the paper [102] for the general formulation
$S=\tilde{\Omega}(n^{1+1/T})$) and our lower bound from Theorem 116 is
$S=\tilde{\Omega}(n(|\mathcal{G}|/n)^{1/T})=\tilde{\Omega}(\sqrt{n|\mathcal{G}|})$.
We significantly strengthen this result by proving an
$S=\Omega(|\mathcal{G}|)$ lower bound for an abelian group $(\mathcal{G},+)$,
completely ruling out any non-trivial data structure with $2$ non-adaptive bit
probes (with $|\mathcal{G}|$ space, we can trivially store a bit vector
representing the sumset $\mathcal{A}_{1}+\mathcal{A}_{2}$ and have $T=1$ while
being non-adaptive):

######  Theorem 117.

Any non-adaptive data structure for $3$SUM-Indexing such that $T=2$ and $w=1$
requires $S=\Omega(|\mathcal{G}|)$ for an abelian group $(\mathcal{G},+)$.

Our proof takes an interesting new approach to data structure lower bounds and
we find that the proof itself is a valuable contribution to data structure
lower bounds. The basic idea is to view the memory cells of the data structure
as a graph with one node per cell. The queries then become edges corresponding
to the $T=2$ memory cells probed. If the number of memory cells is
$o(|\mathcal{G}|)$, then the graph has a super-linear number of edges. This
implies that its girth is at most logarithmic and hence we can find a short
cycle in the graph. A cycle is a set of $m$ queries being answered by $m$
memory cells. The standard cell sampling lower bounds (often used in data
structure lower bounds) cannot derive a contradiction from this, as the $m$
memory bits intuitively are sufficient to encode the $m$ query answers.
However, our novel contribution is to examine the different types of possible
query algorithms (i.e. which function of the two bits probed does it compute)
and argue that in all cases, such a short cycle is impossible. Directly
examining the types of query algorithms has not been done before in data
structure lower bounds and we find this a valuable contribution that we hope
may prove useful in future work.

###  1 Preliminaries

In this section we will formally define data structure problems, and the
$3$SUM Indexing problem.

####  1 Data Structures

A data structure problem $\mathcal{P}$ is a subset of
$\mathcal{S}\times\mathcal{Q}$. A cell probe data structure solving $P$ is a
pair of algorithms $(\mathcal{A}_{1},\mathcal{A}_{2})$ such that
$\mathcal{A}_{1}$ is a computationally unbounded algorithm that takes as input
$D\in\mathcal{S}$ and outputs $S$ memory cells, where each cell consists $w$
bits. Then, $\mathcal{A}_{2}$ is a computationally unbounded algorithm that
takes $q\in\mathcal{Q}$ and uses at most $T$ accesses to the data structure
output by $\mathcal{A}_{1}$ in deciding if $(D,q)\in\mathcal{P}$.

####  2 3SUM-Indexing

The $3$SUM-Indexing problem was first defined by Demaine and Vadhan in an
unpublished manuscript [67] and then by Goldstein, Kopelowitz, Lewenstein, and
Porat in [101].

######  Definition 118 ($3$SUM-Indexing).

Let $(\mathcal{G},+)$ be an finite abelian group. Pre-process two sets of
group elements $A_{1},A_{2}\subseteq\mathcal{G}$ each of size $n$ into a data
structure $D$ of $S$ memory cells of $w$ bits so that given any query group
element $z$, deciding whether there exists $a_{1}\in A_{1}$ and $a_{2}\in
A_{2}$ such that $a_{1}+a_{2}=z$ is done by accessing at most $T$ memory
cells.

Golovnev, Guo, Horel, Park, and Vaikuntanathan in [102] then defined a similar
variant of the problem which additionally asserted that the input sets $A_{1}$
and $A_{2}$ should be the same. We first show that the two definitions are
essentially equivalent up to a small change in the group. i.e. Any solution
that solves the [102] variant of $3$SUM-Indexing can also be adapted to solve
the variant in Definition 112.

######  Lemma 119.

Any pre-processing solution that solves $3$SUM-Indexing as defined in
Definition 112 for input sets of size $n$ and universe sizes of $u$ can also
be used to solve $3$SUM-Indexing as defined in [102].

###### Proof.

For any abelian group $(\mathcal{G}^{\prime},+^{\prime})$, we define
$(\mathcal{G},+)$ to be the group obtained as the direct product of
$(\\{0,1\\},+)$ and $(\mathcal{G}^{\prime},+^{\prime})$. Then, given any two
sets $\mathcal{A}_{1}$ and $\mathcal{A}_{2}$, we construct set
$\mathcal{A}=\\{0\\}\times A_{1}\cup\\{1\\}\times\mathcal{A}_{2}$. For any
query value $z$, we then form the query as $(1,z)$. In our transformation, the
group size and input array length is doubled.

Assuming that there exists a pair $a_{1}\in\mathcal{A}_{1}$ and
$a_{2}\in\mathcal{A}_{2}$ such that $a_{1}+a_{2}=z$, then
$(0,a_{1}),(1,a_{2})$ is in $A$ and so $(0,a_{1})+(1,a_{2})=(1,z)$. On the
other hand, assuming that no such pairing exists, then no such pairing
$(0,a_{1}),(1,a_{2})\in\mathcal{A}$ sums to $(1,z)$ as well. ∎

###  2 Reduction from Reachability Oracles in the Butterfly Graph

In this section, we give a reduction from the problem of _Reachability Oracles
in the Butterfly Graph_ to $3$SUM-Indexing with the cyclic group and the XOR
group, proving Theorem 114. In both cases, the size of the group is at most
quadratic with respect to the input set sizes.

######  Definition 120 (Butterfly Graphs).

A Butterfly graph of degree $B$ and depth $d$ is a directed graph with $d+1$
layers, each comprising of $B^{d}$ nodes. For each layer, the $i^{th}$ node
can be associated with a $d$-digit number in base $B$ which we will refer to
as its _label_ $v_{i}$ where $v_{i}[0]$ denotes the least significant digit.
Then there is an edge from node $i$ on the $k^{th}$ layer to node $j$ on the
$(k+1)^{th}$ layer if and only if $v_{i}[h]=v_{j}[h]$ for all $h\neq k$. That
is to say, that there is an edge if and only if $i$ and $j$ may differ only on
the $k^{th}$ digit of their labels. We will denote such an edge by
$e_{k}(i,j)$.

Nodes in the layer $0$ of the graph are called _source nodes_ , whereas nodes
in layer $d$ of the graph are called _sink nodes_.

######  Definition 121 (Reachability Oracles in the Butterfly Graph).

The problem of Reachability Oracles in the Butterfly Graph is that one has to
pre-process into a data structure a subset of the edges $E$ of the butterfly
graph of degree $B$ and depth $d$. Queries come in the form of $(s,t)$ and the
goal is decide if there exists a path from source node $s$ to sink node $t$
using the subset of edges $E$.

Pǎtraşcu proved the following lower bound for the problem in the cell probe
model:

######  Lemma 122 (Section 5 of [148]).

Any cell probe data structure answering reachability queries in subgraphs of
the butterfly graph with degree $B$ and depth $d$, using $S$ words of $w$ bits
must have query time $t=\Omega(d)$, assuming that $B=\Omega(w^{2})$ and
$\log(B)=\Omega(\log(Sd/N))$ where $N=dB^{d}$.

A few remarks about reachability in the Butterfly graph are in order. Firstly,
note that for any source-sink pair $(s,t)$, there exists a unique path from
source $s$ to sink $t$ in the Butterfly graph. Namely, the path uses exactly
edges of the form $e_{k}(i,j)$ such that for $k\in[d]$, $e_{k}(i,j)$ is the
edge from node $i$ on layer $k$ to node $j$ on layer $k+1$ such that:

  1. 1.

$v_{s}[h]=v_{i}[h]$ for all $h\geq k$. That is to say that the $d-k$ most
significant digits of the labels of nodes $s$ and $i$ are the same.

  2. 2.

$v_{t}[h]=v_{j}[h]$ for all $h\leq k$. That is to say that the $k+1$ least
significant digits of the labels of nodes $t$ and $j$ are the same.

Conversely, we can also say that the edge $e_{k}(i,j)$ connects all pairs of
nodes $s,t$ such that the label for $s$ shares the most significant $d-k$
digits with $i$ and the label for $t$ shares the least significant $k+1$
digits with $t$.

Intuitively, this is because the traversing from node $i$ in the $k^{th}$
layer to node $j$ in the $(k+1)^{th}$ layer can be seen as “setting” the
$k^{th}$ digit of the label for node $i$ into the $k^{th}$ digit of the label
for node $j$ while leaving the rest of the digits unaltered.

The general idea of the reduction to $3$SUM-Indexing is to test whether all
the required edges are present when querying for $s$ and $t$. This should be
done by asking one $3$SUM-Indexing query. We will design it such that a sum
$z=a_{1}+a_{2}$ exists for our query $z$ if and only if there is at least one
edge missing on the path from $s$ to $t$.

###### Constructing $\mathcal{A}_{1}$.

Our basic idea is to take every edge $e_{k}(i,j)$ in the Butterfly graph and
encode it into a group element $g$ in $\mathcal{A}_{1}$. We construct $g$ such
that its digits can be broken up into 5 blocks so that conceptually the:

  1. 1.

first block encodes the layer the edge is from;

  2. 2.

second block encodes the presence of edge $e_{k}(i,j)$ in $E$;

  3. 3.

third block encodes the $d-k$ most significant bits of $i$ followed by $k$
zeroes;

  4. 4.

fourth block holds $d-k-1$ zeroes followed by the $k+1$ least significant
digits of $j$;

  5. 5.

fifth block holds $2$ zeroes.

In short, for every edge $e_{k}(i,j)$, we add group element to
$\mathcal{A}_{1}$ whose digits are in the following form:

$(k,\mathbbm{1}\\{{e_{k}(i,j)\in
E}\\},v_{i}[d-1],\ldots,v_{i}[k],\underbrace{0,\ldots,0}_{\text{d -
1}},v_{j}[k],\ldots,v_{j}[0],0,0)$

where $\mathbbm{1}\\{{e_{k}(i,j)\in E}\\}$ is $1$ if $e_{k}(i,j)\in E$ and $0$
otherwise. Note that the Butterfly graph has $dB^{d}$ nodes with degree $B$,
hence a total of $n=dB^{d+1}$ edges. Since $\mathcal{A}_{1}$ has one element
for each such edge, we have $|\mathcal{A}_{1}|=n$.

###### Constructing $\mathcal{A}_{2}$.

Next, we construct the set $\mathcal{A}_{2}$ of group elements such that for
every $k$, it “helps” any group element $g$ in $\mathcal{A}_{1}$, originating
from an edge $e_{k}(i,j)$, to sum to any value where the third block shares
the $d-k$ most significant bits with $i$ and the fourth block shares the $k+1$
least significant digits of $j$. This can be done by adding into set
$\mathcal{A}_{2}$ every group element such that the:

  1. 1.

first block holds some value $-k$;

  2. 2.

second block is zero;

  3. 3.

third block is $d-k$ zeroes followed by any possible $k$ digit value;

  4. 4.

fourth block holds any possible $d-k-1$ digit value followed by $k+1$ zeroes;

  5. 5.

fifth block holds any possible digit value from $[0,B-1]$.

Thus for $k\in[0,d-1]$, we add any number of the following form into
$\mathcal{A}_{2}$:

$(-k,0,\underbrace{0,\ldots,0}_{d-k},\underbrace{\star,\ldots,\star}_{d-1},\underbrace{0,\ldots,0}_{k+1},\star,\star)$

where $\star$ denotes wildcard. Note that the least significant digits is not
strictly necessary but is included to enforce that the size of the sets
$\mathcal{A}_{1}$ and $\mathcal{A}_{2}$ are the same. Observe that
$|\mathcal{A}_{2}|=dB^{d+1}=n=|\mathcal{A}_{1}|$.

###### Different Groups.

For the reduction to $3$SUM-indexing in the cyclic group, we will consider the
set of integers in $[(dB^{d+1})^{2}]$. To that end, the encoding works by
understanding the $2(d+2)$ digits as specifying a mixed-radix number, where
the most significant digit is in base $4d$, the second most significant digit
is in base $3$ and the remaining digits are in base $B$. In which case, we can
take $-k$ to be $4d-k$.

On the other hand, for the XOR group, assuming that $d$ and $B$ are powers of
$2$, we can then also naturally transform each digit into their binary
representation with the exception of the most significant digit whose bit
representation should be based on the number’s complement and the second most
significant digit may be in base $2$.

###### Translating a Query.

What remains is to explain how we answer a reachability query $(s,t)$. We will
first consider the reduction for the group
$([(dB^{d+1})^{2}],+\mod(dB^{d+1})^{2})$ and subsequently argue that the same
reduction basically holds for the XOR group assuming that $d$ and $B$ are
powers of $2$. We claim that there exists $a_{1}\in A_{1}$ and $a_{2}\in
A_{2}$ whose sum is

$z_{(s,t)}=(0,0,v_{s}[d-1],\ldots,v_{s}[0],v_{t}[d-1],\ldots,v_{t}[0],0,0)$

if and only if there does not exist a path from $s$ to $t$ in the Butterfly
graph.

To see this, we first argue that for a pair $a_{1}+a_{2}$ that could
potentially sum to $z_{(s,t)}$, we need not worry about carries amongst the
digits of the numbers. To see this, we start by observing that $a_{1}+a_{2}$
must have its most significant digit equal to $0$. We claim this is only
possible if $a_{1}$’s most significant digit is $k$ and $a_{2}$’s is
$4d-k=-k$. To see this, observe that the second most significant digit of
$a_{1}$ is at most $1$ and the second most significant of $a_{2}$ is always
$0$. Since the second most significant digit is in base $3$, this means that
we cannot get a carry from these digits. Now that we have established this, we
observe that for all remaining digits of any valid pair $a_{1}$ and $a_{2}$
(pairs where the most significant digit in the sum is $0$), there is at most
one of the elements that has a non-zero digit, hence we will not see any
carries.

Now assume there does not exists a path from some source node $s$ to some sink
node $t$. This must mean that there exists a $k\in[0,d-1]$ and an edge
$e_{k}(i,j)$ not in $E$ where:

$\displaystyle v_{i}$
$\displaystyle=(v_{s}[d-1],\ldots,v_{s}[k],v_{t}[k-1],\ldots,v_{t}[0])$
$\displaystyle v_{j}$
$\displaystyle=(v_{s}[d-1],\ldots,v_{s}[k+1],v_{t}[k],\ldots,v_{t}[0])$

By construction, this implies that the following group element exists in the
set $A_{1}$:

$(k,0,v_{s}[d-1],\ldots,v_{s}[k],\underbrace{0,\ldots,0}_{\text{d -
1}},v_{t}[k],\ldots,v_{t}[0],0,0)$

Furthermore, the following group element always exists in $A_{2}$:

$(-k,0,0,\ldots,0,v_{t}[k-1],\ldots,v_{t}[0],v_{s}[d-1],\ldots,v_{s}[k+1],0,\ldots,0,0)$

This means that the value
$(0,0,v_{s}[d-1],\ldots,v_{s}[0],v_{t}[d-1],\ldots,v_{t}[0],0)$ is obtainable
as a sum $a_{1}+a_{2}$. If on the other hand there is a path between $s$ and
$t$, then all elements in $A_{1}$ of the form

$(k,\star,v_{s}[d-1],\ldots,v_{s}[k],\underbrace{0,\ldots,0}_{\text{d -
1}},v_{t}[k],\ldots,v_{t}[0],0)$

must have $\star=1$ and thus it is not possible to write $z_{(s,t)}$ as
$a_{1}+a_{2}$.

###### The XOR Group.

For a reduction to the XOR group setting, we consider each element coordinate-
wise using their binary representations with the exception that in the first
coordinate the value is represented using the number’s complement
representation. Using the previous remark we also assert that for any pair
$a_{1}\in\mathcal{A}_{1}$, $a_{2}\in\mathcal{A}_{2}$, the only common digit
that is both non-zero is the most significant digit and thus the addition
being done digit-wise. For that reason, the sum behaves exactly the same way
over the XOR group as it does over the cyclic group that we have defined. Thus
the size of the universe and input sets $\mathcal{A}_{1},\mathcal{A}_{2}$
remain unchanged and the reduction holds in the XOR group as well.

###### Analysis.

Now by setting $B=\frac{Sw^{2}}{n}$, note that $B=\Omega(w^{2})$ and:

$\displaystyle\log(Sd/N)\leq\log\mathopen{}\mathclose{{}\left(\frac{SB\log(n)}{n}}\right)\leq\log(SBw/n)\leq\log(B^{2})=O(\log
B)$

Furthermore, it holds that

$\displaystyle\log(Sw/n)=\frac{1}{2}\log((Sw/n)^{2})\geq\frac{1}{2}\log(Sw^{2}/n)\geq\frac{1}{2}\log
B$

Using Lemma 122, it then follows that for any cell-probe solution for $3$SUM-
Indexing for the cyclic group $([m],+\mod m)$ where $m=O(n^{2})$ and XOR group
$(\\{0,1\\}^{2\log(n)+O(1)},\oplus)$ any static data structure that uses
$S\geq n$ cells of $w\geq\log(n)$ bits has query time
$T=\Omega(d)=\Omega(\lg_{B}n)=\Omega(\log n/\log(Sw/n))$.

###  3 Reduction from Lopsided Set Disjointness

In this section, we prove Theorem 115, establishing hardness of $3$SUM-
Indexing also for abelian groups of size $\Delta=n^{1+\delta}$. For the proof,
we focus on the integers modulo $\Delta$, but remark that the proof readily
adapts to the XOR group as well.

For the proof, we use Pǎtraşcu’s Blocked Lopsided Set Disjointness (Blocked
LSD) problem. In this problem, there are two players, Alice and Bob. Bob
receives as input a set $\mathcal{X}$, which is an arbitrary subset of a
universe $[N]\times[B]$. Alice receives a set $\mathcal{Y}\subset[N]\times[B]$
with the restriction that $\mathcal{Y}$ contains exactly one element
$(i,b_{i})$ for every $i=0,\dots,N-1$. The goal for Alice and Bob is to
determine whether $\mathcal{X}\cap\mathcal{Y}=\emptyset$ while minimizing
communication. The following is known regarding the communication complexity
of Blocked LSD:

######  Lemma 123 (Theorem 4 of [148]).

Fix $\delta>0$. Any communication protocol for Blocked LSD requires either
Alice sending at least $\delta N\log B$ bits, or Bob sending at least
$NB^{1-O(\delta)}$ bits.

The basic idea in the reduction, is to have Bob interpret his set
$\mathcal{X}$ as two input sets $\mathcal{A}_{1},\mathcal{A}_{2}$ of $n=NB$
group elements to $3$SUM-Indexing (we may have $|\mathcal{A}_{1}|$ and
$|\mathcal{A}_{2}|$ smaller than $NB$, but we can always pad with dummy
elements, so we assume $n=NB$). Given a data structure $D$ for $3$SUM-
Indexing, Bob then builds $D$ on this input. Alice on the other hand
interprets her set $\mathcal{Y}$ (which has cardinality $N$) as a set of
$N/\ell$ queries to $3$SUM-Indexing, where $\ell$ is a parameter to be
determined. The key property of the reduction, is that the answers to all
$N/\ell$ queries of Alice on $D$, determines whether
$\mathcal{X}\cap\mathcal{Y}=\emptyset$.

###### Communication Protocol.

Assume for now that we can give such a reduction. Alice and Bob then obtains a
communication protocol for Blocked LSD as follows: Let $T$ be the query time
of $D$. For $i=1,\dots,T$, Alice simulates the $i$’th step of the query
algorithm for each of her $N/\ell$ queries, _in parallel_. This is done by
asking Bob for the set of at most $N/\ell$ cells that they probe in the $i$’th
step. This costs $O(\lg\binom{S}{N/\ell})=O((N/\ell)\lg(S\ell/N))$ bits of
communication by specifying the required cells as a subset of the $S$ memory
cells of $D$. Bob replies with the contents of the cells, costing
$((N/\ell)w)$ bits. This is done for $T$ rounds, resulting in a communication
protocol where Alice sends $O((N/\ell)T\lg(S\ell/N))$ bits and Bob sends
$O((N/\ell)Tw)$ bits. If we fix $B=w^{4}$ and $\delta$ as a small enough
constant, then Lemma 123 says that either Alice sends $\Omega(N\lg w)$ bits or
Bob sends $\Omega(N\sqrt{B})=\Omega(Nw^{2})$ bits. In our protocol, Bob’s
communication is $O((N/\ell)Tw)=O(NTw)$ bits. We assume $w=\Omega(\lg n)$,
thus we conclude that either $NTw=\Omega(Nw^{2})\Rightarrow T=\Omega(\lg n)$,
or Alice’s communication must be $\Omega(N\lg B)=\Omega(N\lg w)$ bits. In the
first case, we are done with the proof, hence we examine the latter case.
Alice’s communication is $O((N/\ell)T\lg(S\ell/N))$ bits, which implies
$T=\Omega(\ell\lg w/\lg(S\ell/N))$. Thus to derive our lower bound, we have to
argue that it suffices for Alice to answer $N/\ell$ queries for a large enough
$\ell$.

###### Asking Few Queries.

We will show that it suffices for Alice to ask $N/\ell$ queries with
$\ell=\varepsilon\lg n/\lg w$. Here $\varepsilon>0$ is a small constant
depending on $\delta$ in the group size $\Delta=n^{1+\delta}$. Thus we get a
lower bound of $T=\Omega(\lg n/\lg((S\lg n)/(N\lg w)))$. Since
$N=n/B=n/w^{4}$, this simplifies to $T=\Omega(\lg n/\lg(Sw/n))$ as claimed in
Theorem 115.

Thus what remains is to show how Alice and Bob computes the input and queries.
For this, they conceptually partition the universe $[N]\times[B]$ into groups
$\\{i\ell,\dots,(i+1)\ell-1\\}\times[B]$ for $i=0,\dots,N/\ell$. Alice will
ask precisely one query for each such group. Denote by $\mathcal{Y}_{i}$ the
subset of $\mathcal{Y}$ that falls in the $i$’th group and denote by
$\mathcal{X}_{i}$ the subset of $\mathcal{X}$ that falls in the $i$’th group.
Clearly $\mathcal{X}\cap\mathcal{Y}=\emptyset$ if and only if
$\mathcal{X}_{i}\cap\mathcal{Y}_{i}=\emptyset$ for all $i$. Thus Alice will
use her $i$’th query to determine whether
$\mathcal{X}_{i}\cap\mathcal{Y}_{i}=\emptyset$.

###### Constructing $\mathcal{A}_{1}$ and $\mathcal{A}_{2}$.

To support this, Bob first constructs the set $\mathcal{A}_{1}$ based on his
elements $\mathcal{X}$. He examines each group $\mathcal{X}_{i}$, and for
every $(j,b)\in\mathcal{X}_{i}$, he adds the integer
$i(2B+1)^{\ell+1}+(b+1)(2B+1)^{j-i\ell}$ to $\mathcal{A}_{1}$. Next, he
constructs the set $\mathcal{A}_{2}$. For this, he considers all vectors
$Z=(b_{0},\dots,b_{\ell-1})$ for which the numbers are all between $0$ and $B$
and precisely one of them is $0$. He adds the integer
$\sum_{j\in[\ell]}b_{j}(2B+1)^{j}$ to $\mathcal{A}_{2}$. This completes Bob’s
construction of the input sets $\mathcal{A}_{1}$ and $\mathcal{A}_{2}$. We
have $|A_{1}|\leq NB=n$ and $|\mathcal{A}_{2}|\leq(2B+1)^{\ell}$.

###### Asking the Queries.

We next describe how Alice translates her set $Y$ into queries. For each
$Y_{i}$, she needs to construct one query $z_{i}$ whose answer determines
whether $X_{i}\cap Y_{i}=\emptyset$. Recall that $Y_{i}$ is of the form
$\\{(i\ell,b_{0}),(i\ell+1,b_{1}),\dots,((i+1)\ell-1,b_{\ell-1})\\}$. She
starts by subtracting off $i\ell$ from the first index in each pair, obtaining
the set $\\{(0,b_{0}),(1,b_{1}),\dots,(\ell-1,b_{\ell-1})\\}$. Alice now asks
the query $z_{i}=i(2B+1)^{\ell+1}+\sum_{j=0}^{\ell-1}(b_{j}+1)(2B+1)^{j}$.

###### Correctness.

We claim that $z_{i}$ is part of a $3$SUM if and only if
$\mathcal{X}_{i}\cap\mathcal{Y}_{i}\neq\emptyset$. To see this, observe first
that to write $z_{i}$ as $a_{1}+a_{2}$, it must be the case that $a_{1}$ was
constructed from $\mathcal{X}_{i}$ as otherwise we cannot obtain the
$i(2B+1)^{\ell+1}$ parts of $z_{i}$. Next, observe that if we write the
integers in base $2B+1$, then $\mathcal{A}_{2}$ contains precisely every
integer of the form where there is a single digit $j\in[\ell]$ that is zero
and all remaining are non-zero. Also, the numbers obtained from
$(j,b)\in\mathcal{X}_{i}$ are of the form
$i(2B+1)^{\ell+1}+(b+1)(2B+1)^{j-i\ell}$ and thus have exactly one non-zero
digit among the first $\ell$. Since $z_{i}$ has exclusive non-zero digits in
the first $\ell$, it follows that
$z_{i}=i(2B+1)^{\ell+1}+\sum_{j=0}^{\ell-1}(b_{j}+1)(2B+1)^{j}$ can be written
as $a_{1}+a_{2}$ if and only if $a_{1}$ was obtained from a $(j,b)\in X_{i}$
for which $b$ is equal to $b_{j-i\ell}$. This is the case if and only if
$\mathcal{X}_{i}$ and $\mathcal{Y}_{i}$ intersect in $(j,b)$.

###### Analysis.

We now determine $\ell$. Recall that $B=w^{4}$ and observe that all possible
integers are bounded by $N(2B+1)^{\ell+2}\leq n(2B+1)^{\ell+2}$. If we insist
on a group of size $\Delta=n^{1+\delta}$, this means we can set
$\ell=\delta\lg n/\lg(2B+1)-2\geq\varepsilon\lg n/\lg w$ for a sufficiently
small constant $\varepsilon>0$. This also implies that $|A_{2}|\leq
n^{\delta}\leq n$ and thus completes the proof of Theorem 115.

###  4 Lower Bound for Non-Adaptive Data Structures

In this section, we prove an
$\Omega(\min\\{\lg|\mathcal{G}|/\lg(Sw/n),n/w\\})$ lower bound for non-
adaptive $3$SUM-Indexing data structures when $|\mathcal{G}|=\omega(n^{2})$.
Similarly to the previous approach by Golovnev et al. [102], we use a cell
sampling approach.

Consider a data structure using $S$ memory cells of $w$ bits and answering
queries non-adaptively in $T$ probes. Consider all subsets of $\Delta=n/(2w)$
memory cells. There are $\binom{S}{\Delta}$ such subsets. We say that a query
$z$ is answered by a set of cells $\mathcal{C}$, if all the (non-adaptively
chosen) cells it probes are contained in $\mathcal{C}$. Any query $z$ is
answered by at least $\binom{S-T}{\Delta-T}$ sets of $\Delta$ cells, namely
all those containing the $T$ cells probed on $z$. It follows by averaging over
the $|\mathcal{G}|$ queries that there is a set of cells $\mathcal{C}^{*}$
answering at least

$|G|\binom{S-T}{\Delta-T}/\binom{S}{\Delta}=|\mathcal{G}|\frac{\Delta(\Delta-1)\cdots(\Delta-T+1)}{S(S-1)\cdots(S-T+1)}\geq|G|\mathopen{}\mathclose{{}\left(\frac{\Delta-T+1}{S}}\right)^{T}$

queries.

If $T\geq\Delta/2$, we are already done as we have proven $T=\Omega(n/w)$.
Otherwise, $T\leq\Delta/2$ and thus the above is at least
$|\mathcal{G}|(\Delta/(2S))^{T}=|\mathcal{G}|(n/(4Sw))^{T}$. If we assume for
contradiction that $T=o(\lg|\mathcal{G}|/\lg(Sw/n))$, this is at least
$|\mathcal{G}|^{1-o(1)}>n$. Let $\mathcal{Q}$ be the group elements
corresponding to an arbitrary subset of $n$ of those queries. We argue that we
can construct a distribution over inputs $\mathcal{A}_{1},\mathcal{A}_{2}$
such that the queries $\mathcal{Q}$ cannot be answered from few cells,
contradicting that we have answered them from $\mathcal{C}^{*}$. More
precisely, we show:

######  Lemma 124.

Let $(\mathcal{G},+)$ be an abelian group with $\omega(n^{2})$ elements. Given
any subset $\mathcal{Q}\subseteq\mathcal{G}$ of at most $n$ elements, there
exists an input distribution $D$ of $\mathcal{A}_{1},\mathcal{A}_{2}$ such
that, all the events of the form $q\in(\mathcal{A}_{1}+\mathcal{A}_{2})$
(defined as
$\\{a_{1}+a_{2}:a_{1}\in\mathcal{A}_{1},a_{2}\in\mathcal{A}_{2}\\}$) for all
$q$ in $\mathcal{Q}$ is fully independent. That is, for any subset
$\mathcal{S}=\\{s_{1},s_{2}\ldots,s_{r}\\}$ of $\mathcal{Q}$ of $r$ elements,
and any sequence of $r$ events $E_{1},E_{2},\ldots,E_{r}$ either of the form
$s_{i}\in(A_{1}+A_{2})$ or the form $s_{i}\notin(A_{1}+A_{2})$, it holds that
$\Pr[\bigwedge_{i=1}^{r}E_{i}]=\prod_{i=1}^{r}\Pr[E_{i}]$ . Furthermore, for
any $q\in\mathcal{Q}$, it is the case that $\Pr_{(A_{1},A_{2})\sim
D}[q\in(A_{1}+A_{2})]=\frac{1}{2}$.

The proof is deferred to the end of the section.

We now use Lemma 124 to derive a contradiction to the assumption that
$T=o(\lg|\mathcal{G}|/\lg(Sw/n))$. Concretely, we invoke the lemma with the
$Q$ defined above. This implies that the answers to the queries in
$\mathcal{Q}$ has entropy $n$ bits. However, they are being answered from a
fixed set of $n/2w$ cells. These cells together have $n/2$ bits. Since their
addresses are fixed, their contents must uniquely determine the $n$ query
answers, yielding the contradiction and hence
$T=\Omega(\min\\{\lg|\mathcal{G}|/\lg(Sw/n),n/w\\})$. This completes the proof
of Theorem 116. What remains is to prove Lemma 124:

###### Proof of Lemma 124.

We prove the lemma by first showing that given
$\mathcal{Q}\subseteq\mathcal{G}$ of $n$ elements, for any
$\mathcal{P}\subseteq\mathcal{Q}$ there exists an input pair
$\mathcal{A}_{1}^{\mathcal{P}}$ and $\mathcal{A}_{2}^{\mathcal{P}}$ such that
$\mathcal{P}\subseteq(\mathcal{A}_{1}^{\mathcal{P}}+\mathcal{A}_{2}^{\mathcal{P}})$
and
$(\mathcal{Q}\setminus\mathcal{P})\cap(\mathcal{A}_{1}^{\mathcal{P}}+\mathcal{A}_{2}^{\mathcal{P}})=\emptyset$.
That is to say that for every possible subset $\mathcal{P}$ of $\mathcal{Q}$,
there exists a pair of sets
$(\mathcal{A}_{1}^{\mathcal{P}},\mathcal{A}_{2}^{\mathcal{P}})$ such that
$(\mathcal{A}_{1}^{\mathcal{P}}+\mathcal{A}_{2}^{\mathcal{P}})$ contains all
the pair sums of $\mathcal{P}$ and none of the pair sums outside of
$\mathcal{P}$ and in $\mathcal{Q}$. Then $D$ is the distribution that is
uniform over all possible pairs of sets
$(\mathcal{A}_{1}^{\mathcal{P}},\mathcal{A}_{2}^{\mathcal{P}})$ with
$\mathcal{P}$ ranging over all subsets of $\mathcal{Q}$. Another way to view
$D$ is the distribution that first randomly samples
$\mathcal{P}\subseteq\mathcal{Q}$ before deterministically outputing pairs of
sets $(\mathcal{A}_{1}^{P},\mathcal{A}_{2}^{P})$.

Given any $\mathcal{P}$, we build the sets $\mathcal{A}_{1}^{\mathcal{P}}$ and
$\mathcal{A}_{2}^{\mathcal{P}}$ iteratively, where they are both initially
empty. Let $p_{1},p_{2},\ldots$ enumerate the elements of $\mathcal{P}$. At
each iteration, let $p_{i}$ be the first value not in
$(\mathcal{A}_{1}^{\mathcal{P}}+\mathcal{A}_{2}^{\mathcal{P}})$. There are
$\lvert\mathcal{G}\rvert$ ordered pairs of elements $(a_{1},a_{2})$ such that
$a_{1}+a_{2}=p_{i}$. To see this, note that letting $a_{1}=p_{i}+(-t)$ and
$a_{2}=t$ for any $t\in\mathcal{G}$ yields us a distinct pair of elements for
which the sum holds. We want to show that we can add $n$ pairs of elements
(thus enumerating all of the elements in $\mathcal{P}$ and beyond) without
ever having any pair sum to an element in $(\mathcal{Q}\setminus\mathcal{P})$.
For each element $q\in(\mathcal{Q}\setminus\mathcal{P})$, and each element in
$a\in\mathcal{A}_{1}$, there is exactly one element $b\in\mathcal{G}$ such
that $a+b=q$ (likewise for each element $a\in\mathcal{A}_{2}$). Therefore, for
any given $q$, there are $\lvert\mathcal{A}_{1}\rvert$ elements
$b\in\mathcal{G}$ that if added into set $\mathcal{A}_{2}$, would imply that
$q\in(\mathcal{A}_{1}+\mathcal{A}_{2})$ (likewise for set $\mathcal{A}_{2}$).
Since $\lvert\mathcal{Q}\setminus\mathcal{P}\rvert\leq n$, and at every
iteration $\lvert\mathcal{A}_{1}\rvert=\lvert\mathcal{A}_{2}\rvert\leq n$, we
have that there are at most $2n^{2}$ elements that cannot be added into either
set $\mathcal{A}_{1}$ or set $\mathcal{A}_{2}$ (otherwise sets
$(\mathcal{Q}\setminus\mathcal{P})$ and $(\mathcal{A}_{1}+\mathcal{A}_{2})$
are no longer disjoint).

Therefore there must still exist a pair $(a_{1},a_{2})$ such that
$a_{1}+a_{2}=p_{i}$ and
$(\\{a_{1}\\}\cup\mathcal{A}_{1}^{\mathcal{P}}+\\{a_{2}\\}\cup\mathcal{A}_{2}^{\mathcal{P}})\cap(\mathcal{Q}\setminus\mathcal{P})=\emptyset$,
assuming that $\lvert\mathcal{G}\rvert=\omega(n^{2})$. In the case that every
element in $\mathcal{P}$ is enumerated before we have added $n$ pairs, we can
still pad with more arbitrary pairs of elements from $\mathcal{G}$ whilst
avoiding creating any element in $(\mathcal{Q}\setminus\mathcal{P})$ for the
same reason as laid out above.

It remains to show that our distribution $D$ indeed witnesses full
independence and that each individual event occurs with probability
$\frac{1}{2}$. Let $\mathcal{S}$ be an arbitrary subset of $\mathcal{Q}$ of
size $r\leq n$. Further, let $E_{i}$ be either the event that
$s_{i}\in(\mathcal{A}_{1}+\mathcal{A}_{2})$ or
$s_{i}\notin(\mathcal{A}_{1}+\mathcal{A}_{2})$, and let
$\mathcal{S}^{\prime}\subseteq\mathcal{S}$ contain the elements $s_{i}$ such
that $E_{i}$ is the event that $s_{i}\in(\mathcal{A}_{1}+\mathcal{A}_{2})$ (so
$\mathcal{S}\setminus\mathcal{S}^{\prime}$ is precisely the set of elements
$s_{i}$ for which there is the event
$s_{i}\notin(\mathcal{A}_{1}+\mathcal{A}_{2})$). In the support of $D$, there
are exactly $2^{n}$ pairs of sets $(\mathcal{A}_{1}^{P},\mathcal{A}_{2}^{P})$,
each realising a distinct subset $\mathcal{P}\subseteq\mathcal{Q}$ of elements
such that $\mathcal{P}\subseteq(\mathcal{A}_{1}+\mathcal{A}_{2})$ and
$(\mathcal{Q}\setminus\mathcal{P})\cap(\mathcal{A}_{1}+\mathcal{A}_{2})=\emptyset$.
Thus, given any set
$\mathcal{S}^{\prime}\subseteq\mathcal{S}\subseteq\mathcal{Q}$, there are
$2^{n-r}$ pairs of sets
$(\mathcal{A}_{1}^{\mathcal{P}},\mathcal{A}_{2}^{\mathcal{P}})$ each with for
set $\mathcal{P}$ such that $\mathcal{S}^{\prime}\subseteq\mathcal{P}$ and
$(\mathcal{S}\setminus\mathcal{S}^{\prime})\subseteq(\mathcal{Q}\setminus\mathcal{P})$.
Thus we argue that

$\Pr\mathopen{}\mathclose{{}\left[\bigwedge_{i=1}^{r}E_{i}}\right]=\frac{2^{n-r}}{2^{n}}=2^{-r}.$

Note that for individual events, we can take the subset $\mathcal{S}$ to
contain only a single element $q$ from $\mathcal{Q}$ and the above argument
would imply that $\Pr[q\in(\mathcal{A}_{1},\mathcal{A}_{2})]=\frac{1}{2}$ and
that $\Pr[q\notin(\mathcal{A}_{1},\mathcal{A}_{2})]=\frac{1}{2}$. Thus the
conclusion readily follows from the fact that

$\prod_{i=1}^{r}\Pr\mathopen{}\mathclose{{}\left[E_{i}}\right]=2^{-r}.$

###  5 Bit Probe Lower Bound for $3$SUM-Indexing

In this section we give the bit probe lower bound for $3$SUM-Indexing stated
in Theorem 117.

The proof idea is based on an incompressibility argument. We will inspect the
way the queries are structured and construct a specific input distribution
that the data structure algorithm end up using too few bits for and therefore
derive a contradiction. For this, we will again use Lemma 124 from the
previous section. The key difference between this proof and the proof in the
previous section, lies in how we find a set of queries answered by too few
cells. Moreover, in this proof, we will derive a contradiction even with $m$
queries being answered by $m$ cells, and thus intuitively the cells actually
have enough information, but yet cannot answer the queries. We start by
introducing some graph theory that we need:

######  Lemma 125.

[Theorem 1 of [16]] Let $(V,E)$ be a graph with $n$ nodes, average degree
$d>2$ and girth $r$. Then $n\geq 2(d-2)^{r/2-2}$.

From Lemma 125 we conclude that for a graph with $o(\lvert\mathcal{G}\rvert)$
nodes and $\lvert\mathcal{G}\rvert$ edges, it is the case that the graph has a
girth of $O(\log(n))$. To see this, note that the average degree $d$ of such a
graph is $\omega(1)$ and thus it follows that for some constant $c>1$:

$\displaystyle o(\lvert\mathcal{G}\rvert)\geq 2(d-2)^{r/2-2}$
$\displaystyle\Rightarrow$ $\displaystyle o(\lvert\mathcal{G}\rvert)\gg
2(c)^{r/2}$ $\displaystyle\Rightarrow$ $\displaystyle r\in O(\log_{c}(n))$

Given any non-adaptive pre-processing algorithm with $T=2$,
$S=o(\lvert\mathcal{G}\rvert)$, and $w=1$, define $\mathcal{V}$ to be the set
of $S$ nodes each representing a memory cell and let $E$ be the set of edges
such that an edge $e_{g}=(u,v)$ is in the edge set if and only there exists
some group element $g\in\mathcal{G}$ such that the querying algorithm on input
$g$ accesses both memory cell $u$ and $v$. Furthermore, associate with each
edge $e_{g}$ a function $f_{g}:\\{0,1\\}^{2}\to\\{0,1\\}$ that defines the
output behaviour of the querying algorithm upon reading the bits at node $u$
and $v$. We broadly categorise the possible functions $f_{g}$ into $4$ types:

  1. 1.

Copy type functions. The type of functions $f_{g}$ that depend only one of its
two inputs. There are $4$ of such functions.

  2. 2.

Constant type functions. The type of functions $f_{g}$ that are completely
independent of its two inputs. There are $2$ such functions.

  3. 3.

AND type functions. The type of functions $f_{g}$ whose truth table is such
that exactly $3$ of the $4$ possible inputs leads to the same output where the
last input differs. There are $8$ such functions.

  4. 4.

XOR type functions. The type of functions $f_{g}$ that are either the XOR of
its $2$ inputs or the negation of the XOR of its $2$ inputs. There are $2$
such functions.

Note that none of the edges can be the constant type, since this means that
the querying algorithm’s answer is independent of the input set. Also, by an
averaging argument there is at least one type of function that
$\Omega(\lvert\mathcal{G}\rvert)$ edges are associated with. Furthermore,
Lemma 124 asserts that there can be at most $2$ edges that are parallel to
each other, otherwise we can construct an input distribution $D$ such that the
data structure manages to use $2$ bits to encode the outcome of a random
variable that has Shannon entropy at least $3$, which is a contradiction. Thus
there are $\Omega(\lvert\mathcal{G}\rvert)$ many edges that are not parallel
to each other and are all of the same type. We analyse the different types
separately. We start with the simplest COPY type:

(COPY type) Assuming that there are $\Omega(\lvert\mathcal{G}\rvert)$ edges
that are associated with the copy type function, there must exist at least one
node $u$ such that $\omega(1)$ edges $e_{g}$ are such that the associated
function $f_{g}$ depend only on the bit at this node. Letting $\mathcal{Q}$
contain two such group elements, this yields a contradiction using Lemma 124
to construct a distribution over $\mathcal{A}_{1}$ and $\mathcal{A}_{2}$ such
that the entropy of the two query answers in $\mathcal{Q}$ is $2$ bits.

For the remaining types, we look for a short cycle. Using Lemma 125, we get
that there is a cycle of $O(\log n)$ length using only edges associated with
functions of the same type. Denote by $\mathcal{Y}$ the set of group elements
$g$ such that $e_{g}$ is in the cycle and $y_{1},\ldots,y_{t}$ enumerates the
elements of $\mathcal{Y}$ based on a traversal of the cycle. That is, the edge
corresponding to $y_{i}$ shares endpoints with edges corresponding to
$y_{i-1}$ and $y_{i+1}$, where $y_{t+1}=y_{1}$ and $y_{0}=y_{t}$. We use Lemma
124 with $\mathcal{Q}=\mathcal{Y}$ to get a distribution $D$ over
$(\mathcal{A}_{1},\mathcal{A}_{2})$ such that the answers to queries in
$\mathcal{Y}$ are independent and they are all uniform random. We now handle
the two remaining types separately.

(AND type) Let $b$ be the output of $f_{y_{1}}$ that is only obtainable by
exactly $1$ of the $4$ possible inputs. Consider the distribution $D$
conditioned on the event that $\mathbbm{1}\\{{y_{1}\in(A_{1}+A_{2})}\\}=b$.
Since only $1$ of the $4$ inputs to $f_{y_{1}}$ is consistent with this
output, this fixes the two input bits to $f_{y_{1}}$. Therefore, there are
$t-2$ bits left to encode $t-1$ independent and fully random outputs (namely,
whether $y_{2},\ldots,y_{t}$ are in $A_{1}+A_{2}$), which yields us the
desired contradiction.

(XOR type) Let $(\mathcal{A}_{1},\mathcal{A}_{2})\sim D$ be drawn from the
input distribution constructed using Lemma 124 with $\mathcal{Q}=\mathcal{Y}$.
Let the endpoints of $y_{i}$ be $u_{i},v_{i}$, such that $v_{t}=u_{1}$. Note
for all $i$, it is necessarily the case that
$\mathbbm{1}\\{{y_{i}\in(\mathcal{A}_{1}+\mathcal{A}_{2})}\\}=u_{i}\oplus
v_{i}$ or
$\mathbbm{1}\\{{y_{i}\in(\mathcal{A}_{1}+\mathcal{A}_{2})}\\}=1\oplus
u_{i}\oplus v_{i}$. Then
$\bigoplus_{2}^{t}\mathbbm{1}\\{{y_{i}\in(A_{1}+A_{2})}\\}$ is either
$u_{1}\oplus v_{1}$ or $1\oplus u_{1}\oplus v_{1}$ which means that
$\mathbbm{1}\\{{y_{1}\in(\mathcal{A}_{1}+\mathcal{A}_{2})}\\}$ is either
$\bigoplus_{2}^{t}\mathbbm{1}\\{{y_{i}\in(\mathcal{A}_{1}+\mathcal{A}_{2})}\\}$
or its negation. Then Lemma 124 yields the desired contradiction.

##  Chapter 5 Conclusion and Future Work

###  1 Conclusion

In this thesis, we have worked on giving “negative” (or impossibility) results
in the form of randomness requirements for extensions of secret sharing, and
“positive” (or feasibility) results in the form of either giving privacy
amplification with better guarantees, or confirming a certain level of
security guarantees for one-way functions against pre-processing adversaries
from random oracles.

###  2 Future Work

####  1 Randomness Requirements

###### (Does plain secret sharing need extractable randomness?)

The main question posed by Dodis in [41] remains: Do we need extractable
randomness to share even a single bit to two parties? Given that secret
sharing is a fundamental cryptographic primitive used as a building block in
many other primitives, being able to find an answer to this will also shed
light on the complexity (in terms of randomness) of other primitives as well.

####  2 Non-malleable Extractors

###### (Even better entropy rates)

After our work, Li in [135] improved the entropy requirement from $>0.8n$ from
one source to $>\frac{2}{3}n$. This falls slightly short of the $\frac{1}{2}n$
threshold witnessed by the Raz extractor. Are we able to close the gap any
further to the halfway point? We also note that we get a $t$-non-malleable
extractor instead. As mentioned by [11], “good enough” $t$-non-malleable
extractors will yield a breakthrough in two-source extractors as well. While
our extractor falls short of accomplishing that, a question might be whether
our ideas can be improved upon to yield such an extractor.

###### (Better Multi-Tampering for Two-Source Extractors)

In Theorem 7 of [11], it was mentioned that two-source non-malleable
extractors that have entropy-rate $m(1-\gamma)-3\log(m)$ entropy in both
sources, and can handle $\frac{C_{\delta}}{\gamma^{5}})$ tamperings will lead
to two source extractors with for entropy rates $\delta n$. Both extractors
here in the statement extract a single bit.

Our extractor in Chapter 4, at a one-sided rate of $(1-\frac{1}{2t+3})$,
allows for $t$ tampering functions, instead of $t^{5}$ tamperings. On the
other hand, our very same extractor is lopsided (in that the other entropy
requirement is $\approx n^{\alpha}$, for any $\alpha>0$ in the second source).
Can we somehow perform a trade-off to increase the entropy requirement in the
second source to also increase the number of tampering functions that we can
allow for (from $t$ to $O(t^{5})$)?

####  3 Collision Resistant Extractors

###### (Improving the seed length for collision resistant extractors)

One other thing to note is that our result of constructing collision resistant
extractors from seeded extractors incurs a blowup in the seed by an _additive_
term of
$\log(1/\varepsilon)\log(1/\delta)\log^{2}(\log(1/\delta))$ for a collision
probability of $\delta$, and distance $\varepsilon$ from $m$ uniform bits.

Using Trevisan’s extractor [151], we note that for $\delta\leq\varepsilon$,
this additive term is dominated by the original seed length requirement of the
extractor anyway, and thus we get collision resistance “for free”. However,
Trevisan’s extractor excels at extracting $k$ bits from a source with min-
entropy $k$. If one were content with extracting $\Omega(k)$ bits instead,
they can use the GUV extractor from [107]. In this case, the seed requirement
is actually quadratically smaller — $d=O(\log(n)+\log(1/\varepsilon))$, and
thus our term dominates instead (by a factor of
$\log(1/\delta)\log^{2}(\log(1/\delta))$). It seems pretty clear from our
construction that we will not be able to shave off this additional factor. But
it does beg the question (since we were able to match, up to constant factors,
the parameters in the $m=k$ regime) whether it is also possible to create an
extractor with the same parameters as the GUV extractor, but while retaining
collision resillience?

####  4 Pre-processing Adversaries

###### (Improving lower bounds for $3$SUM-Indexing)

While we have some results based on the hardness of $3$SUM, this is far less
than desirable in a few ways:

  1. 1.

The lower bounds are worst-case hardness, rather than average case. For this
to be useful in a cryptographic setting, average case results would be
required. Can we get lower bounds for a random queries?

  2. 2.

The initial construction introduced by Guo et al. in [102] used $k$SUM. While
all confirmed hardness results used $3$SUM. Can we derive potentially stronger
results using $k$SUM?

  3. 3.

Our lower bounds only work in a low-space setting. Are we able to obtain lower
bounds for the other extreme: High space but low oracle access. One of our
results takes a step in this direction but still in a highly restricted
setting: non-adaptive, and for $T=2,w=1$. Can we at least increase $w$ to
$O(\log(n))$? What about $T=O(1)$?

We want to additionally note that slight improvements to the results will lead
to explicit circuit lower bounds (c.f. works by Dvir, Golovnev, and Weinstein
[87], and Viola [166]). Thus, we view our results as nearly tight without new
techniques.

## References

  * [1] Amir Abboud and Kevin Lewi  “Exact Weight Subgraphs and the k-Sum Conjecture”  In _Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I_ 7965, Lecture Notes in Computer Science  Springer, 2013, pp. 1–12  DOI: 10.1007/978-3-642-39206-1\\_1
  * [2] Divesh Aggarwal, Eldon Chung and Maciej Obremski  “Extractors: Low Entropy Requirements Colliding with Non-malleability”  In _Advances in Cryptology – CRYPTO 2023_ Cham: Springer Nature Switzerland, 2023, pp. 580–610
  * [3] Divesh Aggarwal, Eldon Chung, Maciej Obremski and João Ribeiro  “On Secret Sharing, Randomness, and Random-less Reductions for Secret Sharing”  In _Theory of Cryptography Conference_ , 2022, pp. 327–354  Springer
  * [4] Divesh Aggarwal, Ivan Damgård, Jesper Buus Nielsen, Maciej Obremski, Erick Purwanto, João Ribeiro and Mark Simkin  “Stronger Leakage-Resilient and Non-Malleable Secret Sharing Schemes for General Access Structures”  In _Advances in Cryptology – CRYPTO 2019_ Cham: Springer International Publishing, 2019, pp. 510–539
  * [5] Divesh Aggarwal, Yevgeniy Dodis, Tomasz Kazana and Maciej Obremski  “Non-Malleable Reductions and Applications”  In _Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing_ , STOC ’15  Portland, Oregon, USA: Association for Computing Machinery, 2015, pp. 459–468  DOI: 10.1145/2746539.2746544
  * [6] Divesh Aggarwal, Yevgeniy Dodis and Shachar Lovett  “Non-malleable codes from additive combinatorics”  In _SIAM Journal on Computing_ 47.2 SIAM, 2018, pp. 524–546
  * [7] Divesh Aggarwal, Kaave Hosseini and Shachar Lovett  “Affine-malleable extractors, spectrum doubling, and application to privacy amplification”  In _2016 IEEE International Symposium on Information Theory (ISIT)_ , 2016, pp. 2913–2917  Ieee
  * [8] Divesh Aggarwal, Bhavana Kanukurthi, Sai Lakshmi Bhavana Obbattu, Maciej Obremski and Sruthi Sekar  “Rate one-third non-malleable codes”  In _Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing_ , STOC 2022  Rome, Italy: Association for Computing Machinery, 2022, pp. 1364–1377  DOI: 10.1145/3519935.3519972
  * [9] Divesh Aggarwal, Tomasz Kazana and Maciej Obremski  “Inception Makes Non-malleable Codes Stronger”  In _Theory of Cryptography_ Cham: Springer International Publishing, 2017, pp. 319–343
  * [10] Divesh Aggarwal and Maciej Obremski  “A constant rate non-malleable code in the split-state model”  In _2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)_ , 2020, pp. 1285–1294  DOI: 10.1109/FOCS46700.2020.00122
  * [11] Divesh Aggarwal, Maciej Obremski, João Ribeiro, Mark Simkin and Luisa Siniscalchi  “Privacy Amplification With Tamperable Memory via Non-Malleable Two-Source Extractors”  In _IEEE Transactions on Information Theory_ 68.8, 2022, pp. 5475–5495  DOI: 10.1109/TIT.2022.3167404
  * [12] Divesh Aggarwal, Maciej Obremski, João Ribeiro, Luisa Siniscalchi and Ivan Visconti  “How to Extract Useful Randomness from Unreliable Sources”  In _Advances in Cryptology – EUROCRYPT 2020_ Cham: Springer International Publishing, 2020, pp. 343–372
  * [13] Dakshi Agrawal, Bruce Archambeault, Josyula R. Rao and Pankaj Rohatgi  “The EM Side-Channel(s)”  In _Revised Papers from the 4th International Workshop on Cryptographic Hardware and Embedded Systems_ , CHES ’02  Berlin, Heidelberg: Springer-Verlag, 2002, pp. 29–45
  * [14] Adi Akavia, Shafi Goldwasser and Vinod Vaikuntanathan  “Simultaneous Hardcore Bits and Cryptography against Memory Attacks”  In _Theory of Cryptography_ Berlin, Heidelberg: Springer Berlin Heidelberg, 2009, pp. 474–495
  * [15] N. Alon, O. Goldreich, J. Hastad and R. Peralta  “Simple construction of almost k-wise independent random variables”  In _Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science_ , 1990, pp. 544–553 vol.2  DOI: 10.1109/FSCS.1990.89575
  * [16] Noga Alon, Shlomo Hoory and Nathan Linial  “The Moore bound for irregular graphs”  In _Graphs and Combinatorics_ 18.1 Springer, 2002, pp. 53–57
  * [17] Stephen Alstrup, Thore Husfeldt and Theis Rauhe  “Marked Ancestor Problems”  In _39th Annual Symposium on Foundations of Computer Science, FOCS ’98, November 8-11, 1998, Palo Alto, California, USA_ IEEE Computer Society, 1998, pp. 534–544  DOI: 10.1109/SFCS.1998.743504
  * [18] Amihood Amir, Timothy M. Chan, Moshe Lewenstein and Noa Lewenstein  “On Hardness of Jumbled Indexing”  In _Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I_ 8572, Lecture Notes in Computer Science  Springer, 2014, pp. 114–125  DOI: 10.1007/978-3-662-43948-7\\_10
  * [19] Gorka Irazoqui Apecechea, Mehmet Sinan Inci, Thomas Eisenbarth and Berk Sunar  “Wait a Minute! A fast, Cross-VM Attack on AES.”  In _RAID_ 8688, 2014, pp. 299–319
  * [20] C Ashokkumar, Ravi Prakash Giri and Bernard Menezes  “Highly efficient algorithms for AES key retrieval in cache access attacks”  In _2016 IEEE European symposium on security and privacy (EuroS &P)_, 2016, pp. 261–275  IEEE
  * [21] Giuseppe Ateniese, Danilo Francati, Bernardo Magri and Daniele Venturi  “Public Immunization Against Complete Subversion Without Random Oracles”  In _Applied Cryptography and Network Security_ Cham: Springer International Publishing, 2019, pp. 465–485
  * [22] Per Austrin, Kai-Min Chung, Mohammad Mahmoody, Rafael Pass and Karn Seth  “On the Impossibility of Cryptography with Tamperable Randomness”  In _Advances in Cryptology – CRYPTO 2014_ Berlin, Heidelberg: Springer Berlin Heidelberg, 2014, pp. 462–479
  * [23] Michael Backes, Aniket Kate, Sebastian Meiser and Tim Ruffing  “Secrecy Without Perfect Randomness: Cryptography with (Bounded) Weak Sources”  In _Applied Cryptography and Network Security_ Cham: Springer International Publishing, 2015, pp. 675–695
  * [24] B. Barak  “Constant-round coin-tossing with a man in the middle or realizing the shared random string model”  In _The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings._ , 2002, pp. 345–355  DOI: 10.1109/SFCS.2002.1181957
  * [25] Gill Barequet and Sariel Har-Peled  “Polygon Containment and Translational Min-Hausdorff-Distance Between Segment Sets are 3SUM-Hard”  In _Int. J. Comput. Geom. Appl._ 11.4, 2001, pp. 465–474  DOI: 10.1142/S0218195901000596
  * [26] Balthazar Bauer, Pooya Farshim and Sogol Mazaheri  “Combiners for Backdoored Random Oracles”  In _Advances in Cryptology – CRYPTO 2018_ Cham: Springer International Publishing, 2018, pp. 272–302
  * [27] M. Bellare and J. Rompel  “Randomness-Efficient Oblivious Sampling”  In _Proceedings of the 35th Annual Symposium on Foundations of Computer Science_ , SFCS ’94  USA: IEEE Computer Society, 1994, pp. 276–287  DOI: 10.1109/SFCS.1994.365687
  * [28] Mihir Bellare, Zvika Brakerski, Moni Naor, Thomas Ristenpart, Gil Segev, Hovav Shacham and Scott Yilek  “Hedged Public-Key Encryption: How to Protect against Bad Randomness”  In _Advances in Cryptology – ASIACRYPT 2009_ Berlin, Heidelberg: Springer Berlin Heidelberg, 2009, pp. 232–249
  * [29] Avraham Ben-Aroya, Eshan Chattopadhyay, Dean Doron, Xin Li and Amnon Ta-Shma  “A New Approach for Constructing Low-error, Two-source Extractors”  In _Proceedings of the 33rd Computational Complexity Conference_ , CCC ’18  San Diego, California: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018, pp. 3:1–3:19
  * [30] Avraham Ben-Aroya, Dean Doron and Amnon Ta-Shma  “An Efficient Reduction from Two-Source to Non-Malleable Extractors: Achieving near-Logarithmic Min-Entropy”  In _Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing_ , STOC 2017  Montreal, Canada: Association for Computing Machinery, 2017, pp. 1185–1194
  * [31] Michael Ben-Or, Shafi Goldwasser and Avi Wigderson  “Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation”  In _Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing_ , STOC ’88  Chicago, Illinois, USA: Association for Computing Machinery, 1988, pp. 1–10  DOI: 10.1145/62212.62213
  * [32] Josh Benaloh and Jerry Leichter  “Generalized Secret Sharing and Monotone Functions”  In _Advances in Cryptology - CRYPTO ’88, 8th Annual International Cryptology Conference, Santa Barbara, California, USA, August 21-25, 1988, Proceedings_ 403, Lecture Notes in Computer Science  Springer, 1988, pp. 27–35  DOI: 10.1007/0-387-34799-2\\_3
  * [33] Fabrice Benhamouda, Akshay Degwekar, Yuval Ishai and Tal Rabin  “On the Local Leakage Resilience of Linear Secret Sharing Schemes”  In _J. Cryptol._ 34.2, 2021, pp. 10  DOI: 10.1007/s00145-021-09375-2
  * [34] Charles H. Bennett, Gilles Brassard, Claude Crépeau and Marie-Hélène Skubiszewska  “Practical Quantum Oblivious Transfer”  In _Advances in Cryptology — CRYPTO ’91_ Berlin, Heidelberg: Springer Berlin Heidelberg, 1992, pp. 351–366
  * [35] Charles H. Bennett, Gilles Brassard and Jean-Marc Robert  “Privacy Amplification by Public Discussion”  In _SIAM Journal on Computing_ 17.2, 1988, pp. 210–229  DOI: 10.1137/0217014
  * [36] Abhishek Bhowmick, Ariel Gabizon, Thái Hoàng Lê and David Zuckerman  “Deterministic Extractors for Additive Sources: Extended Abstract”  In _Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS 2015, Rehovot, Israel, January 11-13, 2015_ ACM, 2015, pp. 277–286  DOI: 10.1145/2688073.2688090
  * [37] G.. BLAKLEY  “Safeguarding cryptographic keys”  In _1979 International Workshop on Managing Requirements Knowledge (MARK)_ , 1979, pp. 313–318  DOI: 10.1109/MARK.1979.8817296
  * [38] Manuel Blum  “Independent unbiased coin flips from a correlated biased source—a finite state Markov chain”  In _Combinatorica_ 6.2 Springer, 1986, pp. 97–108
  * [39] Dan Boneh, Richard A. Demillo and Richard J. Lipton  “On the Importance of Eliminating Errors in Cryptographic Computations”  In _J. Cryptol._ 14.2 Berlin, Heidelberg: Springer-Verlag, 2001, pp. 101–119  DOI: 10.1007/s001450010016
  * [40] Joseph Boninger, Joshua Brody and Owen Kephart  “Non-Adaptive Data Structure Bounds for Dynamic Predecessor”  In _37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017, December 11-15, 2017, Kanpur, India_ 93, LIPIcs  Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, pp. 20:1–20:12  DOI: 10.4230/LIPIcs.FSTTCS.2017.20
  * [41] Carl Bosley and Yevgeniy Dodis  “Does Privacy Require True Randomness?”  In _Theory of Cryptography_ Berlin, Heidelberg: Springer Berlin Heidelberg, 2007, pp. 1–20
  * [42] Jean Bourgain  “More on the sum-product phenomenon in prime fields and its applications”  In _International Journal of Number Theory_ 1.01 World Scientific, 2005, pp. 1–32
  * [43] Jean Bourgain  “On the construction of affine extractors”  In _GAFA Geometric And Functional Analysis_ 17.1 Springer, 2007, pp. 33–57
  * [44] G. Brassard, C. Crepeau, R. Jozsa and D. Langlois  “A quantum bit commitment scheme provably unbreakable by both parties”  In _Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science_ , 1993, pp. 362–371  DOI: 10.1109/SFCS.1993.366851
  * [45] Gerth Stølting Brodal and Kasper Green Larsen  “Optimal Planar Orthogonal Skyline Counting Queries”  In _Algorithm Theory - SWAT 2014 - 14th Scandinavian Symposium and Workshops, Copenhagen, Denmark, July 2-4, 2014. Proceedings_ 8503, Lecture Notes in Computer Science  Springer, 2014, pp. 110–121  DOI: 10.1007/978-3-319-08404-6\\_10
  * [46] Joshua Brody and Kasper Green Larsen  “Adapt or Die: Polynomial Lower Bounds for Non-Adaptive Dynamic Data Structures”  In _Theory Comput._ 11, 2015, pp. 471–489  DOI: 10.4086/toc.2015.v011a019
  * [47] Ran Canetti, Yevgeniy Dodis, Shai Halevi, Eyal Kushilevitz and Amit Sahai  “Exposure-Resilient Functions and All-or-Nothing Transforms”  In _Advances in Cryptology - EUROCRYPT 2000, International Conference on the Theory and Application of Cryptographic Techniques, Bruges, Belgium, May 14-18, 2000, Proceeding_ 1807, Lecture Notes in Computer Science  Springer, 2000, pp. 453–469  DOI: 10.1007/3-540-45539-6\\_33
  * [48] Ran Canetti, Rafael Pass and Abhi Shelat  “Cryptography from Sunspots: How to Use an Imperfect Reference String”  In _48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07)_ , 2007, pp. 249–259  DOI: 10.1109/FOCS.2007.70
  * [49] Timothy M. Chan  “More Logarithmic-Factor Speedups for 3SUM, (median, +)-Convolution, and Some Geometric 3SUM-Hard Problems”  In _Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018_ SIAM, 2018, pp. 881–897  DOI: 10.1137/1.9781611975031.57
  * [50] Eshan Chattopadhyay  “A Recipe for Constructing Two-Source Extractors”, 2020
  * [51] Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Ashutosh Kumar, Xin Li, Raghu Meka and David Zuckerman  “Extractors and Secret Sharing Against Bounded Collusion Protocols”  In _2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)_ , 2020, pp. 1226–1242  DOI: 10.1109/FOCS46700.2020.00117
  * [52] Eshan Chattopadhyay, Vipul Goyal and Xin Li  “Nonmalleable Extractors and Codes, with Their Many Tampered Extensions”  In _SIAM Journal on Computing_ 49.5, 2020, pp. 999–1040  DOI: 10.1137/18M1176622
  * [53] Eshan Chattopadhyay, Bhavana Kanukurthi, Sai Lakshmi Bhavana Obbattu and Sruthi Sekar  “Privacy Amplification from Non-malleable Codes”  In _Progress in Cryptology – INDOCRYPT 2019_ Cham: Springer International Publishing, 2019, pp. 318–337
  * [54] Eshan Chattopadhyay and Xin Li  “Extractors for sumset sources”  In _Proceedings of the forty-eighth annual ACM symposium on Theory of Computing_ , 2016, pp. 299–311  ACM
  * [55] Eshan Chattopadhyay and David Zuckerman  “Explicit two-source extractors and resilient functions”  In _Annals of Mathematics_ 189.3 [Annals of Mathematics, Trustees of Princeton University on Behalf of the Annals of Mathematics, Mathematics Department, Princeton University], 2019, pp. 653–705  URL: https://www.jstor.org/stable/10.4007/annals.2019.189.3.1
  * [56] David Chaum, Claude Crépeau and Ivan Damgard  “Multiparty Unconditionally Secure Protocols”  In _Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing_ , STOC ’88  Chicago, Illinois, USA: Association for Computing Machinery, 1988, pp. 11–19  DOI: 10.1145/62212.62214
  * [57] Mahdi Cheraghchi and Venkatesan Guruswami  “Non-malleable Coding Against Bit-Wise and Split-State Tampering”  In _Journal of Cryptology_ 30.1, 2017, pp. 191–241
  * [58] Benny Chor and Oded Goldreich  “Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity”  In _SIAM Journal on Computing_ 17.2, 1988, pp. 230–261  DOI: 10.1137/0217015
  * [59] Benny Chor, Oded Goldreich, Johan Håstad, Jeol Friedman, Steven Rudich and Roman Smolensky  “The Bit Extraction Problem or $t$-resilient Functions”  In _Proceedings of the 26th IEEE Symposium on Foundation of Computer Science_ , 1985, pp. 396–407
  * [60] Eldon Chung and Kasper Green Larsen  “Stronger 3SUM-Indexing Lower Bounds”  In _Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)_ , pp. 444–455  DOI: 10.1137/1.9781611977554.ch19
  * [61] Gil Cohen  “Towards Optimal Two-Source Extractors and Ramsey Graphs”  In _Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing_ , STOC 2017  Montreal, Canada: Association for Computing Machinery, 2017, pp. 1157–1170  DOI: 10.1145/3055399.3055429
  * [62] Gil Cohen, Ran Raz and Gil Segev  “Nonmalleable extractors with short seeds and applications to privacy amplification”  In _SIAM Journal on Computing_ 43.2 SIAM, 2014, pp. 450–476
  * [63] Ronald Cramer, Ivan Bjerre Damgård and Jesper Buus Nielsen  “MPC from General Linear Secret-Sharing Schemes”  In _Secure Multiparty Computation and Secret Sharing_ Cambridge University Press, 2015, pp. 139–158  DOI: 10.1017/CBO9781107337756.007
  * [64] Ronald Cramer, Ivan Bjerre Damgård and Jesper Buus Nielsen  “Secure Multiparty Computation and Secret Sharing”  Cambridge University Press, 2015  DOI: 10.1017/CBO9781107337756
  * [65] Francesco Davì, Stefan Dziembowski and Daniele Venturi  “Leakage-Resilient Storage”  In _Security and Cryptography for Networks_ Berlin, Heidelberg: Springer Berlin Heidelberg, 2010, pp. 121–137
  * [66] Anindya De, Luca Trevisan and Madhur Tulsiani  “Time space tradeoffs for attacks against one-way functions and PRGs”  In _Annual Cryptology Conference_ , 2010, pp. 649–665  Springer
  * [67] Erik D. Demaine and Salil P. Vadhan  “Some notes on 3SUM” Unpublished manuscript, 2001
  * [68] Yvo Desmedt and Yair Frankel  “Shared generation of authenticators and signatures”  In _Advances in Cryptology — CRYPTO ’91_ Berlin, Heidelberg: Springer Berlin Heidelberg, 1992, pp. 457–469
  * [69] Giovanni Di Crescenzo, Richard Lipton and Shabsi Walfish  “Perfectly Secure Password Protocols in the Bounded Retrieval Model”  In _Theory of Cryptography_ Berlin, Heidelberg: Springer Berlin Heidelberg, 2006, pp. 225–244
  * [70] Yevgeniy Dodis  “Exposure-resilient cryptography”, 2000
  * [71] Yevgeniy Dodis, Chaya Ganesh, Alexander Golovnev, Ari Juels and Thomas Ristenpart  “A Formal Treatment of Backdoored Pseudorandom Generators”  In _Advances in Cryptology – EUROCRYPT 2015_ Berlin, Heidelberg: Springer Berlin Heidelberg, 2015, pp. 101–126
  * [72] Yevgeniy Dodis, Bhavana Kanukurthi, Jonathan Katz, Leonid Reyzin and Adam Smith  “Robust Fuzzy Extractors and Authenticated Key Agreement from Close Secrets”  In _IEEE Transactions on Information Theory_ , 2012
  * [73] Yevgeniy Dodis, Xin Li, Trevor D. Wooley and David Zuckerman  “Privacy Amplification and Nonmalleable Extractors Via Character Sums”  In _SIAM Journal on Computing_ 43.2, 2014, pp. 800–830  DOI: 10.1137/120868414
  * [74] Yevgeniy Dodis, Adriana López-Alt, Ilya Mironov and Salil Vadhan  “Differential Privacy with Imperfect Randomness”  In _Advances in Cryptology – CRYPTO 2012_ Berlin, Heidelberg: Springer Berlin Heidelberg, 2012, pp. 497–516
  * [75] Yevgeniy Dodis, Shien Jin Ong, Manoj Prabhakaran and Amit Sahai  “On the (im)possibility of cryptography with imperfect randomness”  In _45th Annual IEEE Symposium on Foundations of Computer Science_ , 2004, pp. 196–205  DOI: 10.1109/FOCS.2004.44
  * [76] Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin and Adam Smith  “Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data”  In _SIAM Journal on Computing_ 38.1, 2008, pp. 97–139
  * [77] Yevgeniy Dodis, Krzysztof Pietrzak and Bartosz Przydatek  “Separating Sources for Encryption and Secret Sharing”  In _Theory of Cryptography_ Berlin, Heidelberg: Springer Berlin Heidelberg, 2006, pp. 601–616
  * [78] Yevgeniy Dodis and Joel Spencer  “On the (non)universality of the one-time pad”  In _43rd Annual IEEE Symposium on Foundations of Computer Science_ , 2002, pp. 376–385  DOI: 10.1109/SFCS.2002.1181962
  * [79] Yevgeniy Dodis and Daniel Wichs  “Non-malleable Extractors and Symmetric Key Cryptography from Weak Secrets”  In _Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing_ , STOC ’09  Bethesda, MD, USA: ACM, 2009, pp. 601–610
  * [80] Yevgeniy Dodis and Yanqing Yao  “Privacy with Imperfect Randomness”  In _Advances in Cryptology – CRYPTO 2015_ Berlin, Heidelberg: Springer Berlin Heidelberg, 2015, pp. 463–482
  * [81] Yevgeniy Dodis and Yu Yu  “Overcoming Weak Expectations”  In _Theory of Cryptography_ Berlin, Heidelberg: Springer Berlin Heidelberg, 2013, pp. 1–22
  * [82] Danny Dolev, Cynthia Dwork and Moni Naor  “Non-malleable cryptography”  In _Proceedings of the twenty-third annual ACM symposium on Theory of computing_ , 1991, pp. 542–552
  * [83] Danny Dolev, Cynthia Dwork and Moni Naor  “Nonmalleable Cryptography”  In _SIAM Review_ 45.4, 2003, pp. 727–784  DOI: 10.1137/S0036144503429856
  * [84] Zeev Dvir  “Extractors for varieties”  In _Comput. Complex._ 21.4, 2012, pp. 515–572  DOI: 10.1007/s00037-011-0023-3
  * [85] Zeev Dvir, Ariel Gabizon and Avi Wigderson  “Extractors And Rank Extractors For Polynomial Sources”  In _Comput. Complex._ 18.1, 2009, pp. 1–58  DOI: 10.1007/s00037-009-0258-4
  * [86] Zeev Dvir, Alexander Golovnev and Omri Weinstein  “Static data structure lower bounds imply rigidity”  In _Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019_ ACM, 2019, pp. 967–978  DOI: 10.1145/3313276.3316348
  * [87] Zeev Dvir, Alexander Golovnev and Omri Weinstein  “Static data structure lower bounds imply rigidity”  In _Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing_ , STOC 2019  Phoenix, AZ, USA: Association for Computing Machinery, 2019, pp. 967–978  DOI: 10.1145/3313276.3316348
  * [88] Stefan Dziembowski  “Intrusion-Resilience Via the Bounded-Storage Model”  In _Theory of Cryptography_ Berlin, Heidelberg: Springer Berlin Heidelberg, 2006, pp. 207–224
  * [89] Stefan Dziembowski and Sebastian Faust  “Leakage-resilient cryptography from the inner-product extractor”  In _International Conference on the Theory and Application of Cryptology and Information Security_ , 2011, pp. 702–721  Springer
  * [90] Stefan Dziembowski, Tomasz Kazana and Maciej Obremski  “Non-malleable codes from two-source extractors”  In _Annual Cryptology Conference_ , 2013, pp. 239–257  Springer
  * [91] Stefan Dziembowski and Krzysztof Pietrzak  “Leakage-Resilient Cryptography”  In _2008 49th Annual IEEE Symposium on Foundations of Computer Science_ , 2008, pp. 293–302  DOI: 10.1109/FOCS.2008.56
  * [92] Stefan Dziembowski, Krzysztof Pietrzak and Daniel Wichs  “Non-Malleable Codes”  In _J. ACM_ 65.4 New York, NY, USA: Association for Computing Machinery, 2018  DOI: 10.1145/3178432
  * [93] Paul Erdös, Peter Frankl and Zoltán Füredi  “Families of finite sets in which no set is covered by the union of $r$ others”  In _Israel Journal of Mathematics_ 51.1-2 Springer, 1985, pp. 79–89
  * [94] Daniel Escudero  “An Introduction to Secret-Sharing-Based Secure Multiparty Computation” https://eprint.iacr.org/2022/062, Cryptology ePrint Archive, Paper 2022/062, 2022  URL: https://eprint.iacr.org/2022/062
  * [95] Sebastian Faust, Pratyay Mukherjee, Jesper Buus Nielsen and Daniele Venturi  “Continuous Non-malleable Codes”  In _Theory of Cryptography_ Berlin, Heidelberg: Springer Berlin Heidelberg, 2014, pp. 465–488
  * [96] Amos Fiat and Moni Naor  “Rigorous Time/Space Tradeoffs for Inverting Functions”  In _Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, May 5-8, 1991, New Orleans, Louisiana, USA_ ACM, 1991, pp. 534–541  DOI: 10.1145/103418.103473
  * [97] Amos Fiat and Moni Naor  “Rigorous time/space trade-offs for inverting functions”  In _SIAM Journal on Computing_ 29.3 SIAM, 2000, pp. 790–803
  * [98] Marc Fischlin, Christian Janson and Sogol Mazaheri  “Backdoored hash functions: immunizing HMAC and HKDF”  In _2018 IEEE 31st Computer Security Foundations Symposium (CSF)_ , 2018, pp. 105–118  IEEE
  * [99] Anka Gajentaan and Mark H. Overmars  “On a class of O(n${}^{\mbox{2}}$) problems in computational geometry”  In _Comput. Geom._ 45.4, 2012, pp. 140–152  DOI: 10.1016/j.comgeo.2011.11.006
  * [100] Oded Goldreich  “Three XOR-Lemmas — An Exposition”  In _Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation_ Springer Berlin Heidelberg, 2011, pp. 248–272  DOI: 10.1007/978-3-642-22670-0_22
  * [101] Isaac Goldstein, Tsvi Kopelowitz, Moshe Lewenstein and Ely Porat  “Conditional Lower Bounds for Space/Time Tradeoffs”  In _Algorithms and Data Structures - 15th International Symposium, WADS 2017, St. John’s, NL, Canada, July 31 - August 2, 2017, Proceedings_ 10389, Lecture Notes in Computer Science  Springer, 2017, pp. 421–436  DOI: 10.1007/978-3-319-62127-2\\_36
  * [102] Alexander Golovnev, Siyao Guo, Thibaut Horel, Sunoo Park and Vinod Vaikuntanathan  “Data Structures Meet Cryptography: 3SUM with Preprocessing”  In _Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing_ , STOC 2020  Chicago, IL, USA: Association for Computing Machinery, 2020, pp. 294–307  DOI: 10.1145/3357713.3384342
  * [103] Vipul Goyal and Ashutosh Kumar  “Non-Malleable Secret Sharing”  In _Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing_ , STOC 2018  Los Angeles, CA, USA: Association for Computing Machinery, 2018, pp. 685–698
  * [104] Vipul Goyal, Omkant Pandey and Silas Richelson  “Textbook non-malleable commitments”  In _Proceedings of the forty-eighth annual ACM symposium on Theory of Computing_ , 2016, pp. 1128–1141
  * [105] Vipul Goyal, Akshayaram Srinivasan and Chenzhi Zhu  “Multi-Source Non-Malleable Extractors and Applications”  In _Eurocrypt_ , 2021
  * [106] Mark Greve, Allan Grønlund Jørgensen, Kasper Dalgaard Larsen and Jakob Truelsen  “Cell Probe Lower Bounds and Approximations for Range Mode”  In _Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part I_ 6198, Lecture Notes in Computer Science  Springer, 2010, pp. 605–616  DOI: 10.1007/978-3-642-14165-2\\_51
  * [107] Venkatesan Guruswami, Christopher Umans and Salil Vadhan  “Unbalanced Expanders and Randomness Extractors from Parvaresh–Vardy Codes”  In _J. ACM_ 56.4 New York, NY, USA: Association for Computing Machinery, 2009  DOI: 10.1145/1538902.1538904
  * [108] Iftach Haitner and Omer Reingold  “Statistically-hiding commitment from any one-way function”  In _Proceedings of the thirty-ninth annual ACM symposium on Theory of computing_ , 2007, pp. 1–10
  * [109] J Alex Halderman, Seth D Schoen, Nadia Heninger, William Clarkson, William Paul, Joseph A Calandrino, Ariel J Feldman, Jacob Appelbaum and Edward W Felten  “Lest we remember: cold-boot attacks on encryption keys”  In _Communications of the ACM_ 52.5 ACM New York, NY, USA, 2009, pp. 91–98
  * [110] Carmit Hazay, Muthuramakrishnan Venkitasubramaniam and Mor Weiss  “ZK-PCPs from leakage-resilient secret sharing”  In _Journal of Cryptology_ 35.4 Springer, 2022, pp. 23
  * [111] Martin Hellman  “A cryptanalytic time-memory trade-off”  In _IEEE transactions on Information Theory_ 26.4 IEEE, 1980, pp. 401–406
  * [112] Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai and Thatchaphol Saranurak  “Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture”  In _Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015_ ACM, 2015, pp. 21–30  DOI: 10.1145/2746539.2746609
  * [113] Thomas Holenstein  “Pseudorandom generators from one-way functions: A simple construction for any hardness”  In _Theory of Cryptography Conference_ , 2006, pp. 443–461  Springer
  * [114] R. Impagliazzo and S. Rudich  “Limits on the Provable Consequences of One-Way Permutations”  In _Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing_ , STOC ’89  Seattle, Washington, USA: Association for Computing Machinery, 1989, pp. 44–61  DOI: 10.1145/73007.73012
  * [115] Yuval Ishai, Amit Sahai and David Wagner  “Private circuits: Securing hardware against probing attacks”  In _Advances in Cryptology-CRYPTO 2003: 23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 2003. Proceedings 23_ , 2003, pp. 463–481  Springer
  * [116] Thomas Johansson, Gregory Kabatianskii and Ben J.. Smeets  “On the Relation between A-Codes and Codes Correcting Independent Errors”  In _Advances in Cryptology - EUROCRYPT ’93, Workshop on the Theory and Application of of Cryptographic Techniques, Lofthus, Norway, May 23-27, 1993, Proceedings_ , 1993, pp. 1–11
  * [117] Yael Tauman Kalai and Leonid Reyzin  “A survey of leakage-resilient cryptography”  In _Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali_ , 2019, pp. 727–794
  * [118] Jesse Kamp, Anup Rao, Salil P. Vadhan and David Zuckerman  “Deterministic extractors for small-space sources”  In _J. Comput. Syst. Sci._ 77.1, 2011, pp. 191–220  DOI: 10.1016/j.jcss.2010.06.014
  * [119] Yoongu Kim, Ross Daly, Jeremie Kim, Chris Fallin, Ji Hye Lee, Donghyuk Lee, Chris Wilkerson, Konrad Lai and Onur Mutlu  “Flipping Bits in Memory without Accessing Them: An Experimental Study of DRAM Disturbance Errors”  In _SIGARCH Comput. Archit. News_ 42.3 New York, NY, USA: Association for Computing Machinery, 2014, pp. 361–372  DOI: 10.1145/2678373.2665726
  * [120] Yoongu Kim, Ross Daly, Jeremie Kim, Chris Fallin, Ji Hye Lee, Donghyuk Lee, Chris Wilkerson, Konrad Lai and Onur Mutlu  “Flipping bits in memory without accessing them: An experimental study of DRAM disturbance errors”  In _ACM SIGARCH Computer Architecture News_ 42.3 ACM New York, NY, USA, 2014, pp. 361–372
  * [121] Paul Kocher, Jann Horn, Anders Fogh, Daniel Genkin, Daniel Gruss, Werner Haas, Mike Hamburg, Moritz Lipp, Stefan Mangard and Thomas Prescher  “Spectre attacks: Exploiting speculative execution”  In _Communications of the ACM_ 63.7 ACM New York, NY, USA, 2020, pp. 93–101
  * [122] Paul Kocher, Joshua Jaffe and Benjamin Jun  “Differential power analysis”  In _Advances in Cryptology—CRYPTO’99: 19th Annual International Cryptology Conference Santa Barbara, California, USA, August 15–19, 1999 Proceedings 19_ , 1999, pp. 388–397  Springer
  * [123] Tsvi Kopelowitz, Seth Pettie and Ely Porat  “Higher Lower Bounds from the 3SUM Conjecture”  In _Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016_ SIAM, 2016, pp. 1272–1287  DOI: 10.1137/1.9781611974331.ch89
  * [124] Ashutosh Kumar, Raghu Meka and Amit Sahai  “Leakage-Resilient Secret Sharing Against Colluding Parties”  In _2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)_ , 2019, pp. 636–660  DOI: 10.1109/FOCS.2019.00045
  * [125] Kasper Green Larsen  “Higher Cell Probe Lower Bounds for Evaluating Polynomials”  In _53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012_ IEEE Computer Society, 2012, pp. 293–301  DOI: 10.1109/FOCS.2012.21
  * [126] Kasper Green Larsen  “The cell probe complexity of dynamic range counting”  In _Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012_ ACM, 2012, pp. 85–94  DOI: 10.1145/2213977.2213987
  * [127] Kasper Green Larsen, Jonathan Lindegaard Starup and Jesper Steensgaard  “Further Unifying the Landscape of Cell Probe Lower Bounds”  In _4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference, January 11-12, 2021_ SIAM, 2021, pp. 224–231  DOI: 10.1137/1.9781611976496.25
  * [128] Kasper Green Larsen, Omri Weinstein and Huacheng Yu  “Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds”  In _SIAM J. Comput._ 49.5, 2020  DOI: 10.1137/18M1198429
  * [129] Rio LaVigne, Andrea Lincoln and Virginia Vassilevska Williams  “Public-key cryptography in the fine-grained setting”  In _Annual International Cryptology Conference_ , 2019, pp. 605–635  Springer
  * [130] Mark Lewko  “AN EXPLICIT TWO-SOURCE EXTRACTOR WITH MIN-ENTROPY RATE NEAR $4/9$”  In _Mathematika_ 65.4 London Mathematical Society, 2019, pp. 950–957  DOI: 10.1112/S0025579319000238
  * [131] Xin Li  “Non-malleable Extractors, Two-Source Extractors and Privacy Amplification”  In _2012 IEEE 53rd Annual Symposium on Foundations of Computer Science_ , 2012, pp. 688–697  DOI: 10.1109/FOCS.2012.26
  * [132] Xin Li  “Improved Two-Source Extractors, and Affine Extractors for Polylogarithmic Entropy”  In _2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)_ , 2016, pp. 168–177  DOI: 10.1109/FOCS.2016.26
  * [133] Xin Li  “Improved Non-Malleable Extractors, Non-Malleable Codes and Independent Source Extractors”  In _Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing_ , STOC 2017  Montreal, Canada: Association for Computing Machinery, 2017, pp. 1144–1156  DOI: 10.1145/3055399.3055486
  * [134] Xin Li  “Non-Malleable Extractors and Non-Malleable Codes: Partially Optimal Constructions”  In _Proceedings of the 34th Computational Complexity Conference_ , CCC ’19  New Brunswick, New Jersey: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2020  DOI: 10.4230/LIPIcs.CCC.2019.28
  * [135] Xin Li  “Two source extractors for asymptotically optimal entropy, and (many) more”  In _2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)_ , 2023, pp. 1271–1281  IEEE
  * [136] David Lichtenstein, Nathan Linial and Michael Saks  “Some Extremal Problems Arising from Discrete Control Processes”  In _Combinatorica_ 9.3, 1989, pp. 269–287
  * [137] Fuchun Lin, Mahdi Cheraghchi, Venkatesan Guruswami, Reihaneh Safavi-Naini and Huaxiong Wang  “Leakage-Resilient Secret Sharing in Non-Compartmentalized Models”  In _1st Conference on Information-Theoretic Cryptography (ITC 2020)_ 163, Leibniz International Proceedings in Informatics (LIPIcs)  Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2020, pp. 7:1–7:24  DOI: 10.4230/LIPIcs.ITC.2020.7
  * [138] Moritz Lipp, Michael Schwarz, Daniel Gruss, Thomas Prescher, Werner Haas, Jann Horn, Stefan Mangard, Paul Kocher, Daniel Genkin and Yuval Yarom  “Meltdown: Reading kernel memory from user space”  In _Communications of the ACM_ 63.6 ACM New York, NY, USA, 2020, pp. 46–56
  * [139] Hemanta K. Maji, Anat Paskin-Cherniavsky, Tom Suad and Mingyuan Wang  “Constructing Locally Leakage-Resilient Linear Secret-Sharing Schemes”  In _Advances in Cryptology – CRYPTO 2021_ Cham: Springer International Publishing, 2021, pp. 779–808
  * [140] Ueli Maurer and Stefan Wolf  “Privacy amplification secure against active adversaries”  In _Advances in Cryptology — CRYPTO ’97_ Berlin, Heidelberg: Springer Berlin Heidelberg, 1997, pp. 307–321
  * [141] James L. McInnes and Benny Pinkas  “On the Impossibility of Private Key Cryptography with Weakly Random Keys”  In _Advances in Cryptology-CRYPTO’ 90_ Berlin, Heidelberg: Springer Berlin Heidelberg, 1991, pp. 421–435
  * [142] Joseph Menn  “Exclusive: Secret contract tied NSA and Security Industry Pioneer”  In _Reuters_ Thomson Reuters, 2013  URL: https://www.reuters.com/article/us-usa-security-rsa-idUSBRE9BJ1C220131220
  * [143] Silvio Micali and Leonid Reyzin  “Physically observable cryptography”  In _Theory of Cryptography: First Theory of Cryptography Conference, TCC 2004, Cambridge, MA, USA, February 19-21, 2004. Proceedings 1_ , 2004, pp. 278–296  Springer
  * [144] John Neumann  “Various Techniques used in Connection with Random Digits”  In _Monte Carlo Method, U.S. National Bureau of Stadndarts, Applied Mathematics Series_ 12, 1951, pp. 36–38
  * [145] Noam Nisan and Avi Wigderson  “Hardness vs randomness”  In _Journal of Computer and System Sciences_ 49.2, 1994, pp. 149–167  DOI: https://doi.org/10.1016/S0022-0000(05)80043-1
  * [146] Maciej Obremski and Maciej Skórski  “Inverted Leftover Hash Lemma”, ISIT, 2018
  * [147] Mihai Patrascu  “Towards polynomial lower bounds for dynamic problems”  In _Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010_ ACM, 2010, pp. 603–610  DOI: 10.1145/1806689.1806772
  * [148] Mihai Patrascu  “Unifying the Landscape of Cell-Probe Lower Bounds”  In _SIAM J. Comput._ 40.3, 2011, pp. 827–847  DOI: 10.1137/09075336X
  * [149] Sivaramakrishnan Natarajan Ramamoorthy and Anup Rao  “Lower Bounds on Non-Adaptive Data Structures Maintaining Sets of Numbers, from Sunflowers”  In _33rd Computational Complexity Conference (CCC 2018)_ 102, Leibniz International Proceedings in Informatics (LIPIcs)  Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2018, pp. 27:1–27:16  DOI: 10.4230/LIPIcs.CCC.2018.27
  * [150] Ran Raz  “Extractors with Weak Random Seeds”  In _Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing_ , STOC ’05  Baltimore, MD, USA: Association for Computing Machinery, 2005, pp. 11–20  DOI: 10.1145/1060590.1060593
  * [151] Ran Raz, Omer Reingold and Salil Vadhan  “Extracting all the Randomness and Reducing the Error in Trevisan’s Extractors”  In _Journal of Computer and System Sciences_ 65.1, 2002, pp. 97–128  DOI: https://doi.org/10.1006/jcss.2002.1824
  * [152] Vojtěch Rödl  “On a Packing and Covering Problem”  In _European Journal of Combinatorics_ 6.1, 1985, pp. 69–78  DOI: https://doi.org/10.1016/S0195-6698(85)80023-8
  * [153] J. Rompel  “One-Way Functions Are Necessary and Sufficient for Secure Signatures”  In _Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing_ , STOC ’90  Baltimore, Maryland, USA: Association for Computing Machinery, 1990, pp. 387–394  DOI: 10.1145/100216.100269
  * [154] Alexander Russell, Qiang Tang, Moti Yung and Hong-Sheng Zhou  “Correcting Subverted Random Oracles”  In _Advances in Cryptology – CRYPTO 2018_ Cham: Springer International Publishing, 2018, pp. 241–271
  * [155] Miklos Santha and Umesh V. Vazirani  “Generating quasi-random sequences from semi-random sources”  In _Journal of Computer and System Sciences_ 33.1, 1986, pp. 75–87  DOI: https://doi.org/10.1016/0022-0000(86)90044-9
  * [156] Adi Shamir  “How to Share a Secret”  In _Commun. ACM_ 22.11 New York, NY, USA: Association for Computing Machinery, 1979, pp. 612–613  DOI: 10.1145/359168.359176
  * [157] Bhavani Shankar, Kannan Srinathan and C. Rangan  “Alternative Protocols for Generalized Oblivious Transfer”  In _Distributed Computing and Networking_ Berlin, Heidelberg: Springer Berlin Heidelberg, 2008, pp. 304–309
  * [158] Christian Sommer, Elad Verbin and Wei Yu  “Distance Oracles for Sparse Graphs”  In _50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA_ IEEE Computer Society, 2009, pp. 703–712  DOI: 10.1109/FOCS.2009.27
  * [159] Michael A. Soss, Jeff Erickson and Mark H. Overmars  “Preprocessing chains for fast dihedral rotations is hard or even impossible”  In _Comput. Geom._ 26.3, 2003, pp. 235–246  DOI: 10.1016/S0925-7721(02)00156-6
  * [160] Akshayaram Srinivasan and Prashant Nalini Vasudevan  “Leakage Resilient Secret Sharing and Applications”  In _Advances in Cryptology – CRYPTO 2019_ Cham: Springer International Publishing, 2019, pp. 480–509
  * [161] Douglas R. Stinson and Ruizhong Wei  “Combinatorial repairability for threshold schemes”  In _Des. Codes Cryptogr._ 86.1, 2018, pp. 195–210  DOI: 10.1007/s10623-017-0336-6
  * [162] Luca Trevisan  “Extractors and Pseudorandom Generators”  In _J. ACM_ 48.4 New York, NY, USA: Association for Computing Machinery, 2001, pp. 860–879  DOI: 10.1145/502090.502099
  * [163] Luca Trevisan and Salil Vadhan  “Extracting randomness from samplable distributions”  In _Proceedings 41st Annual Symposium on Foundations of Computer Science_ , 2000, pp. 32–42  DOI: 10.1109/SFCS.2000.892063
  * [164] Salil P Vadhan  “Pseudorandomness”  In _Foundations and Trends® in Theoretical Computer Science_ 7.1–3 Now Publishers, Inc., 2012, pp. 1–336
  * [165] Emanuele Viola  “Lower Bounds for Data Structures with Space Close to Maximum Imply Circuit Lower Bounds”  In _Theory Comput._ 15, 2019, pp. 1–9  DOI: 10.4086/toc.2019.v015a018
  * [166] Emanuele Viola  “Lower bounds for data structures with space close to maximum imply circuit lower bounds”  In _Theory of Computing_ 15.1 Theory of Computing Exchange, 2019, pp. 1–9
  * [167] Gavin Wright and Alexander S. Gillis  “What is a side-channel attack?”  In _TechTarget_ TechTarget, 2021  URL: https://www.techtarget.com/searchsecurity/definition/side-channel-attack
  * [168] Andrew Chi-Chih Yao  “Should Tables Be Sorted?”  In _J. ACM_ 28.3, 1981, pp. 615–628  DOI: 10.1145/322261.322274
  * [169] Yanqing Yao and Zhoujun Li  “Differential Privacy With Bias-Control Limited Sources”  In _IEEE Transactions on Information Forensics and Security_ 13.5, 2018, pp. 1230–1241  DOI: 10.1109/TIFS.2017.2780802
  * [170] Yuval Yarom and Katrina Falkner  “$\\{$FLUSH+ RELOAD$\\}$: A high resolution, low noise, l3 cache $\\{$Side-Channel$\\}$ attack”  In _23rd USENIX security symposium (USENIX security 14)_ , 2014, pp. 719–732
  * [171] Marius Zimand  “Efficient privatization of random bits”  In _Randomized Algorithms Satellite Workshop of the 23rd International Symposium on Mathematical Foundations of Computer Science_ , 1998
  * [172] D. Zuckerman  “Simulating BPP using a general weak random source”  In _[1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science_ , 1991, pp. 79–89  DOI: 10.1109/SFCS.1991.185351