Computational Limitations in Robust Classification and Win-Win Results

Introduction

The basic task in learning theory is to learn a classifier given a dataset. Namely, given a labeled dataset $\{(X_{i},f(X_{i}))\}_{i\in[n]}$ where $f$ is the unknown ground-truth and $X_{i}$ are drawn i.i.d. from a distribution $D$, learn a classifier $h$ so as to (approximately) minimize

Adversarial machine learning is harder in that the learned classifier is required to be robust. Namely, it has to produce the right answer even under bounded perturbations (under some distance measure) of the sample $X\sim D$. That is, the goal is to learn a classifier $h$ so as to (approximately) minimize

where B(X,\varepsilon)=\mathopen{}\mathclose{{}\left\{Y:d(X,Y)\leq\epsilon}\right\} and $d$ is the distance measure in question.

Learning robust classifiers is an important question given a large number of attacks against practical machine learning systems that show how to minimally perturb a sample $X$ so that classifiers output the wrong prediction with high probability. Such attacks were first discovered in the context of spam filtering and malware classification [DDS+04, LM05, BR18] and more recently, following [GSS, SZS+13], in image classification, voice recognition and many other domains.

This state of affairs raises a slew of questions in learning theory. Fix a concept class $\mathcal{F}$ and a distribution $D$ for which efficient (non-robust) learning is possible. Do there exist robust classifiers for $F$? Do there exist efficiently computable robust classifiers for $F$? Pushing the envelope further, can such classifiers be learned with small sample-complexity? and finally, is the learning algorithm computationally efficient? The answer to these questions give rise to five possible worlds of robust learning, first postulated in two recent works [BPR18] and [BLPR18], henceforth referred to as BPR and BLPR respectively.To be precise, [BPR18] postulated four worlds, namely worlds $1$ and $3$–$5$. Subsequent work of [BLPR18] added the second world. This is the starting point of our work.

No robust classifiers exist, regardless of computational or sample-efficiency considerations. [FFF18] show a learning task in this world, namely one where computationally efficient non-robust classification is possible, no robust classifiers exist. On the other hand, for natural learning tasks, humans seem to be robust classifiers that tolerate non-zero error rate $\epsilon$, indeed even efficient robust classifiers; see [BPR18] for a more detailed discussion.

Robust classifiers exist, but they are computationally inefficient. We demonstrate learning tasks in this world.

Computationally efficient robust classifiers exist, but learning them incurs large sample complexity. [SST+18] show a learning task where a computationally efficient robust classifier exists, but learning it requires polynomially more samples than non-robust learning. On the other hand, [BPR18] show that this gap cannot be more than linear in the dimension; see [BPR18] for a more detailed discussion.

Computationally efficient robust classifiers exist, and can be learned sample-efficiently, but training is computationally inefficient. [BLPR18] show a learning task in this world. However, as we observe below, their computationally efficient robust classifier only recovers from a very small number (indeed, a constant number) of perturbations. Whether there exists an efficient robust classifier for their task that recovers from large perturbations seems related to long-standing open questions in computational number theory [Hen19, Gre13]. As our second result, we show two examples of learning tasks that live in this world; more details in Section 2.

The best world of all, in which there exist efficient algorithms both for classification and training, and the sample complexity is small (but it could be that we haven’t discovered the right algorithm just yet.)

We want to understand – are we likely to find learning tasks such as the ones [BLPR18] and we demonstrate in the wild? To that end, our third result is a win-win statement: namely, any such learning task gives rise to a cryptographic object– either a simple one like a one-way function or a complex one like public-key encryption.

We proceed to describe the three results in more detail.

But before we do so, a word of warning. We and [BLPR18] define these five worlds in a coarse way using polynomial-time as a proxy for computational efficiency, and a large constant accuracy as a proxy for successful classification. (We should also mention that [BPR18] use SQ-learning as a different proxy for computationally efficient learning.) One could be more careful and speak of running-time/accuracy tradeoffs in the different worlds, but since our goal here is to show broad counterexamples, we do not attempt to do such a fine-grained distinction.

Our Results

We explore the relationship of computational constraints and efficient robust classification. The setting we consider consists of two distributions $D_{0},D_{1}$ and the classifier has to correctly classify inputs from both. We consider the two facets to efficient robust classification: (1) existence: do efficient robust classifiers exist? (corresponds to World 2) and (2) learnbility: can we learn robust classifiers efficiently? We show three sets results on which we elaborate below.

In terms of feasibility, we show that there are learning tasks where while inefficient robust classification is possible, no efficient robust classifiers exist. That is, we demonstrate learning tasks in World 2. We can show the following:

There exist classification tasks over where (1) efficient non-robust classifiers exist, (2) no efficient robust classifier exists, but (3) inefficient robust classifiers exist.

This result does not require cryptographic assumptions, and relies only on the existence of average-case hard functions and good error-correcting codes. In fact, this result scales down to more fine-grained notions of efficiency than polynomial-time. All that is required is a function that is average-case hard for the “efficient” class, but computable by the “inefficient” class.

We give several examples of such learning tasks, including some examples that require cryptographic assumptions but obtain other desirable properties (such as obtaining tasks with efficiently-samplable distributions). More details are given in Sections 3.4, 3.5, 5, 6 and 8.

2 Learnability (World 4)

We want to understand the hardness of learning an efficient robust classifier when it exists. The starting point of this work was the BLPR work [BLPR18]. They showed that under cryptographic assumptions, there exists a learning task which admits efficient robust classifiers, but it is computationally infeasible to train such a classifier. More precisely, they showed that there exists a classification task (over $\{0,1\}^{n}$) where (a) learning any non-trivial robust classifier is computationally infeasible while (b) an efficient robust classifier exists.

Unfortunately, we observe that their robust classifier is efficient only when correcting a constant number of errors. Indeed, as we explain in Section 3.1, the question of whether there exists a computationally efficient robust classifier for their task correcting even $\omega(1)$ bits of error is an important open question in computational number theory that has received some attention in the cryptanalysis community [Gre13, Hen19].

The BPLR construction can be rescued using error correcting codes to enable efficient robust classifiers robust to large (constant fraction) perturbations. Our results strengthen theirs in two ways: we can weaken the required cryptographic assumption to that one-way functions exist and demonstrate tasks where the gap between learning and robust classification is more: in that efficient learning algorithms can learn to not only classify, but also to generate fresh samples from the distributions.

Under the minimal cryptographic assumption that one-way functions, there exist classification tasks over $\{0,1\}^{m}$ where (1) it is easy to learn a non-robust classifier (2) an efficient robust classifier that tolerates $m/8$-sized perturbations exists, and (3) it is computationally hard to learn any non-trivial robust classifier.

Assuming Learning Parity with Noise (or Learning with Errors) in the “public-key” regime of parameters, there exist classification tasks on $\{0,1\}^{m}$ where (1) it is easy to learn a non-robust classifier. (2) an efficient robust classifier tolerating $O(\sqrt{m})$-errors exists, and (3) it is computationally hard to learn any non-trivial robust classifier.

Furthermore, it is easy to learn generators/evaluators for the non-robust distributions.Generators and Evaluators [KMR+94], are algorithms that can sample from the distribution and output the pdf of the distribution respectively.

We elaborate on the differences between the two theorems in the techniques section. Briefly, there are three key differences: Theorem 2.3 requires a stronger assumption, but gives a more “natural” example where the resulting distributions are “more easier” to learn non-robustly. In particular, it is easy to learn how to generate fresh samples from the two distributions, something that the one-way function based example cannot support. This is important because we want to separate the complexity of learning the distribution from that of robust classification. And here, these distributions can be learned in a stronger sense while still being hard to classify under adversarial perturbations.

3 A Win-Win Result

Finally, we want to understand – Are we likely to find such learning tasks in the wild? To that end, we show a converse to our results. Namely,

Any computational task where an efficient robust classifier exists, but is hard to learn one in polynomial time implies one-way functions, and hence symmetric key cryptography.

Furthermore, if the learning task satisfies certain natural properties, it gives us (a certain weaker form of) public-key cryptography as well!

