Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: - The authors propose SALSA, an attack on LWE-based cryptographic schemes, which has emerged as quantum-resistant cryptosystem, based on machine learning. 
- The authors demonstrate that the process of modular arithmetic can be trained using transformer.
- Using trained transformer, the authors show that the instances from LWE can be distinguished from random instances.
- The authors propose two secret recovery algorithms, `direct secret recovery` and `distinguisher secret recovery`, and they justify these algorithms theoretically.
strengths_and_weaknesses: # Strengths
- The idea to perform modular arithmetic using a transformer seems interesting and novel.
- The method can recover secret even though the trained transformer has low-accuracy.
- Tables in the appendix are very helpful. For example, Table 20 and Table 21 helps me understand the broad effectiveness of the method.

# Weaknesses
- The algorithms require large computational resources and long runtime.
- Scalability of the method with respect to the dimension of the lattice seems poor. 
questions: - Does the runtime on Table 2 contain the training time? If not I want to see the training time of transformers used in the paper.
- If the authors can conduct other baseline methods on their machine, I want to see the comparison on runtime required for SALSA and the baseline methods on the same device. 

POST REBUTTAL COMMENTS : The authors answer the questions. My concerns have been addressed and I decide to maintain my score.
limitations: That said, I wish that the authors include ethics or broader-impact statement in the paper or appendix.
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: The paper proposes a machine learning approach to modular arithmetic and to breaking LWE-based cryptosystems based on said arithmetic.

strengths_and_weaknesses: The solved instances are trivial. For example, the last instance in Table 2 corresponds to finding a 128-bit secret of which all but three bits are zero. There are only $128 choose 3 = 341,376$ such secrets. I suspect this number of secrets can be tried in much less than the 23 hours it took this work. I think it's not appropriate to say this is comparable to the Darmstadt challenge where the secret is chosen uniformly at random from the whole domain, that is $n$ values modulo $q$, where $n \in [40,120]$ and $q$ is several thousand. The density of 0.002 is used with $n$ more than 10,000 leading to a much much larger number of possibilities.

The authors only show figures for reducing density with increasing dimension. This limits the possibilities for the secret. I think it's therefore overblown to say that the solution "may scale to attack real-world LWE-based cryptosystems".

questions: Do you agree that the running time of secret recovery roughly corresponds to the number of possible secrets?

limitations: yes
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper performs cryptanalysis of the LWE problem using transformer models. They show that transformers can learn modular arithmetic. This justifies that, in principle, a transformer can learn the mapping from LWE inputs to outputs. They then show two ML-based cryptanalysis strategies which involve learning the LWE function and using this function to recover the secret. They evaluate on moderately-sized LWE problems.
strengths_and_weaknesses: Strengths:

The paper is a pleasant read. It includes a good amount of problem-specific background.

SALSA is a novel attack on LWE. Regardless of whether SALSA in its current incarnation will be able to scale to larger problems, I think this is an interesting path for further investigation. SALSA also appears to have some principled justification.

There is a healthy amount of ablation and understanding how SALSA performs at different parameter settings. This is important for any new application of ML, and especially for a cryptanalysis technique.

Weaknesses:

The modular arithmetic results are not very well connected to the LWE results. My understanding of models' struggles with arithmetic is more that they're bad at extrapolating beyond the arithmetic they see in training. Modular arithmetic doesn't really require extrapolation, which might make this less interesting a result.

SALSA is not as interpretable as existing cryptanalysis techniques. That is, while it may be able to argue that a certain parameter setting is breakable, it is difficult to extrapolate how well SALSA will work on more real-world problems. Indeed, there is already some strange non-monotonicity in SALSA's performance: from n=90 -> n=110 (in Table 2), SALSA requires fewer samples and less running time.

It is unclear whether SALSA can simultaneously handle higher Hamming weights and higher dimension.
questions: The strategy relies on being able to make predictions on these a_i vectors given random LWE samples. Could you attempt to measure the train/test overlap here? What is the closest vector in the (expanded) training set to the a_i vectors?

