UC Riverside

Linearity testing is an area of theoretical computer science which has been widely studied over the last few decades, and lends itself to numerous applications in cryptography and coding theory. Beginning with the seminal work of [BLR93], the goal of linearity testing is to design an algorithm which distinguishes functions that are linear from those that are far from linear. Linearity tests are characterized by two parameters: the test acceptance parameter $\ep$ and agreement parameter $\delta$. Linearity tests have the property that they should always accept when the input function is linear, but if the function is $(1-\delta)-$far from linear should reject with probability $1-\ep$. We build on previous work in this space to construct two novel high dimensional linearity tests, each of which operate in what we refer to as a ``hybrid'' mode between the high and low agreement regimes. Additionally, we provide concrete applications of each to cryptography. Specifically, we use our first novel linearity test to aid us in proving a lattice hardness result; we use our second novel linearity test in the course of proving an approximation variant of the celebrated Goldreich-Levin Theorem in high dimension with low agreement.

Lattice-based cryptography is the theory of constructing cryptosystems whose security is based on the assumed hardness of lattice problems. Several hard lattice problems, such as the renowned problem of Learning with Errors (LWE), are conjectured to be hard even in the quantum model of computation. As such, many lattice-based cryptosystems serve as the most promising candidates to offer robust security guarantees against quantum adversaries. Beginning with the seminal work of Oded Regev in 2005, a plethora of cryptosystems have been constructed from LWE, including symmetric key encryption, public key encryption, digital signatures, trapdoor functions, fully homomorphic encryption, and many more. However, for many years we had been unable to construct certain types of ``deterministic" cryptosystems directly from LWE, such as pseudorandom function (PRF) families. In 2012, Banerjee, Peikert, and Rosen (EUROCRYPT'12) introduced the problem of Learning with Rounding (LWR), reduced LWE to LWR when the modulus parameter $q$ is super-polynomial in the lattice dimension $n$, and constructed a PRF family from LWR. The assumption that $q$ is super-polynomial in $n$, though, does not provide for practical instantiations of LWR-based cryptosystems; in order to achieve these, we need $q$ to be polynomial in $n$. Many subsequent works provided improved reductions from LWE to LWR for polynomial $q$, but all such works impose an \emph{a priori} bound on the number $m$ of input samples to the reduction.

We show that when $q$ is polynomial and $m$ is unbounded, there does not exist a certain type of reduction from LWE to LWR. In particular, every prior reduction from LWE to LWR is of this type. Hence no prior reduction from LWE to LWR will work for polynomial $q$ and unbounded $m$. Our result \emph{does not} imply that LWR is easy; instead it asserts that any prior reduction from LWE to LWR for polynomial $q$ and unbounded $m$ cannot operate like any prior reduction in the literature.

In the course of proving our result, we introduce a high-dimensional approximate version of the celebrated Goldreich-Levin Theorem (STOC'89). The Goldreich-Levin Theorem at its core solves a learning problem; specifically, it states that any function which predicts the inner product of a secret vector and a uniformly random vector with any advantage over randomly guessing admits an algorithm which recovers the secret vector. Over the last few decades, the Goldreich-Levin Theorem has found numerous applications in cryptography and coding theory, such as to symmetric key cryptography and error correction codes. In our work, we introduce a novel conditional linearity test, and reduce our approximate version of the Goldreich-Levin Theorem in higher dimension to proving such a conditional linearity testing theorem.