It would be very surprising to us if public-key cryptography (and even one-way functions) arise out of natural classification tasks on, say, images. Thus, perhaps uncharacteristically for cryptographers, we offer a possible (optimistic) interpretation of this state of affairs: namely, that for natural learning tasks where there exists a robust classifer, it can also be efficiently found, we just haven’t figured out the right algorithm yet.

An important caveat is due here: our definition of hardness of learning a robust classifier is a strong one: it requires that the perturbing adversary be constructive and universal. Our classification tasks do satisfy this definition, and that only makes them stronger. On the other hand, it does make our converse weaker. More details are given in Section 3.

4 Related Work.

The works closest to ours are [BPR18, BLPR18]. We discuss them last.

The problem of adversarial classification ws first considered by [DDS+04]. Starting with [SZS+13], there is a large body of work demonstrating the existence of small adversarial perturbations in neural networks that cause them to misclassify examples with high confidence. There have been various approaches proposed against such perturbations and many of them have been broken (see [CW17, ACW18] and references therein).

[SST+18] demonstrate simple classification tasks (distinguishing between high dimensional gaussians) where the sample complexity of robust learning is higher than that of classical learning by a polynomial factor. Hence they show evidence for world 3. [BPR18] show that this gap is essentially tight. This work is similar in spirit to ours, with the resource being sample complexity instead of computational complexity in our case. In the case of computational complexity, we can essentially show exponential gap between the running time required for learning non-robustly vs learning robust classifiers.

In BPR, they showed two results. First, that in the world of polynomial sample complexity with no bounds on running time, learning a non-robust classifier and learning a robust classifer have the comparable sample complexity, if such a robust classifier exists. Second, they exhibit a learning task where while learning a robust classifier was information-theoretically easy with polynomial sample complexity, but doing so was difficult in the SQ model and it required exponentially many queries. This gives rise to a task where learning a robust classifier in a computationally efficient manner (in the SQ model) was a lot harder than doing so inefficiently.

In a followup work, BLPR they considered strengthening the second BPR result to show that under cryptographic assumptions, there exists a learning task which admitted efficient robust classifiers, but it was computationally infeasible to do so. They showed that there exists a classification task (over $\{0,1\}^{n}$) where learning any non-trivial robust classifier is computationally infeasible while an efficient robust classifier exists that can correct $O(1)$-bit error. A description of their construction is given in Sections 3.1 and A.

Our Techniques

In this section, we give a high level description of our techniques. We begin by describing the BLPR classification task and its limitations. Then we describe the definition of robust classification and non-existence/unlearnability of such classifiers. We then describe several recipes for constructing tasks where robust classification is computationally intractable. In the first recipe, based on one-way functions, we show tasks where while efficient robust classifiers exist, but are hard to learn, thus proving Theorem 2.2. The second recipe assuming average-case hard functions proves Theorem 2.1, where no efficient robust classifiers exist. The final recipe is based on hardness assumptions on decoding noisy codewords / lattices, namely Learning Parity with Noise (LPN) and Learning with Errors (LWE) and proves Theorems 2.1 and 2.3 in different parameter regimes.

We sketch the [BLPR18] classification task where it is difficult to learn a robust classifier. A more detailed description of their construction is given in Appendix A.

They show that the Blum-Blum-Shub Pseudorandom generator [BBS86] has such a trapdoor. Given a trapdoor PRG, their learning task $D_{0},D_{1}$ is the following:

The first bit enables easy non-robust classification. The fact that there exists an inefficient robust classifier follows from a volume argument – that the there are a few PRG outputs in a large domain. This implies that there is an inefficient robust classifier that tolerates $O(\sqrt{n})$-sized perturbations. That a robust classifier is hard to learn follows from the perturbing adversary that sets the first bit to . A robust classifier has to distinguish between outputs of the PRG from random strings, without the trapdoor. This is infeasible by the security guarantee of the PRG.

Finally, what needs to be proved is that the trapdoor enables robust classification. The trapdoor indeed does enable a robust classifier that tolerates constant-sized pertubations (i.e., if any constant number of bits are altered) simply by exhaustive search among the polynomially many possible sets of perturbed bits. For a constant $c$, the robust classifier given input $y$ goes over all $n^{c}$ words in the Hamming ball $y^{\prime}\in B(y,c)$ and checks if the distinguisher ${\mathsf{D}}({\mathsf{trap}},y^{\prime})=1$. If yes, output $D_{0}$ else output $D_{1}$. But this approach does not give a classifier beyond constant-sized errors because the running time is exponential in the number of errors corrected.

The primary limitation of trapdoor PRGs is that the trapdoor does not enable decoding the PRG output from the perturbed samples, only distinguishes PRG outputs from random strings. Indeed, for the Blum-Blum-Shub trapdoor PRG (and related constructions such as the one of Micali and Schnorr [MS91]) considered in BLPR, the question of whether there is any trapdoor that permits robust inversion is an open question in computational number theory. We refer the reader to Appendix A for discussions regarding related questions. To enable efficient decoding, their construction can be modified by using an error correcting code to make it robust to larger pertubations.

2 Definitions: Robust Classification

We start by describing the notion of robust classification and hardness of robust classification used.

When we state that a robust classifier exists (for given $\varepsilon$), we show the strongest notion: that there exists a classifier ${\mathsf{R}}$ (efficient or inefficient, as specified) that classifies all input close to a random sample correctly:

Non-Existence/Unlearnability of Robust Classifiers.

When we describe the non-existence (or unlearnability) of robust classification, we satisfy the strongest notion: that there exists a poly-time perturbation adversary ${\mathsf{P}}$ whose perturbed examples cannot be classified better than chance by any efficient (or efficiently learned) classifier. That is, for any efficient ${\mathsf{R}}$ (or ${\mathsf{R}}\leftarrow\mathsf{learn}^{D_{0},D_{1}}(1^{n})$),

3 Unlearnability From Pseudorandom Functions and Error Correcting Codes

In this section, we construct a learning task where classification is easy, robust classifier exits, but is hard to learn. The primary ingredients of this construction are pseudorandom functions and error correcting codes. We introduce both the primitives and build the construction in stages. A pseudorandom function family (PRF) [GGM86] is a family of keyed functions $F_{k}:\{0,1\}^{n}\rightarrow\{0,1\}$ where the key $k\leftarrow\{0,1\}^{n}$, that are indistinguishable from uniformly random functions to any polynomial time algorithm. That is, for every poly time algorithm ${\mathsf{A}}$,

where $U_{n}:\{0,1\}^{n}\rightarrow\{0,1\}$ is a uniformly random function. PRFs can be constructed from one-way fucntions. Kearns and Valiant [KV94] constructed a hard to learn classification task using pseudorandom functions as follows:

The task essentially asks to efficiently learn a predictor for the pseudorandom function which is difficult. To transform this task to one that is hard to learn robustly, while an efficient robust classifier exists, we use error correcting codes. Recall that an error correcting code has two algorithms $({\mathsf{Encode}},{\mathsf{Decode}})$ where ${\mathsf{Encode}}$ returns a redundant encoding of the message that the ${\mathsf{Decode}}$ algorithm can efficiently recovers the encoded message even when the encoded codeword is tampered adversarially to some degree. So, consider the following classification task: distinguish between error-corrected versions of the PRF:

Note that this task has the following properties: (1) A robust classifier exits and, (2) a robust classifier is hard to learn. For the first property, consider the following robust classifier: the classifier given the secret key, first decodes the perturbed sample using the ${\mathsf{Decode}}$ algorithm and then checks if is of the form $(x,F_{k}(x))$ or $(x,1-{F_{k}(x)})$ and outputs which case it is. The robustness follows from the error correcting code. The fact that no classifier is learnable follows from the fact that the PRF is hard to predict, and thats exactly what the classifier has to do. Finally, we want the task to be easy to classify non-robustly. Here we use the “BPR trick” ([BPR18]). That is, we additionally append to each sample a bit indicating which distribution it was sampled from. That is,

