SALSA: Attacking Lattice Cryptography with Transformers
Authors: Emily Wenger
Mingjie Chen
Francois Charton
Kristin Lauter
Venue: NeurIPS 2022 Accept (2022)
Keywords: machine learning
cryptanalysis

Abstract: Currently deployed public-key cryptosystems will be vulnerable to attacks by full-scale quantum computers. Consequently, "quantum resistant" cryptosystems are in high demand, and lattice-based cryptosystems, based on a hard problem known as Learning With Errors (LWE), have emerged as strong contenders for standardization. In this work, we train transformers to perform modular arithmetic and mix half-trained models and statistical cryptanalysis techniques to propose SALSA: a machine learning attack on LWE-based cryptographic schemes. SALSA can fully recover secrets for small-to-mid size LWE instances with sparse binary secrets, and may scale to attack real world LWE-based cryptosystems.

SALSA: Attacking Lattice Cryptography with Transformers
Emily Wenger University of Chicago
Mingjie Chen University of Birmingham
Francois Charton ? Meta Al
Kristin Lauter
Meta AI
Abstract
Currently deployed public-key cryptosystems will be vulnerable to attacks by full-scale quantum computers. Consequently, "quantum resistant" cryptosystems are in high demand, and lattice-based cryptosystems, based on hard problem known as Learning With Errors (LWE), have emerged as strong contenders for standardization. In this work, we train transformers perform modular arithmetic and mix half-trained models with statistical cryptanalysis techniques to propose SALSA: machine learning attack on LWE-based cry cryptographic schemes. SALSA can fully recover secrets for small-to-mic size LWE instances with sparse binary secrets, and may scale attack real-world LWE-based cryptosystems.
Introduction
The looming threat of quantum computers has upended the field of cryptography. Public-key cryptographic systems have at their heart a difficult-to-sole math problem that guarantees their security. The security of most current systems (e.g. (58] 28 50) relies on problems such as integer factorization, or the discrete logarithm problem in an abelian group. Unfortunately. these problems are vulnerable to polynomial time quantum attacks on large-scal quantum computers due to Shor's Algorithm [62]. Therefore, the race is on to find new post-quantum cryptosystems (PQC) built upon alternative hard math problems.
Several leading candidates in the final round of the 5-year NIST PQC competition are latrice-based based cryptosystems, based on the hardness of the Shortest Vector Problem (SVP) (2). which involves finding short vectors in high dimensional lattices. Many cryptosystems have been proposed based on hard problems which reduce to some version of the SVP. and known attacks are largely based on lattice-basis reduction algorithms which aim to find short vectors via algebraic techniques. The LLL. algorithm 43 was the original template for lattice reduction, and although runs in polynomial time (in the dimension of the lattice), it returns an exponentially bad approximation to the shortest vector. It an active area of research [22 48 5 to fully understand the behavior and running time of wide range of lattice-basis reduction algorithms, but the best known classical attacks on the PQC candidates run in time exponential in the dimension of the lattice.
In this paper, we focus on one of the most widely used lattice-based hardness assumptions: Learning With Errors (LWE) (56). Given dimension n. an integer modulus g. and secret vector s E Z the learning with errors problem is to find the secret given noisy inner products with random vectors. LWEe-based encryption schemes encrypt a message by blinding it with noisy inner product. Given random vector Z the noisy inner product is = a S + mod g. where is an "error" vector sampled from a narrow Gaussian distribution (so entries are small, thus the reference noise).
"Co-first authors, work done while at Meta AI CCo-last authors
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Interestingly, the assumption for cryptographic applications is that the Learning With Errors problem hard: given lot of noisy inner products of random vectors with secret vector, it should be hard to learn the secret vector. However, in Machine Learning we make the opposite assumption: given a lot of noisy data, we can still learn patterns from it. So this paper we investigate the possibility to train ML models to learn from LWE samples.
To that end, we propose SALSA, a technique for performing Secret-recovery Attacks on LWE via Sequence to sequence models with Attention. SALSA trains a language model to predict b from a, and we develop two algorithms to recover the secret vector s using this trained model.
Our paper has three main contributions. We demonstrate that transformers can perform modular arithmetic on integers and vectors. We show that transformers trained LWE samples can be used to distinguish LWE instances from random. This can be further turned into two algorithms that recover binary secrets. We show how these techniques yield practical attack LWE based cryptosystems and demonstrate its efficacy in the cryptanalysis of small and mid-size LWE instances with sparse binary secrets. Our code is available /tttts:ttgiiiiie how.a///ooooaacoooooooeeeeeeee
2 Lattice Cryptography and LWE
2.1 Lattices and Hard Lattice Problems
An integer lattice of dimension n over Z is the set of all integer linear combinations of n lin- early independent vectors in Z". In other words, given n such vectors V; nd i Nn. we define the lattice vv.) == 1 a;V; ag E Z). Given a lattice A, the Shortest Vector Prob- lem (SVP) asks for a nonzero vector v E A with minimal norm. Figure I depicts solution to this problem in the trivial case of 2-dimensional lattice, where b and 2 generate lattice A and the green vector is the shortest vector in A.
b2
Figure 1: The dots form a lattice A, generated by vec- tors b b2. v is the shortest vector in A.
The best known algorithms to find exact solutions SVP take exponential time and space with respect to n, the dimension of the lattice [49]. There exist lattice reduction algorithms to find approximate shortest vectors, such as LLL 43 (polynomial time, but exponentially bad approximation), or BKZ [22]. The shortest vector problem and its approximate variants are the hard mathematical problems that serve as the core of lattice-based cryptography.
2.2 LWE
The Learning With Errors (LWF) problem, introduced in 56 parameterized by a dimension n, the number of samples m. a modulus g and an error distribution x (e.g., the discrete Gaussian distribution) over Z,, = {0, I,.... q- 1}. Regev showed that LWE is at least as hard as quantumly solving certain hard lattice problems. Later [53] 46 [4] showed LWE to be classically as hard standard worst-case lattice problems, therefore establishing a solid foundation for building cryptographic schemes on it.
LWE and RLWE. The LWE distribution As,x consists of pairs b) E Zm x Zn where A is uniformly random matrix in Z,nxxn b = As + mod g, where s E Z is the secret vector sampled uniformly at random and e E Z is the error vector sampled from the error distribution X- We call the pair (A, b) an LWE sample, yielding n LWE instances: one row of A together with the corresponding entry in b is one LWE insiance. There is also a ring version of LWE, known as the Ring Learning with Errors (RLWE) problem (described further in Appendix A.1).
Search-LWE and LeE. We now state the LWE hard problems. The search-LWa problem is to find the secret vector s given (A. b) from As.y The decision-LWE problem is to distinguish As from the uniform distribution {(A, b) E 2 x x 27: A and b are chosen uniformly at random)]. (56) provided a reduction from search-LWW to decision-L.WF, We give a detailed proof of this reduction in Appendix AA.2 for the case when the secret vector is binary (i.e. entries are O and 1). In Section 4.3 our Distinguisher Secret Recovery method is built on this reduction proof.
(Sparse) Binary secrets. In LWE based schemes, the secret key vector can be sampled from various distributions. For efficiency reasons, binary distributions (sampling in (0.1) 1)²) and ternary distributions (sampling (-1, 0, 1)") are commonly used, especially homomorphic encryption 4. In fact, many implementations use sparse secret with Hamming weight h (the number of I's

---

Loss
Accuracy (%)
14
100
Table I: Size of the training sets required for learn- ing modular inversion. Basc-2 logarithm of the num- ber of examples needed reach 95% accuracy, for different values [10g2(4) and bases. '." means 95% accuracy not attained after 90 million examples.
60
21
401
20
[(R
2
Base
24
27
30
81
128
15
23
21
23
22
20
23
22
20
20
16
Epochs
Epochs
17
23
25
22
23
24
22
22
22
18
22
Figure 2: Learning modular multiplication for var- ious moduli q- Test loss and accuracy for q with [loga(2) from 15 to 21. 300,000 training examples per epoch. One layer transformers with 512 dimen- sions, 8 attention heads, integers encoded in base 81.
19
23
25
25
24
25
24
20
24
21
24
22
23
in the binary secret). For instance, HEAAN weight 64 23 For more on the use of sparse binary secrets in LWE, see 6 25].
215
2628 =2268 ternary secret and Hamming
3 Modular Arithmetic with Transformers
Two key factors make breaking LWE difficult: the presence of error and the use of modular arithmetic. Machine learning (MI.) models tend to robust to noise in their training data. the absence of modulus, recovering s from observations of and easy task for ML. Once a modulus is introduced, attacking LWE requires performing linear regression on an n-dimensional torus, much harder problem.
+ merely requires linear regression, an
Modular arithmetic therefore appears to be significant challenge for an ML-based attack on LWE. Previous research has concluded that modular arithmetic is difficult for ML models [52], and that transformers struggle with basic arithmetic [5T]. However, [17] showed that transformers can compute matrix-vector products, the basic operation in LWE, with high accuracy. As a first step towards attacking LWE, we investigate whether these results can be extended to the modular case.
We begin with the one-dimensional case, training models to predict b = as mod q from for some fixed unknown value of s when as Zg. This is a form of modular inversion since the model must implicitly learn the secret in order to predict the correct output b. We then investigate the n-dimensional case, with ž and either in 2n or in {0, 13" (binary secret). In the binary case,
this becomes (modular) subset sum problem.
3.1 Methods
Data Generation. We generate training data by fixing the modulus q (a prime with 15 S [logz (4) < 30, see the Appendix B), the dimension n, and the secret E L (or {0, 1)" in the binary case). We then sample a uniformly in ž and compute b = a mod g, to create data pair (a, b).
Encoding, Integers are encoded base B (usually, B=81), as a sequence of digits in {0, ... 1}. For instance, (a, b) = (16. 3) is represented as the sequences [1, 0, 0, 0, 0] and [1, 1] in base 2, or [2,2] and [3] in base 7. the multi-dimensiona. case, special token separates the coordinates.
Model Training. The model is trained to predict b from a, for an unknown but fixed value of We use sequence -o-eeueeee transformers [67] with one layer in the encoder and decoder, 512 dimensions and attention heads. We minimize a cross-entropy loss, and use the Adam optimizer [39 with learning of 5 10-5, At epoch end (300000 examples), model accuracy is evaluated over a test set of 10000 examples. We train until test accuracy 95% or loss plateaus for 60 epochs.
3.2 Results
One-Dimensional. For a fixed secret s. modular multiplication is function from Z, into itself, that can be learned by memorizing y values. Our models learn modular multiplication with high accuracy for values of y such that [log{(g] < 22. Figure 2 presents learning curves for different values of log2(g). The loss and accuracy curves have a characteristic step shape, observed in many of our experiments, which suggests that "casier cases" (small values of (as/g]) are learned first.
3

---

The speed of learning and the training set size needed to reach high accuracy depend on the problem difficulty, i.c. the value of q. Table presents the [log of the number of examples needed reach 95% accuracy for different values of [log2(g) (g)] and base B. Since transformers learn from scratch, without prior knowledge of numbers and moduli, this procedure is not data-efficient. The number of examples needed to learn modular multiplication is between 10g and 50g. Yet, these experiments prove that transformers can solve the modular inversion problem in prime fields.
Table illustrates an interesting point: learning difficulty depends on the base used to represent integers. For instance, base and allow the model to learn up to [log[()]] 17 and 18, whereas base 3 and 7 can reach [9) 21. Larger bases, especially powers of small primes, enable faster learning. The relation between representation base and learning difficulty is difficult to explain from a number theoretic standpoint. Additional experiments are in Appendix B
Multidimensional integer secrets. In the n-dimensional case, the model must learn the modular dot product between vectors a and s in Z,,. The proves to be a much harder problem. For n = 2, with the same settings, small values of q (251, 367 and 967) can be learned with over 90% accuracy, and = 1471 with 30%. In larger dimension, all models fail to learn. Increasing model depth to 2 or 4 layers, or dimension 1024 or 2048 and attention heads 12 and 16, improves data efficiency (less training samples are needed), but does not scale to larger values of or > 2.
Multidimensional binary secrets. Binary secrets make n-dimensional problems easier to learn. For n = 4, our models solve problems with [log2(g)] S 29 with more than 99.5% accuracy. For n = 6 and 8, we solve cases [log2(4) (q) S 22 with more than 85% accuracy. But we did not achieve high accuracy for larger values of n. So in the next section, we introduce techniques for recovering secrets from a partially trained transformer. We then show that these additional techniques allow recovery of sparse binary secrets for LWE instances with 30 < S 128 (so far).
4 Introducing SALSA: LWE Cryptanalysis with Transformers
Having established that transformers can perform integer modular arithmetic, we leverage this result to propose SALSA, method for Secret-recovery Attacks on LWE via Seq2Seq models with Attention.
4.1 SALSA Ingredients
SALSA has three modules: a transformer model M, a secret recovery algorithm, and secret verification procedure. We assume that SALSA has access a number of LWE instances in dimension n that use the same secret, i.e. pairs (a, b) such that b = a S + mod g, with e an error from a centered distribution with small standard deviation. SALSA runs in three steps. First, it uses LWE data to train M to predict b given a. Next SALSA runs a secret recovery algorithm. It feeds M special values of a, and uses the output b = MM(a) to predict the secret. Finally, SALSA evaluates the guesses $ by verifying that residuals r b a mod g computed from LWE samples have small standard deviation. If so, s has been recovered and SALSA stops. If not, SALSA returns to step and iterates.
4.2 Model Training
SALSA uses LWE instances to train model that predicts b from by minimizing the cross-entropy between the model prediction b' and The model architecture is a universal transformer [27), in which shared transformer layer is iterated several times (the output from one iteration is the input to the next). Our base model has two encoder layers, with 1024 dimensions and 32 attention heads, the second layer iterated 2 times, and two decoder layers with 512 dimensions and 8 heads, the second layer iterated times. To limit computation in the shared layer, we use the copy-gate mechanism from (24) Models are trained using the Adam optimizer with lr 10 and 8000 warmup steps.
For inference, we use beam search with depth 1 (greedy decoding) 40 65 epoch, we compute model accuracy over test set of LWE samples. Because of the error added when computing i = a s + e, exact prediction of is not possible. Therefore, we calculate accuracy within tolerance T (acez): the proportion of predictions = M(a) that fall within Tq of b, i.e. such that ||6 b| < rg. In practice we set T = 0.1.
At the end of each
4.3 Secret Recovery
We propose two algorithms for recovering s: direct recovery from special values of a, and distin- guisher recovery using the binary search to decision reduction (Appendix A.2). For theoretical justification of these, see Appendix C

---

Direct Secret Recovery. The first technique, based on the LWE search problem, is analogous to chosen plaintext attack.For each E N,, a guess of the i-th coordinate is made by feeding model M the special value a; Ke; (all coordinates except the i-th), with a large integer. If
Algorithm 1 Direct Secret Recovery
8 = 0, and the model MM correctly approxi-
1: Input: M, Kn
mates b,- = a; 0 S + e from aj, then we expect
2: Output: secret 8
= .M(a) to be a small integer; likewise if
3: p= 0"
8, 1 we expect large integer. This technique
4: for i = 1.... 12 do
is formalized in Algorithm ! The binarize
5:
a 0%: a, = K
function in line 7 is explained in Appendix C In SALSA, we run direct recovery with 10 differ- ent K values in order to yield 10 guesses.
6: Pt = M(a)
7: 8 binarize(p)
8: Return:
Distinguisher Secret Recovery. The second algorithm for secret recovery is based on the decision- LWE problem. It uses the output of M to determine if LWE data (a, b) can be distinguished from secret recovery is shown in Algorithm 2 At a high level, the algorithm works as follows. Suppose we have LWE instances (a, b) and random instances (a,. b,)) For each secret coordinate 82, we transform the a into a' = ag c, with 2g random integers. We then model M to compute M(a') and M(aa). If the model has learned and the tt bit of is O, then MMa') should be significantly closer to b than M(a,) is to by. Iterating on allows us to recover the secret bit by bit. SALSA runs the distinguisher recovery algorithm when model =cC,=0.1 is above 30%. This is the theoretical limit for this approach to work.
randomly generated pairs (ar, br). The algorithm for distinguisher-basee
4.4 Secret Verification.
Algorithm 2 Distinguisher Secret Recovery
At the end of the recovery step, we have 10 or 11 guesses 5 (depending on whether the distin- guisher recovery algorithm was run). To verify
1: Input: M,, n. aCCr,
2: Output: secret
3: = O"
them, we compute the residuals r a mod q for a set of LWE samples (a, b). If correctly guessed, we have = s, so a 8 b = mod q will be distributed as the error e with small standard deviation a. If & * s. r will be (approximately) uniformly distributed over En (because a and are uni- formly distributed over E.), and will have stan-
4: advantage, bound acc, 2- TT T,
5: = min{50, 50, adwantage"
6: ALWE, BLWE LW ESamples(t, n,
7: for = 1.... do
1 9: Bunif ~ (4 1)e
8: Aunit (1,
10:
c~ 2021 -}
11:
A ALWE ALWE
(r) g/ e/V(11 (12). Therefore, we can verify if š is correct by calculating the stan- dard deviation of the residuals: it is close to a, the standard deviation of error, the secret was recovered. In this paper, a 3 and 9 = 251, so the standard deviation of r will be around 3 if s s, and 72.5 if not.
dard deviation
12:
A ALWE | = (AtwEla +c)) mod g
13:
BLWE -M(A(.R)
14:
Bunif = MMM
15:
dl = BLWE - BLWE
16:
du = |Bunif - B Bunif
17:
CLWE # dl, < bound. j E N,,
5 SALSA Evaluation
18:
Camif #(j du, < bound, j E N₂)
19:
if (CLWE Cunis) S advantage -t2 then
In this section, we present our experiments with SALSA. We generate datasets for LWE prob-
20:
8; =1
lems of different sizes, defined by the dimension 21:
Return:
and the density of ones in the binary secret. We use gated universal transformers, with two layers in the encoder and decoder. Default dimensions and attention heads in the encoder and decoder are 1024/512 and 16/4, but we vary them as we scale the problems. Models are trained on two NVIDIA Volta 32GB GPUs
internal cluster.
5.1 Data generation
We generate LWE data for SALSA training/evaluation is randomly given the following parameters: dimension n. secret density d, modulus q, encoding base B, binary secret s, and error distribution x- For all experiments, we use q = 251 and B = 81 (see I3.1), fix the error distribution X as a discrete Gaussian with μ 0, 3 (4. and generate random
We vary the problem size (the LWE dimension) and the density d (the proportion of ones in the secret) to test attack success and to observe how it scales. For problem size, we experiment with
5

---

Test Loss
Table 2:
Full secret recovery. Highest density values at which the secret was recovered for each n. q 251. For n 100, the model has 1024/512 embedding. 16/4 attention heads. For n 2 100, the model has 1536/512 12 embedding. 32/4 attention heads. For com- parison, we include the logz number of possible se- crets each v/d level.
5.25
5.00
dimeniion 50
4.50
128
Test Accuracy
Acqurncy (9)
Dim. n
Density d'
loga samples
loga secrets
Runtime (hours)
0.1
21.9
12.0
1.2
30
0.13
24.8
14.7
21
0.06
22.4
14.3
5.5
50
0.08
25.6
17.8
18.5
Training Epoch
70
0.04
22.5
15.7
4.5
Full secret recovery: Curves for loss and acc, 0.1, for varying n with Hamming weight 3. For n < 100, model has 1024/512 embedding, 16/4
Figure 3:
90
0.03
24.1
16.8
35.0
110
0.03
21.5
17.7
32.0
attention heads. For n 2 100, model has 1536/512 embedding, 32/4 attention heads.
128
0.02
22.3
18.4
23.0
30 to π 128. For density, we experiment with 0.002 < d 0.15. For given select d so that the Hamming weight of the binary secret (h = dn), is larger than 2. Appendix D.2 contains an ablation study of data parameters. We generate data using the RLWE variant of LWE, described in Appendix [A] For RLWE problems, each a is a line a circulant matrix generated from an initial vector E Zy. RLWE problems exhibit more structure than LWE due the use of the circulant matrix, which may help our models learn.
5.2 Results
Table presents problem sizes n and densities for which secrets can be fully recovered, together with the time and the logarithm of number of training samples needed. SALSA can recover binary secrets with Hamming weight 3 for dimensions up to 128. Hamming weight 4 secrets can be recovered for n < 70. For context, we include column "logz secrets" listing the number of possible secrets for the corresponding Hamming weight. Exhaustive search for the secret may run faster than our current experiments for low Hamming weight. However, an exhaustive search requires knowing the exact hamming weight in advance, or iterating through all possible Hamming weights. Although we have only succeeded unconditionally with low Hamming weight so far, SALSA does not a priori know the secret Hamming weight h. It remains to be seen how SALSA will scale to larger and h.
Interestingly, the number of samples required for SALSA to succeed for fixed Hamming weight is relatively flat as the dimension n increases. However the time needed to recover the secret for fixed Hamming weight increases with n. partly because the length of the input sequence fed into the model is proportional to n even though the number of samples needed remains stable as n grows. This is an important result, because all the data used for training the model must be collected (e.g. via eavesdropping), making sample size an important metric.
For given n, scaling to higher densities requires more time and data, and could not be achieved with the architecture we use for n >> 50. As grows, larger models are needed: our standard architecture, with 1024/512 dimensions and 16/4 attention heads (encoder/decoder) was sufficient for < 90. For n. > 90, we needed 1 1536/512 512 dimensions and 32/4 attention heads.
Figure 3 illustrates model behavior during training. After an initial burn-in period, the loss curve (top graph) platcaus until the model begins learning the secret. Once loss starts decreasing, model accuracy with 0.1g tolerance (bottom graph) increases sharply. Full secret recovery (vertical lines in the bottom graph) happens shortly after, often within one or two epochs. Direct secret recovery accounts for 55% of recoveries, while the distinguisher only accounts for 18% of recoveries (see Appendix C.3). 27% of the time, both methods succeed simultancously.
One key conclusion from these experiments is that the secret recovery algorithms enable secret recovery long before the transformer has been trained to high accuracy (even before training loss settles a low level). Frequently, the model only needs to begin to learn for the attack succeed.

---

Table 3: Architecture Experiments We test the effect of model layers, loops, gating, and encoder dimension and report the loga samples required for secret recovery (n 50, Hamming weight 3).
Regular vs, UTs (1024/512, 16/4, 8/8)
Ungated vs, Gated (1024/512, 16/4, 8/8)
UT Loops
Encoder Dim. (X/512, 16/4, 2/8)
Decoder Dim.
(1024/512,
16/4, X/X)
(1024/X. 16/4, 2/8)
Regular
UT
Ungated
Gated
2/8
4/4
8/2
512
2048
3040
256
768
1024
1536
26.3
22.5
26.5
22.6
23.5
26.1
23.2
23.3
20.1
19.7
22.5
21.8
23,9
24.3
5.3
Experiments with model architecture
SALSA's base model architecture is a Universal Transformer (UT) with copy-gate mechanism. Table 3 demonstrates the importance of these choices. For problem dimension n = 50, replacing the UT by regular transformer with 8 encoder/decoder layers, or removing the copy-gate mechanism increases the data requirement by factor of 14. Reducing the number of iterations in the shared layers from 8 to 4 has a similar effect. Reducing the number of iterations in either the encoder or decoder (i.e. from 8/8 to 8/2 or 2/8) may further speed up training. Asymmetric transformers (e.g. large encoder and small decoder) have proved efficient for other math problems, e.g. (37), 17 and asymmetry helps SALSA as well. Table[]Jdemonstrate
that increasing the encoder dimension from 1024 to 3040, while keeping the decoder dimension at 512, results in a 7-fold reduction in sample size. Additional architecture experiments are presented in Appendix D.I
5.4 Increasing dimension and density
To attack real-world LWE problems, SALSA must handle larger dimension n and density d. Our experiments with architecture suggest that increasing model size, and especially encoder dimension, is the key factor to scaling Empirical observations indicate that scaling d is much harder problem. We hypothesize that this is due to the subset sum modular addition at the core of L.WE with binary secrets. For secret with Hamming weight h, the base operation integers, followed by a modulus. For small values of ht the modulus operation is not always necessary, the sum might not exceed q. As density increases, so does the number of times the sum "wraps around" the modulus, perhaps making larger Hamming weights more difficult to learn. To test this hypothesis, we limited the range of the coordinates in a, so that a, < r, with r aq and 0.3 < a < 0.7. For n = 50, we recovered secrets with density up to 0.3, compared to 0.08 with the full range of coordinates (see Table 4). Density larger than 0.3 is no longer considered sparse secret.
+ mod is sum of
5.5 Increasing error size
Table 5: loga samples needed for seeret recovery
when o = [vnj. Results averaged over 6 SALSA runs each n/o level.
Theoretically for lattice problems to be hard, a
should scale with vn, although this is often ig- nored in practice, e.g. [4). Consequently, we run most SALSA experiments with = 3, com- mon choice in existing RLWE- based systems. Here, investigate how SALSA performs as a increases. First, to match the theory, we run experiments where o = Lvn. h = 3 and found that SALSA recovers secrets even as scales with (see Table same model architecture Second, we evaluate SALSA's performance for fixed n/h values as a increases. We fix n = 50 and h and evaluate for a values up number of samples required for recovery linearly increases (see Figure in Appendix). For both sets of experiments, we reuse samples up to 10 times.
n/o
30/5
50/7
70/8
90/9
logSamples 18.0
18.5
19.3
19.6
Table 2
24. Secret recovery succeeds for all tests, although the
6 SALSA in the Wild
Problem Size. Currently, SALSA can recover secrets from LWE samples with n up to 128 and density d 0.02. can recover higher density secrets for smaller n (d 0.08 when n 50). As mentioned in Section sparse binary secrets are used in real world LWE homomorphic encryption, and attacking these implementations a future goal for SALSA. Admittedly, SALSS must scale to attack larger n before it can break full-strength homomorphic encryption implementations. However, other parameters of full-strength homomorphic encryption such as secret density (the secret vector in HEAAN has d 0.002) and error size recommends 3.2) are within SALSA's reach.
7

---

Table 4: Secret recovery when value is bounded. Results shown are fraction of the secret recovered by SALSA for 50 with varying when values are S p Q. Green means that was fully recovered. Yellow means all of the bits were recovered, but not all 0 bits. Red means SALSA failed. For completeness, we also note the logz number of possible secrets at each d level.
log2 secrets
Max a value as fraction of
d
0.35
0.4
0.45
0.5
0.55
0.6
0.65
0.16
29.0
1.0
1.0
1.0
1.0
1.0
1.0
0.88
0.18
31.2
1.0
1.0
1.0
1.0
0.82
0.86
0.84
0.20
33.3
1.0
1.0
1.0
1.0
1.0
0.82
0.82
0.22
35.1
0.98
1.0
1.0
0.98
0.80
0.78
0.86
0.24
36.8
1.0
1.0
1.0
0.98
0.78
0.78
0.80
0.26
38.4
1.0
0.88
0.92
0.76
0.76
0.76
0.28
39.8
0.98
1.0
0.80
0.74
0.74
0.76
0.74
0.30
41.0
0.98
1.0
0.93
0.76
0.72
0.74
0.74
Ratio of samples needed for secret recovery (with reuse) to samples needed for secret recovery (no reuse)
Expected Observed
0.15
Ratio
0.1
0.05
5
10
15
20
25
of times samples are reused
Figure 4: Reusing LWE samples yields a significant decrease in the number of samples needed for secret recovery. Shown here is the ratio of samples required for secret recovery with reuse to the samples required for secret recovery without reuse, both expected (top curve) and observed (bottom curve, better than expected).
Other LWE-bbsed schemes secret dimensions that seem achievable given current results. For example, in the -.see public key encryption scheme Crystal-Kybed [9], the secret dimension is k 256 for f {2, 3, 4), approachable range for SALSA based initial results. The LWe-based signature scheme Crystal-Dilithe sparse binary secrets, and adapting SALSA nonbinary secrets an avenue for future work.
has similar n sizes [29]. However, these schemes don't 't use
Sample Efficiency. A key requirement of real-world LWE attacks is sample efficiency. practice, an attacker will only have access small set of LWE instances (a, b) for given secret For instance, in Crystal-
there are only (k + 1)n LWE instances available with = 2, 3 or 4 and 256. The experiments in (20 I1I use less than 500 LWE instances. The TU Darmstadt challenge provides n² LWE instances to attackers.
The log, samples column of Table lists the number of LWE instances needed for model training. This number is much larger than what likely available in practice, so it important reduce sample requirements. Classical algebraic attacks on LWE require LWE instances to be linearly independent, but SALSA does not have this limitation. Thus, we can reduce SALSA's sample use several ways. First, we can reuse samples during training. fewer samples. Second, we can use integer linear combinations of given LWE samples to make new samples which have the same secret but larger eπror Appendix E contains the formula for the number of new samples we can generate with this method (up to 22 new samples from 100 samples).
that this allows secret recovery with
Comparison to Baselines. Most existing attacks on LWE such uSVP and dual attack use an algebraic approach that involves building lattice from LWE instances such that this lattice contains an exceptionally short vector which encodes the secret vector information. Attacking LWE then involves finding the short vector via lattice reduction algorithms like BKZ (22). For LWE with sparse binary secrets, the main focus of this paper, various techniques can be adapted to make algebraic attacks more efficient. 20 and 23 provide helpful overviews of algebraic attacks on sparse
binary secrets. More information about attacks on LWE is in Appendix A.3

---

Compared to existing attacks, SALSA's most notable feature is its novelty. We do not claim that to have better runtime, neither do we claim the ability to attack real-world LWE problems (yet). Rather, we introduce a new attack and demonstrate with non-toy successes that transformers can be used to attack LWE. Given our goal, no serious SALSA speedup attempts have been made so far, but a few simple improvements could reduce runtime. First, the slowest step in SALSA is model training, which can be greatly accelerated by distributing it across many GPUs. Second, our transformers are trained from scratch, so pre-training them on such basic tasks as modular arithmetic could save time and data. Finally, the amount of training needed before the secret is recovered depends in large part on the secret guessing algorithms. New algorithms might allow SALSA to recover secrets faster.
Since SALSA does not involve finding the shortest vector in a lattice. it has an advantage over the algebraic attacks - with all LWE parameters fixed and in the range of SALSA, SALSA can attack the LWE problem for a smaller modulus q compared to the algehraic attacks. This because the target vector is relatively large in the lattice when is smaller and is harder to find. For instance, in [20]. their Table 2 shows that when the block size is 45, for n = 90, their attack does not work for q less than 10 bits, but we can handle q as small as 8 bits (Table 20).
7 Related Work
Use of ML for cryptanalysis. The fields of cryptanalysis and machine learning are closely re- lated [57]. Both seek to approximate an unknown function F using data, although the context and techniques for doing so vary significantly between the fields. Because of the similarity between the domains, numerous proposals have tried to leverage ML for cryptanalysis. MI- based attacks have been proposed against number of cryptographic schemes, including block ciphers [3] 63 [8 TO 30 12 21), hash functions [3T], and substitution ciphers (4,44 [ Although
our work is the first to recurrent neural networks for lattice cryptanalysis, prior work has used them for other cryptographic tasks. For example, (32) showed that LSTMs can learn the decryption function for polyalphabetic ciphers like Enigma. Follow-up works used variants of LSTMs, including transformers, to successfully attack other substitution ciphers
1 64 g
Use of transformers for mathematics. The use of language models to solve problems of mathematics has received much attention in recent years. A first line of research explores math problems set up in natural language. [59] investigated their relative difficulty, using LSTM [44] and transformers, while
33 showed large transformers could achieve high accuracy on elementary/high school problems. A second line explores various applications of transformers on formalized symbolic problems. [42] accuracy with transformers. [68] discussed their limits when generalizing out of their training distribution. Transformers have been applied to dynamical systems [18], transport graphs [19], theorem proving [54]. SAT solving [61]. and symbolic regression 13 26]. A third line of research focuses arithmetic/numerical computations and has had slower progress. [52] and (51] discussed the difficulty of performing arithmetic operations with language models. Bespoke network architectures have been proposed for arithmetic operations [35 66), and transformers were used for addition and similar operations
showed that symbolic math problem could be solved to state-of-
[55] 17) showed that transformers can learn numerical computations, such as linear algebra, and introduced the shallow models with shared layers used in this paper.
Shamir and Shammah [60] showed that some problems of modular arithmetic cannot be solved by gradient descent. Because it uses transformer to learn the secret, by predicting b from a, SALSA's scalability hinges on the solvability of LWE by gradient descent. Here, we provide our perspective on this question.
Learnability of LWE. Shalev-
The LWE problem amounts to (discrete) linear regression on an rn-dimensional torus with radius g. When q is infinite, LWE is pure lincar regression, and gradient methods will succeed. For finite q, gradients are informative unless the model's s prediction lies on the opposite side of the torus from the true solution (e.g. = 100, true value is O, prediction is 50). At this point, the projection of the gradient along the coordinate axis is uninformative, since either direction on the torus points towards the true solution. For large q, this situation is uncommon, gradient methods should work. For very small q. this will happen more often, and gradient methods will be perturbed. In the degenerate case
q = 2, featured in (60), gradient methods will always fail.
For the value y = 251 used SALSA, gradient methods can recover secrets (i.e. solve the modular linear regression problem) for up 128 so far. Except for the case of very small q, it is unlikely

---

that LWE belongs to the "failing gradient" class of problems described in [60]] Any learnability problems should disappear altogether as q increases.
Interestingly, this intuition about the size of also appears in the classical lattice reduction approach to solving LWE. Laine and Lauter [41] LLL demonstrate concrete polynomial-time attacks against lattice problems for large They also explore the boundary of where these attacks start to fail for smaller q. The intuition is that when q is large, LLL directly finds vector which is "small enough" compared to to break the system. When q is small, LLL does not find short enough [20]. which gives concrete running times for generalizations of LLL and quantifies the size of q where these attacks start to fail.
vector. This is further explored
Conclusion
Discussion. In this paper, we demonstrate that transformers can be trained to perform modular arithmetic. Building this capability, design SALSA, method for attacking the LWE problem with binary secrets, hardness assumption at the foundation of many nattice-based cryptosystems. We show that SALSA break LWE problems of medium dimension (up to n 128), which is in the same range as problems in the Darmstadt challenge [[5], although we restrict to the easier case of sparse binary secrets. This is the first paper to transformers to solve hard problems in lattice-based cryptography. Future work will attempt to scale up SALSA to attack higher dimensional lattices with more general secret distributions.
The key to scaling up to larger lattice dimensions seems to be to increase the model size, especially the dimensions, the number of attention heads, and possibly the depth. Large architectures should scale to higher dimensional lattices such as n = 256 which is used in practice. Density, on the other hand, is constrained by the performance of transformers of finite fields could improve transformer performance on these tasks. Finally, our secret guessing algorithms enable SALSA to recover secrets from low-accuracy transformers, therefore reducing the data and time needed for the attack. Extending these algorithms to take advantage of partial learning should result in better performance.
modular arithmetic. Better representations
Ethics and Broader Impact. The primary value of this work is in alerting the cryptographic and ML communities to the risk of ML-based attacks on PQC. Even current attacks do not succeed, believe that providing early warning of potential threats is critical. However, emphasize that SALSA represents proof of concept that cannot be used against real-world implementations (i.e. the PQC schemes which NIST standardized on July 5, 2022). Additional scaling work would be necessary before these techniques would be relevant to attacking real-world cryptosystems.
10

---

References
[1] Ezat Ahmadzadeh, Hyunil Kim, Ongee Jeong, and Inkyu Moon. Novel Dynamic Attack on Classical Ciphers Using Attention-Bann Based LSTM Encoder- Model. IEEE Access, 2021.
[2] Miklós Ajtai. Generating hard instances of lattice problems. In Proc. the 28th annual ACM symposium on Theory of Computing, 1996.
[3] Mohammed M Alani. Neuro-cryptanalysis of DES and triple-DES. In Proc. of NeurIPS, 2012.
[4] Martin Albrecht, Melissa Chase, Hao Chen, Jintai Ding, Shafi Goldwasser, Sergey Gorbunov, Shai Halevi, Jeffrey Hoffstein, Kim Laine, Kristin Lauter, et al. Homomorphic encryption standard. In Protecting Privacy through Homomorphic Encryption, pages 31 31-62. Springer, 2021.
[5] Martin Albrecht, Carlos Cid, Jean-Charles Faugère, Robert Fitzpatrick, and Ludovic Perret. On the complexity of the BKW algorithm on LWE. Designs, Codes and Cryptography, 2015.
[6] Martin Albrecht. On dual lattice attacks against small-secret Iwe and parameter choices in helib and seal. In EUROCRYPT, 2017.
[7] Martin R. Albrecht, Jean-Charles Faugère, Robert Fitzpatrick, and Ludovic Perret. Lazy Modulus Switching for the BKW Algorithm on LWE. In Public-Key Cryptography, 2014.
[8] Nada Aldarrab and Jonathan May. Can sesquence-t--sqqueee models crack substitution ciphers? arXiv preprint
15229, 2020.
[9] Roberto Avanzi, Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Peter Schwabe, Gregor Seiler, and Damien Stehlé. CRYSTALS- Kyyeerr (version 3.02) Submission to round 3 of the NIST post-quantum project. 2021.
[10] Seunggeun Baek and Kwangjo Kim. Recent advances of neural attacks against block eiphers. In Proc. of SCIS, 2020.
[11] Shi Bai and Steven D. Galbraith. Lattice Decoding Attacks on Binary LWE. In Information Security and Privacy, 2014.
[12] Adrien Benamira, David Gerault, Thomas Peyrin, and Quan Quan Tan. A deeper look machine learning-based cryptanalysis. In Proc. of Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2021.
[13] Luca Biggio, Tommaso Bendinelli, Alexander Neitz, Aurelien Lucchi, and Giambattita Paras- candolo. Neural symbolic regression that scales. arXiv preprint 1.Xiv:2106.06422 2021.
[14] Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev, and Damien Stehlé. Classical Hardness of Learning with Errors. In Proc. of the Forty-Fifth Annual ACM Symposium on Theory of Computing, 2013.
[15] Johannes Buchmann, Niklas Büscher, Florian Göpfert, Stefan Katzenbeisser, Juliane Krämer, Daniele Micciancio, Sander Siim, Christine van Vredendaal, and Michael Walter. Creating Cryptographic Challenges Using Multi- -arty Computation: The LWE Challenge. In Proc. of the 3rd ACM International Workshop on ASIA Public-Key Cryptography. 2016.
[16] Johannes A. Buchmann, Florian Göpfert, Rachel Player, and Thomas Wunderer. On the Hardness of LWE with Binary Error: Revisiting the Hybrid Lattice-Reduction and Meet-in-the- Middle Attack. In Proc. of AFRICACRYPT, 2016.
[17] François Charton. Linear algebra with transformers. arXiv preprint arXiv:2112.0188: 2021.
[18] François Charton, Amaury Hayat, and Guillaume Lample. Learning advanced mathematical computations from examples. arXiv preprint arXiv:2006.06466 2020.
[19] François Charton, Amaury Hayat, Sean T. McQuade, Nathaniel J. Merrill, and Benedetto Piccoli. A deep language model to predict metabolic network equilibria. arXiv preprint arXiv:21 12.03588, 2021.

---

[20] Hao Chen, Lynn Chua, Kristin E. Lauter, and Yongsoo Song. On the Concrete Security of LWE with Small Secret. IACR Cryptol. ePrint Arch., 2020:539, 2020.
[21] Yi Chen and Hongbo Yu. Bridging Machine Learning and Cryptanalysis via EDLCT. Cryptology ePrint Archive, 2021.
[22] Yuanmi Chen and Phong Q. Nguyen. BKZ 2.0: Better Lattice Security Estimates, In Proc. of ASIACRYPT 2011, 2011.
[23] Jung Hee Cheon, Minki Hhan, Seungwan Hong, and Yongha Son. A Hybrid of Dual and Meidiil Attack on Sparse and Ternary Secret LWE. IEEE Access, 2019.
[24] Róbert Csordás, Kazuki Irie, and Jürgen Schmidhuber. The Neural Data Router: Adap- tive Control Flow in Transformers Improves Systematic Generalization. arXiv preprint urXiv:2100007333 2021.
[25] Benjamin R. Curtis and Rachel Player. On the feasibility and impact of standardising sparse- secret LWE parameter sets for homomorphic encryption. In Proc. of the 7th ACM Workshop on Encrypted Computing & Applied Homomorphic Cryptography, 2019.
[26] Stéphane d' Ascoli, Alexe-Ale Kamienny, Guillaume Lample, and François Charton. Deep symbolic regression for recurrent sequences. arXiv preprint wtt.:2201.046000 2022.
[27] Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. Uni- versal transformers. arXiv preprint arXiv:1807 10t.:18877.0899 2018.
[28] Whitfield Diffie and Martin Hellman. New directions in cryptography. IEEE transactions on Information Theory, 1976.
[29] Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler, and Damien Stehlé. CRYSTALS-Dilthhe - Algorithm Specifications and Supporting Docu- mentation (Version 3.1). 2021.
[30] Aron Gohr. Improving attacks on round-reduced speck32/64 using deep learning. In Proc. of Annual International Cryptology Conference, 2019.
[31] Sergij V Goncharov. Using fuzzy bits and neural networks to partially invert few rounds of some cryptographic hash functions. arXiv preprint 1XXv:1901..02438. 2019.
[32] Sam Greydanus. Learning the enigma with recurrent neural networks. arXiv preprint 1XXi:11008.07576 2017.
[33] Kaden Griffith and Jugal Kalita. Solving Arithmetic Word Problems with Transformers and Preprocessing of Problem Text. arXiv preprint arXiv:2106.00892 2021.
[34] Sepp Hochreiter and Jürgen Schmidhuber: Long short-term memory. Neural Computation, 1997.
[35] Lukasz Kaiser and Ilya Sutskever. Neural GPUs learn algorithms. 1XXiv:1511.08228 2015.
arXiv preprint
[36] Ravi Kannan. Minkowski's Convex Body Theorem and Integer Programming. Mathematics of Operations Research, 12(3):415444, 1987.
[37] Jungo Kasai, Nikolaos Pappas, Hao Peng, James Cross, and Noah A. Smith. Deep Encoder, Shallow Decoder: Reevaluating the Speed-Quality Tradeoff in Machine Translation. arXiv preprint arXiv:2006.10369) 2020.
[38] Hayato Kimura, Keita Emura, Takanori Isobe, Ryoma Ito, Kazuto Ogawa, and Toshihiro Ohigashi. Output Prediction Attacks on SPN Block Ciphers using Deep Learning. TACR Cryptol. ePrint Arch,, 2021.
[39] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint MrXiv:1412.69800 2014.
12

---

[40] Philipp Koehn. Pharaoh: beam search decoder for phrase- based statistical machine translation models. In Conference of the Association for Machine Translation in the Americas. Springer, 2004.
[41] Kim Laine and Kristin Lauter. Key recovery for Iwe in polynomial time. Cryptology ePrint Archive, 2015.
[42] Guillaume Lample and François Charton. Deep learning for symbolic mathematics. arXiv preprint arXiv:1912.01411 2019.
[43] H.W. jr. Lenstra, A.K. Lenstra, and L. Lovász. Factoring polynomials with rational coefficients. Mathematische Annalen, 261:515-534, 1982.
[44] Richard Lindner and Chris Peikert. Better Key Sizes (and Attacks) for LWE-Based Encryption. In Topics in Cryptology - CT-RSA 2011, 2011.
[45] Mingjie Liu and Phong Q Nguyen. Solving BDD by Enumeration: An Update. In Ed Dawson editor, Topics in Cryptology CT-RSA 2013, 2013.
[46] Vadim Lyubashevsky and Daniele Micciancio. On Bounded Distance Decoding, Unique Shortest Vectors, and the Minimum Distance Problem. In Advances Cryptology. 2009.
[47] Daniele Micciancio. On the Hardness of Learning With Errors with Binary Secrets. Theory of Computing, 2018.
[48] Daniele Micciancio and Oded Regev. Lattice-based crypoggrphhy Post-Quantum Cryptography, pages 147-191, 2009.
[49] Daniele Micciancio and Panagiotis Voulgaris. Faster exponential time algorithms for the shortest vector problem. Proc. of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2010.
[50] Victor S Miller. Use of elliptic curves in cryptography. In Conference the Theory and Application of Cryptographic Techniques. Springer, 1985.
[51] Rodrigo Nogueira, Zhiying Jiang, and Jimmy Lin. Investigating the limitations of transformers with simple arithmetic tasks. arXiv preprint arXiv:2 102.019,, 2021.
[52] Theodoros Palamas. Investigating the ability of neural networks to learn simple modular arithmetic. 2017.
[53) Chris Peikert. Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem: Ex- tended Abstract. In Proc. of the Forty-Fint First Annual ACM Symposium on Theory of Computing. 2009.
[54] Stanislas Polu and Ilya Sutskever. Generative language modeling for automated theorem proving. arXiv preprint arXiv:2009.03330 2020.
[55] Alethea Power, Yuri Burda, Harri Edwards, Igor Babuschkin, and Vedant Misra. Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets. arXiv preprint AXXi::2001.0217, 2022.
[56] Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In Proc. of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, 2005.
[57] Ronald L. Rivest. Cryptography and machine learning. In International Conference on the Theory and Application of Cryptology, pages 427-439. Springer, 1991.
[58] Ronald L Rivest, Adi Shamir, and Leonard Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 1978.
[59] David Saxton, Edward Grefenstette, Felix Hill, and Pushmeet Kohli. Analysing Mathematical Reasoning Abilities of Neural Models. arXiv preprint stXiv:1904.011 2019.
13

---

[60] Shai Shalev-Shward Ohad Shamir, and Shaked Shammah. Failures of gradient- based deep learning. In Proc. of ICML. 2017.
[61] Feng Shi, Chonghan Lee, Mohammad Khairul Bashar, Nikhil Shukla, Song-Chun Zhu, and Vijaykrishnan Narayanan. Transformer-based Machine Learning for Fast SAT Solvers and Logic Synthesis. arXiv preprint arXiv:2107.07116, 2021.
[62] Peter W Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th Annual Symposium Foundations of Computer Science, 1994.
[63] Jaewoo So. Deep learning- based cryptanalysis of lightweight block ciphers. Security and Communication Networks, 2020.
[64] Shivin Srivastava and Ashutosh Bhatia. On the Learning Capabilities of Recurrent Neural Networks: A Cryptographic Perspective. In Proc. of ICBK, 2018.
[65] Ilya Sutskever, Oriol Vinyals, and Quoc V Le. Sequence to sequence learning with neural networks. In Proc. of NeurIPS, 2014.
[66] Andrew Trask, Felix Hill, Scott Reed, Jack Rae, Chris Dyer, and Phil Blunsom. Neural 2018.
arithmetic logic units. arXiv preprint
[67] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Proc. of NeurlPs, 2017.
[68] Sean Welleck, Peter West, Jize Cao, and Yejin Choi. Symbolic Brittleness in Sequence Models: on Systematic Generalization in Symbolic Mathematics, 2021.
14


Reviews:
[{"review_id": "d7xBDCaFugg", "reviewer": "Reviewer_bqbN", "summary": "The paper proposes a machine learning approach to modular arithmetic and to breaking LWE-based cryptosystems based on said arithmetic.\n", "questions": "Do you agree that the running time of secret recovery roughly corresponds to the number of possible secrets?\n", "limitations": "yes", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nThe 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\".\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "cGzR-4LYfB5", "reviewer": "Reviewer_WA3X", "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.", "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?\n\nDoes 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?\n\nThe training data expansion technique seems to bear some resemblance to sieving-based SVP algorithms. Could you comment on this? Could it be helping?\n\nSince 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.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe paper is a pleasant read. It includes a good amount of problem-specific background.\n\nSALSA 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.\n\nThere 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.\n\nWeaknesses:\n\nThe 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.\n\nSALSA 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.\n\nIt is unclear whether SALSA can simultaneously handle higher Hamming weights and higher dimension.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "_VYZ-fH3v5M", "reviewer": "Reviewer_sMrM", "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.\n\nAfter 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.", "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.\n", "limitations": "No big limitation, except maybe the one I raised in the strength/weaknesses.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\nOverall, 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.\n\nMy 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. \nYet, 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.\n\nI 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*.\n\n[1] https://proceedings.neurips.cc/paper/2020/hash/e7e8f8e5982b3298c8addedf6811d500-Abstract.html\n\n[2] https://proceedings.mlr.press/v70/shalev-shwartz17a.html", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "1DzGu1REf-k", "reviewer": "Reviewer_fdwD", "summary": "- The authors propose SALSA, an attack on LWE-based cryptographic schemes, which has emerged as quantum-resistant cryptosystem, based on machine learning. \n- The authors demonstrate that the process of modular arithmetic can be trained using transformer.\n- Using trained transformer, the authors show that the instances from LWE can be distinguished from random instances.\n- The authors propose two secret recovery algorithms, `direct secret recovery` and `distinguisher secret recovery`, and they justify these algorithms theoretically.", "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.\n- 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. \n\nPOST 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.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n- The idea to perform modular arithmetic using a transformer seems interesting and novel.\n- The method can recover secret even though the trained transformer has low-accuracy.\n- Tables in the appendix are very helpful. For example, Table 20 and Table 21 helps me understand the broad effectiveness of the method.\n\n# Weaknesses\n- The algorithms require large computational resources and long runtime.\n- Scalability of the method with respect to the dimension of the lattice seems poor. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept