Isaac M Hair

Isaac M Hair, Amit Sahai

We prove a list recovery guarantee for random low-rate linear codes over sufficiently large prime fields. For fixed dimension $d$, error fraction $α$, and accuracy parameter $\varepsilon$, a random $d$-dimensional linear code $C \subseteq \mathbb{F}_p^n$ is, with high probability, $(α,\ell,\frac{1+\varepsilon}{1-α}\ell)$-list recoverable simultaneously for all input list sizes $\ell\le 2^{O_{α, \varepsilon, d}(n/\log n)}$. The proof is inspired by work of Matoušek, Př\'ıvětivý, and Škovroň on reconstructing point sets from their projections. It combines a deterministic graph-theoretic certificate, a nonvanishing determinant criterion, and the Schwartz--Zippel lemma. We also give a lower bound showing that any linear code $C \subseteq \mathbb{F}_p^n$ of dimension at least two cannot be $(α,\ell,\frac{1+\varepsilon}{1-α}\ell)$-list recoverable for feasible list sizes $\ell \geq 2^{Ω_{α, \varepsilon}(n)}$. In this sense, our result is nearly optimal.

Isaac M Hair, Amit Sahai

We give a public key encryption scheme with plausible quasi-exponential security based on the conjectured intractability of two constraint satisfaction problems (CSPs), both of which are instantiated with a corruption rate of $1 - o(1)$. First, we conjecture the hardness of a new large alphabet random predicate CSP (LARP-CSP) defined over an arbitrary but strongly expanding factor graph, where the vast majority of predicate outputs are replaced with random outputs. Second, we conjecture the hardness of the standard $k$XOR problem defined over a random factor graph, again where the vast majority of parity computations are replaced with random bits. In support of our hardness conjecture for LARP-CSPs, we give a variety of lower bounds, ruling out many natural attacks including all known attacks that exploit non-random factor graphs. Our public key encryption scheme is the first to leverage high corruption CSPs while simultaneously achieving a plausible security level far above quasi-polynomial. At the heart of our work is a new method for planting cryptographic trapdoors based on the label extended factor graph for a CSP. Along the way to achieving our result, we give the first uniform construction of an error-correcting code that has an expanding, low density generator matrix while simultaneously allowing for efficient decoding from a $1 - o(1)$ fraction of corruptions.

Isaac M Hair, Amit Sahai

We show that, assuming NP $\not\subseteq$ $\cap_{δ> 0}$DTIME$\left(\exp{n^δ}\right)$, the shortest vector problem for lattices of rank $n$ in any finite $\ell_p$ norm is hard to approximate within a factor of $2^{(\log n)^{1 - o(1)}}$, via a deterministic reduction. Previously, for the Euclidean case $p=2$, even hardness of the exact shortest vector problem was not known under a deterministic reduction.