Now the samples are easy to classify non-robustly, simply output the first bit. Learning a robust classifier is hard, for that, consider the perturbing adversary that erases the first bit. For these samples, robust classification is identical to predicting the output of the PRF. This is difficult for any efficiently learned classifier. Hence, this gives us a task that that is easy to classify, has an efficient robust classifer and yet, any non-trivial robust classifier is hard to learn.

Note that because we have excellent error correcting codes, this recipe is maximally robust. We can pick a code that tolerates a constant fraction ($\frac{1}{4}-\varepsilon$) errors and still enable correct decryption [GI01]. This can be further boosted to $(\frac{1}{2}-\varepsilon)$ by using list decoding instead of unique decoding and increasing the output size of the PRF to $n$-bits. We do not formally write this construction.

4 Non-Existence of Robust Classifiers from Average-Case Hardness

This section describes a learning task for which no computationally efficient robust classifier exists, even though inefficient ones do, based on average-case hard functions, thus proving Theorem 2.1.

Let $g:\{0,1\}^{n}\to\{0,1\}$ be a function that is average-case hard, such that no polynomial-time nonuniform algorithm can compute $z\mapsto g(z)$ noticeably better than random guessing. For example, taking $g$ to be a random function $\{0,1\}^{n}\to\{0,1\}$ suffices. Let $({\mathsf{Encode}},{\mathsf{Decode}})$ be a good error correcting code, capable of decoding from a constant fraction of errors. Now, construct distributions $D_{0},D_{1}$ as follows:

for $x\leftarrow\{0,1\}^{n}$ uniformly. Note that these distributions are trivially distinguishable non-robustly. However, with a perturbation adversary that destroys the first coordinate, distinguishing $D_{0}$ from $D_{1}$ essentially requires computing the function $g(x)$, which cannot be done efficiently. Thus, there is no efficient robust classifier. Moreover, an inefficient robust classifier exists, since one can decode the error correcting code (correcting any adversarial errors) and compute $g(x)$.

When using an average-case hard function, one limitation here is that the algorithm generating the samples from distributions $D_{0},D_{1}$ is inefficient. This can be remedied by using one-way functions, because generating $D_{0},D_{1}$ requires the algorithm to perform the simpler task of sampling $(z,g(z))$ for random $z$’s, and not computing $g(z)$ given $z$, that the classifier has to do. In fact, this is precisely the difference between average-case ${\mathsf{NP}}$ hardness, which requires us to generate hard instances, and one-way functions, which require generating hard instances along with their solutions. See Section 3.4 for more details.

5 From Hardness of Decoding under Noise.

Then the computational task is to distinguish a point close to the code from a uniformly random point in the space. The conjectured hardness of these problems can be used to construct a variety of cryptographic primitives. In the overview, we will describe the construction with the LPN assumption. The LWE construction is conceptually identical.

So, the task is to distinguish codewords of $C$ from their affine shift ($\bm{1}$ represents the all-ones vector). The distributions are easy to classify non-robustly. There exists an inefficient robust classifier because the distance between the two codes $C$ and $C+\bm{1}$ is large.

To show that a robust classifier is hard to learn, consider the perturbation adversary that adds random noise of varying size to the two distributions. Learning a robust classifier for this adversary is equivalent to distinguishing LPN samples from random. Hence any computationally efficient adversary cannot classify these examples better than chance.

Finally, we need to show that for a certain perturbation regime, no efficient robust classifier exists while for a different perturbation regime, an efficient robust classifier does exist. The latter is accomplished by the notion of “trapdoor sampling” where the code is sampled with a trapdoor that enables decoding noisy codewords (and hence robust classification too).

Below we describe the example in more detail and give a sketch of the arguments needed. Formal proofs are given in Sections 5 and 6.

LPN Assumption.

The LPN hardness assumption states that: for $m={\mathsf{poly}}(n)$,

Hardness Regimes and Trapdoors.

Along with their conjectured computational hardness, we are interested in another property of these problems, the existence of a trapdoor: that is, can we sample the code along with some polynomial-size side information that lets us distinguish efficiently random points from points close to the code. This information usually is a “short basis” for the dual code. The trapdoor property has two important regimes: the “public-key” regime and the “private-key” regime. In the case of LPN, the public-key regime corresponds to error rate $r=O(1/\sqrt{n})$ while the private-key regime translates to constant error rates, e.g., $r=0.1$. The public key regime of parameters enables construction of advanced cryptographic primitives, including public key encryption. On the other hand, in the private-key regime, we know constructions of one-way functions and symmetric key cryptography, but not much more.

Importantly for us, in “public-key” parameter regime, such a trapdoors exists and can be sampled efficiently. On the other hand, in the private-key regime, it is conjectured that no such trapdoor exists. Traditionally this problem is studied as the problem of decoding linear codes with preprocessing (for LPN) and closest vector problem with preprocessing (for LWE). In the problem of decoding linear codes with preprocessing, an inefficient algorithm $\mathsf{Preprocess}$ performs arbitrary preprocessing on the given linear code (described by the matrix $\mathbf{A}$) and has to come up with a short polynomial-sized trapdoor for the code. Later the ${\mathsf{Decode}}$ algorithm has to use this trapdoor to efficiently find the codeword close to a given input. This problem and the closest vector problem (is the same problem, on lattices instead of codes) are ${\mathsf{NP}}$-hard to approximate in the worst-case [BN90, Mic01, Reg04].

We require an average-case variant of the problem termed as the hardness of LPN with Preprocessing. The assumption is stated more formally in Assumption 5.4. This assumption can be used to construct a task where no efficient robust classifier exists. The task is very similar to the one below where a efficient robust classifier exists but is hard to find, except with higher levels of noise. More details in Section 5.

Task with an Hard-to-Learn Efficient Robust Classifier.

Note that earlier, we added $0.1m$ bits of noise, instead here we are adding $0.1\sqrt{m}$ bits. This level of noise places the problem in the “public-key” regime of parameters. Furthermore, given the trapdoor, in this case, we can recover which distribution the unperturbed sample was sampled from, giving us the required robust classifier. See Section 5 for more details.

Again, it is clear that learning a non-robust classifier is easy. The hardness of LPN assumption implies that it is hard to learn a robust classifier. This is in contrast to the previous construction where no efficient robust existed. Here, the trapdoor gives us an efficient robust classifier, but the hardness of LPN implies that such a classifier is hard to learn. In fact, any efficiently learned classifier cannot do better than chance.

A feature of this construction is that an efficient algorithm can learn to not only distinguish the samples from distributions $D_{0}$ and $D_{1}$, it can easily learn to generate samples from the two distributions as well.

Comparing Recipes.

There are three key differences between the recipes. The first difference is in the underlying hardness assumption. The first two constructions are based on weaker assumptions: namely general assumptions that one-way functions exist (or average-case hard function respectively) rather than the specific assumptions of LWE and LPN.

The second difference is that the distributions based on LWE/LPN facilitate learning in a stronger sense, that it is possible to sample from the non-robust distributions after seeing polynomially many samples. In construction I based on one-way functions, we do not learn either $D_{0}$ or $D_{1}$ in that strong sense. In fact, after seeing polynomially many samples, efficient sampling algorithms have no non-trivial advantage with the other recipes. As pointed out in in construction II, it is possible to support generation, albeit using a slightly stronger assumption that one-way functions exist.

The third difference is that of naturalness: we feel that the LWE/LPN recipe gives a more natural learning task. This is obviously a subjective notion. This learning task of distinguishing noisy codewords from random has existed independent of the notion of robust classification and arises naturally in other contexts.

6 Converse: Cryptography from Hardness of Robust Classification.

In this section, we describe how Theorem 2.4 is proved. The key result we rely on here is that we can construct one-way functions from any pair of samplable distributions that are statistically far and computationally indistinguishable.

Given a pair of distributions $(X_{0},X_{1})\leftarrow{\mathcal{F}}$ over ${\mathcal{X}}$ that are statistically far, i.e., $d_{TV}(X_{0},X_{1})>0.9$ and computationally indistinguishable. That is for every polynomial time adversary ${\mathsf{A}}$ that gets sample access to the distributions,