Does SALSA ever manage to extract a Hamming weight 5 secret? I see Hamming weight 4 secrets are possible if n < 70. Can you argue a bit more why this small Hamming weight limitation seen in the experiments is not inherent to the approach?

The training data expansion technique seems to bear some resemblance to sieving-based SVP algorithms. Could you comment on this? Could it be helping?

Since an epoch consists of 300000 examples (rather than a full pass through the training set), are there any examples seen multiple times?
limitations: I think the authors discuss limitations with SALSA as it exists, but I think they are more optimistic about SALSA than is backed up by their experiments.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper tackles LWE, a so-called *hard learning problem* by training transformers models. The general idea is to feed a model with tuples of data/labels that are instances of an LWE distribution. If the model learns something, that means that it has implicitly guessed the secret variable $s$. The authors then proposes two ways to *extract* the secret $s$ from a model, in order to solve LWE.

After first demonstrating the efficiency of transformers models on modular arithmetic, the authors apply their technique on a special instance of LWE, namely with low-density binary secrets, in dimensionalities not yet close cryptographic-use, but still far from trivial. Based on these experimental outcomes, the authors argue to what extent the technique could scale to more realistic instances of LWE for cryptographic puposes.
strengths_and_weaknesses: Except for a few typos, the paper is well-written and easy to follow. The authors concisely introduce all the cryptographic material necessary to grasp the LWE problem. The principles of the attack are intuitive to follow. The parameters of the problem are clearly stated and discussed. The only drawback I could notice is that it does not introduce the transformers model, nor its variants that are yet mentioned and discussed throughout the paper. I guess that most of the target audience is familiar with such models, but I wish it could not have been assumed.
Overall, I enjoyed reading this paper. Moreover, the contribution seems original enough to me, and to the best of my knowledge, I am not aware of missing references close to this work.

My main concern about this papers covers the significance of the results. The authors deal with some parameters of the problem (the dimensionality $n$, the density of the secret, the modulus $q$ that are not yet cryptographic standards, although this is honestly and clearly stated by the authors. And despite, the parameters remain far from trivial. 
Yet, the latter point sets the ground for the authors to argue to what extent their work could be extended to higher parameters in future works. Whether this extension is credible would imply the significance of the paper. And so far, I am not fully convinced that the difficulty only results from the intrinsic hardness of the LWE problem (as hypothesized l.272). I elaborate hereafter.

I have been aware of some works [1,2] explaining and quantifying the length of the initial plateau in the loss function in Figure 3. For example, it is known that the *learning parity* problem (i.e. for $q=2$, and $\sigma=0$), can be efficiently solved thanks to Gaussian elimination, but cannot be efficiently solved with gradient descent, regardless of the underlying model ($i.e.$ whether using transformers or not). Indeed, the initial plateau may have a length exponential with the parameter $n$ (removing the sparsity assumption). I assume that with low noise levels such as those considered in the paper, and with higher values of $q$, the same argument might apply. If so, this would be provably hard to solve (some instances of) LWE with gradient descent, whereas those LWE instances would not be cryptographically *hard*.

[1] https://proceedings.neurips.cc/paper/2020/hash/e7e8f8e5982b3298c8addedf6811d500-Abstract.html

[2] https://proceedings.mlr.press/v70/shalev-shwartz17a.html
questions: Any thought regarding my comment on the limitation of gradient descent? Do you think that it formally applies to your problem? Regardless of your answer, I think it would be valuable to add a discussion about that.

limitations: No big limitation, except maybe the one I raised in the strength/weaknesses.
review_title: null

Meta-review: metareview: The authors propose SALSA: a machine learning attack on cryptographic schemes based on Learning With Errors (LWE) as the underlying hard problem. They show that SALSA recovers secrets of small and medium size LWE instances with sparse binary secrets. The main selling point is that if the attack could scale up, it may pose a real treat to real-world LWE-based cryptosystems.

The reviewers found use of transformers to perform modular arithmetic interesting. At the same time, I agree with the reviewers that given the current computational complexity of the attack and given its poor scalability in the dimension of the lattice could potentially prevent its deployment in real-world systems. As such despite the merit of the paper, I find it to be a borderline submission.
confidence: Less certain
Decision: Accept