Then one-way functions exist.The constants in the equations are fairly arbitrary. We can replace them by any constants $\alpha,\beta$ where $\alpha>\beta$ and the result holds (see [NR06, BDRV19]).

In order to construct such distributions, we rely on the learning task (given by $(D_{0},D_{1})$) and the perturbation adversary ${\mathsf{P}}$. The distributions we consider are

Note that because efficient robust classifiers are hard to learn, no efficient algorithm ${\mathsf{A}}$ (that knows ${\mathsf{P}}$ and gets access to the distributions $D_{0},D_{1}$) can distinguish between the two distributions . On the other hand, because a robust classifier exists, these two distributions are statistically far from each other. This implies that one-way functions exist.

Definitions

For a family of classification tasks ${\mathcal{F}}$ over ${\mathcal{X}}$ is easy to classify if there exists a learning algorithm that given ${\mathsf{poly}}(n)$ i.i.d. samples from a pair of distributions $(D_{0},D_{1})\in{\mathcal{F}}$ supported on ${\mathcal{X}}$, outputs an efficiently computable classifier ${\mathsf{A}}:{\mathcal{X}}\rightarrow\{0,1\}$ such that,

We want to consider other notions of learning distributions as well, in order to make more refined distinctions between learning distributions. The following definition for learnability of discrete distributions is from [KMR+94].

For a distribution $D$ over a discrete domain ${\mathcal{X}}$,

Generator. A circuit ${\mathsf{G}}:\{0,1\}^{m}\rightarrow{\mathcal{X}}$ is an $\varepsilon$-good generator for $D$ if

where ${\mathsf{G}}(U)$ denotes the distribution obtained by evaluating ${\mathsf{G}}$ on a uniformly random input.

where ${\mathsf{E}}$ denotes the distribution obtained by sampling with probability density function ${\mathsf{E}}$.

A class of distributions {\mathcal{F}}=\mathopen{}\mathclose{{}\left\{F_{n}}\right\} over a discrete domain {\mathcal{X}}=\mathopen{}\mathclose{{}\left\{{\mathcal{X}}_{n}}\right\} is $(\varepsilon,\delta)$-efficiently learnable with a generator (or evaluator resp.) if there exists a polynomial time algorithm ${\mathsf{Gen}}$ that given oracle access to any $D_{n}\in{\mathcal{F}}_{n}$ runs in time ${\mathsf{poly}}(n,1/\delta,1/\varepsilon)$ and outputs ${\mathsf{G}}$ (or ${\mathsf{E}}$ resp.) such that with probability $\geq 1-\delta$ over the randomness of ${\mathsf{Gen}}$ and samples, ${\mathsf{G}}$ (${\mathsf{E}}$ resp.) is an $\varepsilon$-good generator (evaluator resp.) of $D$.

In our examples, we seek to find distributions where the gap between ease of learning the actual distributions and that of the adversarially perturbed distributions is maximized.

2 Hardness of Efficient Robust Classification

We start by recalling the notion of robust classification. Then, we consider two ways of formalizing the difficulty of efficient robust classification: (1) no efficiently computable robust classifier exists, (2) an efficient robust classifer exists, but it is hard to learn one efficiently.

Consider a classification task given by two distributions $D_{0},D_{1}$ over ${\mathcal{X}}^{n}$. Let $\|\cdot\|$ be a norm over the space ${\mathcal{X}}^{n}$ and $\varepsilon>0$. Let ${\mathsf{R}}:{\mathcal{X}}^{n}\rightarrow\{0,1\}$ be a classifier. The classifier ${\mathsf{R}}$ is $\varepsilon$-robust if

Consider a family of classification tasks, defined by two distributions $D_{0}$, $D_{1}$ over ${\mathcal{X}}^{n}$ sampled from a distribution over learning tasks $\sf{Samp}$. Let $\|\cdot\|$ be a norm over the space ${\mathcal{X}}^{n}$ and $\varepsilon>0$. We consider the following notions of difficulty of robust classification:

No efficient $\varepsilon$-robust classifier exists. There exists a polynomial-sized perturbation algorithm ${\mathsf{P}}$, such that for every polynomial sized classifier ${\mathsf{R}}$, the perturbed samples are hard to classify. That is,

Efficient $\varepsilon$-robust classifier is hard to learn. There exists a polynomial-sized perturbation algorithm ${\mathsf{P}}$, such that every polynomial-time learning algorithm $\mathsf{learn}$ that outputs a polynomial sized classifier ${\mathsf{R}}$, the perturbed samples are hard to classify for ${\mathsf{R}}$. That is, for a learning task $D_{0},D_{1}$ sampled by $\mathsf{Samp}$ and robust classifer ${\mathsf{R}}\leftarrow\mathsf{learn}^{D_{0},D_{1}}(1^{n})$ output by $\mathsf{learn}$,

An alternate definition of hard to classify robustly would be the negation of robust classification. That definition takes a following form:

This definition is unsatisfactory because it does not say anything about how difficult it is to find such perturbations. In the event when such examples are not efficiently discoverable, we do not have to worry about these.

In the definitions used, the perturbing adversary is both efficient and universal. Efficiency is a very natural property to have, in that if the adversarial examples are computationally hard to find, then they are less of a concern. The universality property says that there is a single perturbation adversary that succeeds against all efficient classifiers. This is a strong requirement. This makes our robustly hard to learn tasks better: that they have a unique perturbation adversary that is independent of which classification algorithm is used. On the other hand, it makes our converse results constructing one-way functions from hard to learn robust tasks weaker, because they only hold for such robustly hard to learn tasks, with universal perturbation adversaries.

It is possible to have a perturbation adversary ${\mathsf{P}}$ that is efficient but not universal. The perturbation adversary gets oracle access to the classifier and has to then output a misclassified example. This is a weaker requirement than Definition 4.5. We do not know if such a definition also implies cryptography.

Learning Parity with Noise

The Learning Parity with Noise (LPN) assumption assumes that for $m={\mathsf{poly}}(n)$ and $t=\theta(m/\sqrt{n})$, the LPN samples are indistinguishable from random. That is, for every efficient distinguisher ${\mathsf{D}}$,

This regime of parameters $m={\mathsf{poly}}(n)$ and $t=\theta(m/\sqrt{n})$ is what is traditionally used to construct public key encryption from the LPN assumption. Next, we consider the LPN problem with preprocessing: in this variant of the problem, an inefficient algorithm $\mathsf{Preprocess}$ is allowed to process the matrix $\mathbf{A}$ arbitrarily to construct a “trapdoor”. Then the distinguisher is asked to distinguish LPN sample $(\mathbf{A},\bm{s}^{T}\mathbf{A}+\bm{e})$ from random. The assumption states that this is difficult for higher error rates.

We say that a pair of algorithms $(\mathsf{Preprocess},{\mathsf{D}})$ where $\mathsf{Preprocess}$ is possibly inefficient and ${\mathsf{D}}$ is efficient, solves $\mathsf{LPN}_{n,m,t}$ if ${\mathsf{D}}$ can distinguish an LPN sample from a random sample given the trapdoor ${\mathsf{trap}}$ generated by $\mathsf{Preprocess}(\mathbf{A})$.

The Learning Parity with Noise problem is hard even with preprocessing in the constant noise regime.

where the probability is over the code $\mathbf{A}$, $\bm{s},\bm{e},\bm{r}$ and the randomness of the distinguisher ${\mathsf{D}}$.

The most important parameter of the LPN problem is its error rate, that is $r=t/m$. The higher the error rate, the more difficult the problem. There are two important regimes of the error rate: $r$ is a constant and $r=o(\frac{1}{\sqrt{n}})$. When the error rate is a constant, the hardness of LPN in this regime implies one-way functions and hence symmetric key cryptography. We do not know how to base public key encryption on error rates in this regime. When the error rate decreases below $O(\frac{1}{\sqrt{n}})$, we can construct public key encryption from this problem. For error rates below $\log n/n$, the problem becomes easy. The best known algorithms for solving LPN are due to Blum Kalai and Wasserman [BKW03] which solves LPN in time $2^{O(n/\log n)}$ requiring $2^{O(n/\log n)}$ samples; and Lyubashevsky [Lyu05] which solves LPN in time $2^{O(n/\log\log n)}$ with polynomially many samples. For structured LPN samples, more efficient algorithms are known [AG11]. Our error distributions are not structured.

Note that the lesser used variant of LPN is used here, in that we insist that the Hamming weight of the error vector is exactly $t$ instead of a random variable. This is equivalent to the standard formulation [JKPT12].In the search version of the problem where the adversary has to find $\bm{s}$ given $\mathbf{A},\bm{s}^{T}\mathbf{A}+\bm{e}^{T}$, these two versions are equivalent as $t$ takes polynomially many values, hence we can go over all polynomially-many and try solving each exact version). This is done for convenience and the example can be translated to the definition of LPN where the error vector is drawn from a product distribution.

We also consider a the preprocessing variant of Learning Parity with Noise. In this variant, the adversary is allowed to preprocess the code and generate a small “trapdoor” to the code. Then an efficient adversary is tasked with distinguishing the LPN samples from random. The preprocessing variant of LPN assumption states that even this is hard in the constant error regime, that is when $t/m$ is a constant. It is known that decoding linear codes is NP-hard in the worst case [BN90]. The search analog of LPN is precisely the average-case variant of this question and is conjectured to be hard in the regime of constant noise rate.

Trapdoor for Efficient Decoding.

In the public key regime, we want to show that trapdoors exist that enable effient distinguishing of LPN samples. We state the result next: that there is a way to sample a random matrix $\mathbf{H}$ that is indistinguishable from a random matrix such that it has a trapdoor that enables efficient distinguishing.

The algorithm has the following properties:

The matrix $\mathbf{H}$ is computationally indistinguishable from uniformly random matries. That is,

With overwhelming probability over the randomness of the algorithm, it outputs $\mathbf{E}$ such that every column of $\mathbf{E}$ has Hamming weight at most $t$ and every row of $\mathbf{E}$ has Hamming weight exactly $t$.

The notion of Trapdoor sampling is very widely used in the context of learning with errors assumption. A trapdoor sampling algorithm samples along with the public matrix $\mathbf{A}$ which is statistically close to a random matrix (representing the code/lattice), a secret “trapdoor”. This trapdoor enables solving the bounded distance decoding problem, that is given a point close to a codeword in the code, finds the close codeword. As we know, without this trapdoor, this problem is conjectured to be hard. But the trapdoor enables solving this problem.

We have a computational analog of that property for LPN in the “public-key” regime of parameters. We construct that below. Because $\mathbf{E}$ is a sparse matrix, it can be used to solve the problem of distinguishing LPN samples from random and decoding noisy codewords.

By definition, $\operatorname{rowspan}(\mathbf{E})\subset\operatorname{rowspan}(\mathbf{H})$ and that each row of $\mathbf{E}$ has Hamming weight exactly $t$. We need to show that $\mathbf{H}$ is indistinguishable from random and that every column of $\mathbf{E}$ has at most $t$ ones. The former follows from the Learning Parity with Noise combined with a hybrid argument and the latter from a Chernoff bound.

The output distribution of $\mathbf{H}$ is computationally indistinguishable from uniform. That is,

Observe that the LPN assumption can be restated as, The LPN assumption assumes that the following two distributions are indistinguishable:

Let $\bm{e}_{(\cdot,j)}$ denote the $j$-th column of matrix $\mathbf{E}$. Then,

The proof follows from Chernoff bound and a union bound. For any fixed column $j$, each coordinate $e_{i,j}=1$ independently with probability $t/8n$ where the probability is over $i$. Hence, for any column $j$, the expected Hamming weight is $\frac{t}{8n}\cdot n=\frac{t}{8}$. By a Chernoff bound, we can observe the following:

A union bound over all $j$ gives us the required bound. ∎

Because $t=\sqrt{n}$, the failure probability is negligible. ∎

2 No Efficient Robust Classifier Exists

Next, we describe a learning task where while it is possible to inefficiently perform robust classification, no efficient robust classifier exists.

The learning task has the following properties.

(Learnability) A classifier to distinguish $D_{0}$ from $D_{1}$ can be learned from the samples efficiently. Furthermore, it is easy to learn a generator/ evaluator for these distributions.

(No Efficient Robust Classifier Exists) There exists a perturbation algorithm ${\mathsf{P}}$ such that there exists no efficient robust classifier ${\mathsf{R}}$ such that,

Learnability of this task is trivial. Given enough samples, the entire subspace spanned by $\mathbf{A}$ is learned and can be sampled from.

In order to show that no efficient robust classifier exists for $\varepsilon=2n$, we rely on the difficulty of LPN with Preprocessing (Assumption 5.4). Consider the following perturbing adversary ${\mathsf{P}}$:

Consider the following pair of algorithms $\mathsf{Preprocess},{\mathsf{D}}$: $\mathsf{Preprocess}(\mathbf{A})$ inefficiently finds the best possible efficient robust classifier ${\mathsf{R}}$ and returns that as the trapdoor ${\mathsf{trap}}={\mathsf{R}}$. The distinguisher ${\mathsf{D}}$ simply runs the robust classifier ${\mathsf{R}}$ and returns the answer. It can do this in polynomial time because ${\mathsf{R}}$ is also polynomial time computable.

Now a hybrid argument finishes the proof as the following distributions are computationally indistinguishable for ${\mathsf{R}}$:

where the two $\approx_{c}$ statements follow from Eq. 1 and the $\equiv$ follows from the fact that adding any fixed vector to the uniform distribution still remains uniform.

3 Efficient Robust Classifier Exists but is Hard to Learn

where both are uniform distributions on the sets and $\bm{1}$ is the all ones vector on $8n$ dimensions.

The learning task has the following properties.

(Learnability) A classifier to distinguish $D_{0}$ from $D_{1}$ can be learned from the samples efficiently. Furthermore, it is easy to learn a generator/ evaluator for these distributions.

(Existence of an Efficient Robust Classifier) There exists an efficient robust classifier ${\mathsf{R}}$ such that,

where \varepsilon=\mathopen{}\mathclose{{}\left\lfloor\sqrt{n}}\right\rfloor and $B(y,\varepsilon)=\{y^{\prime}:\|y-y^{\prime}\|_{\sf{Ham}}\leq\varepsilon\}$.

(Unlearnability of Robust Classifier) There exists a perturbation algorithm such that no efficiently learned classifier can classify better than chance.

We drop $\mathbf{H}$ from the notation to avoid clutter and denote the distributions as $D_{0},D_{1}$. Here $\mathbf{H}$ functions as the parity check matrix of the code $D_{0}$ and $D_{1}$ is a shift of the code. Observe that Part (1): distinguishing between $D_{0}$ and $D_{1}$ is easily done by Gaussian elimination.

We want to show that (2) a robust classifier exists, and, (3) it is difficult to find any robust classifier efficiently. We argue this in the subsequent claims.

Consider the following robust classifier:

If \mathopen{}\mathclose{{}\left\|\bm{z}}\right\|_{\sf{Ham}}\leq n output otherwise, output $1$.

The correctness of the robust classifier follows from the fact that $\mathbf{E}$ is a sparse matrix where each column has Hamming weight at most $t$. Consider the case when $\bm{y}\leftarrow D_{0}$, the other case is analogous. Observe that,

where \mathopen{}\mathclose{{}\left\|\bm{\epsilon}}\right\|_{\sf{Ham}}\leq\varepsilon\leq\sqrt{n}. Hence,

where the second equality follows from the fact that $\mathbf{H}y=0\bmod 2$ and that $\operatorname{rowspan}(E)\subseteq\operatorname{rowspan}(H)$. Observe that each column of $\mathbf{E}$ has at most $t$ ones and that the Hamming weight of $\bm{\epsilon}$ is at most $\varepsilon$. As, $\mathbf{E}\bm{\epsilon}=\sum_{j:\epsilon_{j}=1}\bm{e}_{(\cdot,j)}$, we can bound the Hamming weight \mathopen{}\mathclose{{}\left\|\mathbf{E}\bm{\epsilon}}\right\|_{\sf{Ham}}\leq t\mathopen{}\mathclose{{}\left\|\bm{\epsilon}}\right\|_{\sf{Ham}}\leq t\cdot\varepsilon\leq n/3. Hence the classifier would always correctly classify adversarially perturbed samples from $D_{0}$.

In the other case when $b=1$ observe that $\mathbf{E}\cdot\bm{1}=\bm{1}$ because each row of $\mathbf{E}$ has Hamming weight $t$ which is odd. Hence the Hamming weight of $\bm{z}$ is at least $2n-n/3>n$ in this case and would be classified correctly. This proves that a robust classifier exists. ∎

There exists a perturbation algorithm ${\mathsf{P}}$ such that for every polynomial time learner ${\mathsf{L}}$, the learner ${\mathsf{L}}$ has no advantage over chance in classifying examples perturbed by ${\mathsf{P}}$. That is,

This proof is identical to the proof of security of Aleknovich’s public key encryption scheme [Ale03].

Observe that $D_{0},D_{1}$ are completely specified by the matrix $\mathbf{H}$. So, the learner gets $\mathbf{H}$ instead of sample access. Consider the following random perturbation algorithm ${\mathsf{P}}$:

Suppose an efficient learner ${\mathsf{L}}$ exists that can succeed in this game with high probability, we can break the learning parity with noise assumption. This is done in two steps. In the first step, we replace the parity check matrix $\mathbf{H}$ with a uniformly random matrix $\mathbf{H}^{\prime}$ this should not noticeably change the success probability because the two distributions are indistinguishable. In the second step, now observe that $\mathbf{H}^{\prime}$ is a uniformly random parity check matrix hence gives rise to a random code. Now we can apply the LPN assumption again, this time to replace the error $\bm{\epsilon}$ by a uniformly random vector and not noticably change the success probability. This is a contradiction.

Learning with Errors

We have written specific versions of the LWE assumption. LWE is conjectured to be hard for a large setting of parameters. For a discussion on parameters, see [Pei16].

We say that a pair of algorithms $(\mathsf{Preprocess},{\mathsf{D}})$ where $\mathsf{Preprocess}$ is possibly inefficient and ${\mathsf{D}}$ is efficient, solves $\mathsf{LWE}_{n,m,t}$ if ${\mathsf{D}}$ can distinguish an LWE sample from a random sample given the trapdoor ${\mathsf{trap}}$ generated by $\mathsf{Preprocess}(\mathbf{A})$.

The Learning Parity with Noise problem is hard even with preprocessing in the constant noise regime. We state the assumption below formally.

A trapdoor for $A$ is a short basis for the lattice $L^{\perp}(A)$.

In the case of LWE, it is known that we can sample matrices $\mathbf{A}$ from a distribution statistically close to uniformly random along with a trapdoor which allows for efficient distinguishing and recovering the lattice point from a noisy one, for close distances (this is referred to as bounded distance decoding).

The output distribution of $\mathbf{A}$ is statistically close to uniform (total variation distance $<2^{-O(n)}$).

2 No Efficient Robust Classifier Exists

In this section we describe a learning task based on LWE that has no robust classifier. This is identical to the LPN based task except the noise distribution is set differently.

The learning task has the following properties.

(Learnability) A classifier to distinguish $D_{0}$ from $D_{1}$ can be learned from the samples efficiently. Furthermore, it is easy to learn a generator/ evaluator for these distributions.

(No Efficient Robust Classifier Exists) There exists a perturbation algorithm ${\mathsf{P}}$ such that there exists no efficient robust classifier ${\mathsf{R}}$ such that,

The proof is identical to the LPN case, with the perturbation adversary ${\mathsf{P}}$ instead adding noise distributed according to $\chi^{m}$.

3 An Efficient Robust Classifier Exists but is Hard to Learn

where both are uniform distributions on the sets and $\bm{1}$ is the all ones vector on $m$ dimensions. We drop $\mathbf{A}$ from the notation to avoid clutter and denote the distributions as $D_{0},D_{1}$.

Hence, the task consists of distinguishing lattice vectors from an affine shift of the lattice. That is, given a vector $x\in(D_{0}\cup D_{1})$, classify weather $x\in D_{0}$ or $x\in D_{1}$. Gaussian elimination accomplishes this task easily. We want to show that (a) a robust classifier exists, and, (b) it is difficult to find any robust classifier efficiently. We argue this based on the learning with errors assumption.

The learning task has the following properties.

(Learnability) A classifier to distinguish $D_{0}$ from $D_{1}$ can be learned efficiently.

(Existence of Robust Classifier) There exists a robust classifier ${\mathsf{R}}$ such that,

(Unlearnability of Robust Classifier) There exists a perturbation algorithm such that no efficiently learned classifier can classify better than chance.

Consider the following robust classifier ${\mathsf{R}}$:

If \bm{z}\in\mathopen{}\mathclose{{}\left\{\frac{-q}{4},\dots,\frac{q}{4}}\right\}^{n} output otherwise, output $1$.

The correctness of the robust classifier follows from the fact that $\mathbf{T}$ is a zero-one matrix and that the errors are bounded in size. Consider the case when $\bm{y}\leftarrow D_{0}$, the other case is analogous. Observe that,

where $\|\bm{e}\|_{\infty}\leq\frac{q}{4m}$. Hence,

As $\mathbf{T}$ has only zero-one entries, $\bm{e}^{T}\mathbf{T}$ is bounded over integers with the absolute value of each coordinate being at most $m\cdot\|\bm{e}\|_{\infty}\leq\frac{q}{4}$. This implies that the robust classifier would correctly output 0 when given perturbed samples from $D_{0}$. ∎

In order to show that it is difficult to recover the robust classifier, we rely on the learning with errors assumption. We consider a perturbation adversary that simply adds random noise to the sample it receives.

There exists a perturbation algorithm ${\mathsf{P}}$ such that for every polynomial time learner ${\mathsf{L}}$, the learner ${\mathsf{L}}$ has no advantage over chance in classifying examples perturbed by ${\mathsf{P}}$. That is,

Observe that $D_{0},D_{1}$ are completely specified by the matrix $\mathbf{A}$ and given $\mathbf{A}$ can be sampled efficiently. So, it suffices to give the learner $\mathbf{A}$ instead of sample access. Consider the following random perturbation algorithm ${\mathsf{P}}$:

So, the experiment above is equivalent to the following:

The cruical observation is that the learner’s job is to distinguish LWE samples $(\mathbf{A},\bm{s}^{T}\mathbf{A}+\bm{e}^{T})$ from shifted LWE samples $(\mathbf{A},\bm{s}^{T}\mathbf{A}+\bm{e}^{T}+\frac{q}{2}\bm{1}^{T})$. The LWE assumption implies that this is difficult because the two distributions are indistinguishable. That is,

and hence no efficient adversary ${\mathsf{L}}$ can distinguish between the distribution when $b=0$ from when $b=1$. And hence for any efficient adversary, the success probability of classifying these perturbed instances is negligibly close to a half, as desired. ∎

Hence, we have described a learning task that is learnable, has a robust classifier, but robust classifiers are computationally hard to learn.

Using Pseudorandom Functions and Error Correcting Codes

In this section, we formally describe the hard-to-robustly learn task based on one-way functions. There are two main ingredients that we use to construct the learning task: Error Correcting Codes (ECCs) and Pseudorandom Functions (PRFs).

An uniquely decodable binary error correcting code allows encoding messages to redundant codewords such that from any codeword perturbed to some degree, we can recover the encoded message.

An uniquely decodable binary error correcting code, $C:\{0,1\}^{n}\rightarrow\{0,1\}^{m}$ consists of two efficient algorithms ${\mathsf{Encode}},{\mathsf{Decode}}$. The code tolerates error fraction $e$ if for all messages $x\in\{0,1\}^{n}$,

where $B({\mathsf{Encode}}(x),em)$ denotes the Hamming ball of radius $em$.

We know very good error correcting codes.

For any constant $\gamma>0$, there exists a binary error correcting code $C:\{0,1\}^{n}\rightarrow\{0,1\}^{m}$ where $m=O(n/\gamma^{3})$ with a decoding radius of $(\frac{1}{4}-\gamma)m$ with polynomial time encoding and decoding.

We will use this coding scheme with $\gamma=1/8$ giving us an error correcting code $C:\{0,1\}^{n}\rightarrow\{0,1\}^{m}$ where $m=\theta(n)$ and tolerates $m/8$ errors for unique decoding.

A pseudorandom function is a keyed function $F_{k}:\{0,1\}^{n-1}\rightarrow\{0,1\}$ where the secret key is picked uniformly random such that, for every efficient adversary, the output of the function is indistinguishable from the output of a random function. A more formal definition is given below. It is known that pseudorandom functions can be constructed from one-way functions.

where ${\mathcal{U}}_{n}$ is the uniform distribution over all functions from $\{0,1\}^{n}$ to $\{0,1\}$.

Pseudorandom functions exist if one-way functions exist.

Next, we informally describe the learning task. Consider the following learning task: The two distributions $D_{0},D_{1}$ are parameterized by the PRF key $k$ and defined as follows:

So, the two distributions are tuples where the first half is which distribution the sample was taken from and the second an error correcting code applied to the tuple $(x,F_{k}(x)+b)$, that is, either the PRF evaluation at the location $x$ or its complement. Note that without the first bit, classifying the original distributions is computationally infeasible. The pseudorandom function looks random at every new location. Including the bit in the sample itself makes the unperturbed classification task easy. The error correcting code ensures that we have a robust classifier.

Let \mathopen{}\mathclose{{}\left\{F_{k}}\right\} for $F_{k}:\{0,1\}^{n-1}\rightarrow\{0,1\}$ be a pseudorandom function family and $C:\{0,1\}^{n}\rightarrow\{0,1\}^{m}$ where $m=\theta(n)$ be an efficiently decodable error correcting code with decoding algorithm $\sf{Decode}$ that tolerates $m/8$ errors.

Consider the following learning task. For a random pseudorandom function key $k$, define:

supported on $\{0,1\}^{m}$. The learning task has the following properties.

(Easy to Learn) A classifier to distinguish $D_{0}$ from $D_{1}$ can be learned from the samples efficiently.

(Robust Classifier Exists) There exists a robust classifier ${\mathsf{R}}$ such that,

where $m/8$ is the decoding radius and $B(y,d)=\{y^{\prime}:\|y-y^{\prime}\|_{\sf{Ham}}\leq d\}$.

(A Robust Classifier is hard-to-learn) There exists a perturbation algorithm such that no efficiently learned classifier can classify perturbed adversarial examples better than chance.

To prove Part (1) consider the classifier that outputs the first bit. It works correctly on instances from the distributions. To prove Part (2), we rely on the decoding algorithm. After $d=m/8$ edits to the sample, we can recover the underlying message by ignoring the first bit of the tuple and decoding the rest to get the underlying message of the form $(x,c)$ and then use the PRF to classify. More formally, consider the following robust classifer:

Observe that error correcting code ensures that from every perturbed sample, we efficiently recover the encoded message. And then because the message is of the form $(x,F_{k}(x)+b)$ for class $b$, this allows for correct classification.

To show Part (3), we rely on the unlearnability of the PRF. Consider a perturbing adversary that replaces the first bit of the sample by 0. Classification is now equivalent to predicting $F_{k}(x)$ given $x$. Because predicting $F_{k}(x)$ is computationally infeasible to learn, so is a robust classifier. ∎

Note that, compared to the previous counter-examples, this example does not rely on public key assumptions. The reason for that is that the samples here are “evasive”. In that there is no way to generate fresh samples from the two distributions. So, we cannot translate this to a public key encryption scheme because to encrypt, we need a samples from the distributions $D_{0},D_{1}$ along with the perturbing adversary and we do not have access to these samples.

The hardness of this task comes from the hardness of learning the PRF and not from the perturbations. This is different from the schemes based on LPN and LWE.

Using Average-Case Hardness and Error Correcting Codes

In this section, we formally state Theorem 2.1 and provide the proof outlined in Section 3.4. We also give an alternative construction that relies on one-way-permutations, but yields a classification problem with distributions that are efficiently samplable.

We first need the notion of an average-case hard function.

A boolean function $g:\{0,1\}^{n}\to\{0,1\}$ is $(s,\delta)$-average-case hard if for all non-uniform probabilistic algorithms $A$ running in time $s$,

There exists functions $g$ which are $(2^{\Theta(n)},1/2-2^{-\Theta(n)})$-average-case hard (a random function $g$ will suffice with constant probability).

Let $g:\{0,1\}^{n}\rightarrow\{0,1\}$ be a function that is $(2^{\Theta(n)},1/2-2^{-\Theta(n)})$-average-case hard, and let ${\mathsf{Encode}}:\{0,1\}^{n+1}\rightarrow\{0,1\}^{m}$ where $m=\theta(n)$ be an efficiently decodable error correcting code with decoding algorithm $\sf{Decode}$ that tolerates $m/8$ errors.

Consider the following classification task. Define:

This classification task has the following properties.

(Easy to Classify) An efficient classifier to distinguish $D_{0}$ from $D_{1}$ exists.

(Robust Classifier Exists) There exists a inefficient robust classifier ${\mathsf{R}}$ such that,

where $m/8$ is the decoding radius and $B(y,d)=\{y^{\prime}:\|y-y^{\prime}\|_{\sf{Ham}}\leq d\}$.

(No Efficient Robust Classifier Exists) There exists a perturbation algorithm ${\mathsf{P}}$ such that there exists no polynomial-time robust classifier ${\mathsf{R}}$ such that,

This proof closely follows the proof of Theorem 7.5. For Part (1), the classifier that simply outputs the first bit is always correct. For Part (2), we can robustly classify by using the error correcting code to recover the message $(x,g(x))$ or $(x,1-g(x))$, and then we can compute the function $g$ to distinguish between these cases. Specifically, the robust classifier is identical to the one presented in the proof of Theorem 7.5, but computing the function $g$ instead of $F_{k}(x)$. For Part (3), we rely on the average-case hardness of $g$. Consider the perturbation adversary that replaces the first bit of the sample by 0. Now, classifying $D_{0}$ vs $D_{1}$ with non-negligible advantage is equivalent to predicting $g(x)$ given $x$ with non-negligible advantage. This is impossible in polynomial time by the average-case hardness of $g$, and thus efficient robust classification is impossible. ∎

We now describe how to achieve the above properties with distributions that are efficiently samplable. First, recall the notion of a hard-core bit: Let $f:\{0,1\}^{n}\to\{0,1\}^{n}$ be a one-way function. A predicate $b:\{0,1\}^{n}\to\{0,1\}$ is a hard-core bit for $f$ if for all probabilistic polynomial-time algorithms $A$,

Let $f:\{0,1\}^{n}\rightarrow\{0,1\}^{n}$ be a one-way permutation, and let $b:\{0,1\}^{n}\to\{0,1\}$ be a hard-core bit for $f$. Let ${\mathsf{Encode}}:\{0,1\}^{n+1}\rightarrow\{0,1\}^{m}$ where $m=\theta(n)$ be an efficiently decodable error correcting code with decoding algorithm $\sf{Decode}$ that tolerates $m/8$ errors.

Consider the following classification task. Define:

This classification task has the following properties.

(Easy to Classify) An efficient classifier to distinguish $D_{0}$ from $D_{1}$ exists.

(Robust Classifier Exists) There exists a inefficient robust classifier ${\mathsf{R}}$ such that,

where $m/8$ is the decoding radius and $B(y,d)=\{y^{\prime}:\|y-y^{\prime}\|_{\sf{Ham}}\leq d\}$.

(No Efficient Robust Classifier Exists) There exists a perturbation algorithm ${\mathsf{P}}$ such that there exists no polynomial-time robust classifier ${\mathsf{R}}$ such that,

(Efficiently Samplable) The distributions $D_{0},D_{1}$ can be sampled in polynomial time.

Parts (1)-(3) follow exactly as in the proof of Theorem 8.2. Note that an inefficent distinguisher can invert $f(x)$ to find $x$, and compute $b(x)$. For Part (4), both distributions are clearly efficiently samplable, by first sampling $x$ and then computing $f(x),b(x)$. ∎

Cryptography from Robustly Hard Tasks

In this section, we show that the existence of tasks with a provable gap in classification and robust classification implies one-way functions and hence a variety of cryptographic primitives that include pseudorandom functions, symmetric key encryption among others.

Provably hard-to-learn robust classifiers imply one-way functions. Given a learning task $D_{0},D_{1}$ such that,

(Robust Classifier Exists) There exists a robust classifier ${\mathsf{R}}$ such that,

where $d$ is the decoding radius and $B(y,d)=\{y^{\prime}:\|y-y^{\prime}\|_{\sf{Ham}}\leq d\}$.

(A Robust Classifier is hard-to-learn) There exists an efficient perturbing adversary ${\mathsf{P}}$ such that every efficiently learned classifier ${\mathsf{L}}$ is not a robust classifier. That is, for a learning task $D_{0},D_{1}\leftarrow\sf{Samp}(n)$ and classifier ${\mathsf{L}}$,

The proof of this theorem relies on fact that we can construct one-way functions from any two distributions that are staistically far and computationally close. The two distributions considered are the perturbed distributions. That is,

We show that these two distributions are statistically far and yet computationally indistinguishable giving one-way functions. They are statistically far because the robust classfier can distinguish between them. Hence, the total variation distance between the two has to be large. And that they are computationally close because no efficient algorithm can distinguish between the two. Hence one way functions exist.

We formally state the theorem used below.

Given a pair of distributions $(X_{0},X_{1})\leftarrow{\mathcal{F}}$ over ${\mathcal{X}}$ that are statistically far,

and computationally indistinguishable. That is for every polynomial time adversary ${\mathsf{A}}$ that gets sample access to the distributions,

Then one-way functions exist.The constants in the equations are fairly arbitrary. We can replace them by any constants $\alpha,\beta$ where $\alpha^{2}>\beta$ and the result holds.

We want to show that these two distributions are statiscally far and computationally close. This relies on the existence of the robust classifier and the difficultly of learning one respectively.

We start by showing that, $d_{TV}(D^{\prime}_{0},D^{\prime}_{1})\geq 0.8$. To observe this, consider the robust classifier as the distinguisher. This implies that,

On the other hand, any efficient distinguisher cannot distinguish between the samples by the assumption. Hence we are done. ∎

The two distributions described above have the following public-key encryption flavor: the robust classifier can serve as the decryption algorithm to distinguish between samples from the perturbed distributions $D_{0}^{\prime},D_{1}^{\prime}$. If after seeing enough samples, the learning algorithm can generate fresh samples from the two unperturbed distributions $D_{0},D_{1}$ then we also have an encryption algorithm: to encrypt a bit $b$, first sample from the distribution $D_{b}$ and run the perturbation adversary ${\mathsf{P}}$ to generate the encryption of the bit. To decrypt, use the robust classifier.

There are two key ingredients missing: (1) The encryption algorithm ${\mathsf{P}}$ needs access to fresh samples from the two distributions to encrypt. There are learning tasks where we do not have access to these. (2) The ability to sample the robust classifier along with descriptions of the learning tasks. This might not be feasible, especially when the tasks are not chosen, but supplied by nature.

Acknowledgments.

We would like to thank Shafi Goldwasser and Nadia Heninger for discussions regarding inversion of the (noisy) BBS PRG.

References

Appendix A A Description of BLPR Example and the Blum-Blum-Shub PRG.

In this section, we describe the BLPR counter-example and the Blum-Blum-Shub pseudorandom generator.

We start by defining the notion of a trapdoor pseudorandom generator. A trapdoor pseudorandom generator ${\mathsf{TrapPRG}}:\{0,1\}^{n}\rightarrow\{0,1\}^{2n}$ is an expanding function whose outputs are indistinguishable from truly random strings. That is, \mathopen{}\mathclose{{}\left\{{\mathsf{TrapPRG}}(x):x\leftarrow\{0,1\}^{n}}\right\}\approx_{c}\mathopen{}\mathclose{{}\left\{y:y\leftarrow\{0,1\}^{2n}}\right\}. Furthermore, the function has a trapdoor ${\mathsf{trap}}$ that allows distinguishing the output of the PRG from random outputs. That is, there exists a distinguisher ${\mathsf{D}}$ that given the trapdoor,

Given a trapdoor PRG, the BLPR learning task $D_{0},D_{1}$ is the following:

We describe the BBS PRG and its trapdoor property next. The Blum-Blum-Shub pseudorandom generator is defined as follows:

Output $y_{1},y_{2},\dots,y_{m-1},x_{m}$.

The trapdoor property BLPR refer to construct the robust classifier is the following one: In the construction of the PRG, the security does not rely on outputting the last entry ($x_{m}$) in its entireity. Though doing so enables the following “trapdoor” property:

There exists a distinguisher ${\mathsf{D}}$ that given the factorization of $N$ can distinguish between the output of the $\sf{BBSPRG}$ from random strings. That is,

The proof relies on the fact that Rabin’s one way function $f(x)=x^{2}\bmod N$ is a trapdoor function that can be efficiently inverted given the factorization of $N$. Furthermore, the inverse returned is the only square root of $x^{2}$ that is a square itself. Hence the distinguisher does the following:

Interpret the input as $y_{1},y_{2},\dots y_{m-1},x_{m}$.

If $x_{m}$ is not a square mod $N$, output .

Compute $x_{1},x_{2},\dots x_{m-1}$ as $x_{i}=f^{-1}(x_{i+1})$.

If $y_{i}={\sf hcb}(x_{i})$ for all $i$, return $1$, else return .

Observe that the distinguisher always outputs $1$ on outputs of the PRG. On the other hand, when fed a random string, $x_{m}$ is not a square with probability $3/4$ and even when it is a square, the probability of each $y_{i}={\sf hcb}(x_{i})$ is exactly $1/2$ independently. Hence the probability that the distinguisher outputs $1$ on a random string is $\frac{1}{4}\cdot(\frac{1}{2})^{m-1}$ which is tiny. ∎

Based on this, the BLPR counterexample is the following:

Let $N=pq$ where $p,q$ are random $n$-bit primes of the form $3\pmod{4}$. Let $m=n^{2}$. Define $D_{0},D_{1}$ as:

Then, the learning task has the following properties: (1) The distributions are easy to classify non-robustly. (2) There exists an inefficient robust classifier for $\varepsilon=\theta(\sqrt{n})$. (3) No efficiently learned classifier can classify better than chance. (4) Given the factorization of $N$, there exists an efficient robust classifier for $\varepsilon=\theta(\sqrt{n})$.

Properties 1, 2, 3 are true. To the best of our knowledge, 4 is not known to be true. As we described earlier, we know of robust classifiers for $\varepsilon=O(1)$. This leaves us with the following open questions.

Given factorization of $N$, prove that there exists an efficient robust classifier for $\varepsilon=\omega(1)$-bits.

(Perturbation Adversary 1) Consider the perturbation adversary that erases the first bit and adds random noise to each bit of the PRG with prob $1/\sqrt{n}$. Given the factorization a $N$, does there exists an efficient robust classifier for this adversary.

(Perturbation Adversary 2) The adversary deletes the last complete entry output by the PRG (i.e., $x_{m}$). Given the factorization of $N$, can we distinguish this PRG from random, when no other error is added.

Although BBS is a trapdoor PRG, it crucially relies on the fact that $x_{m}$, the last value is available completely intact. Without access to this value, BBS is still a PRG but it is not clear how to do the trapdoor decoding.

As we described earlier, Open Question 3 is a long-standing open question in the computational number theory community [Hen19, Gre13]. And Open Question 1 is a harder variant of that question. Finally, Question 2 asks a error correction or decoding question – given the output of a PRG with random errors, can you recover the original PRG string (even given some trapdoor). We are not aware of any way in which this factorization actually helps decoding under random noise.