SALSA VERDE: a machine learning attack on LWE with sparse small secrets
Authors: Cathy Yuanchen Li
Emily Wenger
Zeyuan Allen-Zhu
Francois Charton
Kristin E. Lauter
Venue: NeurIPS 2023 poster (2023)
Keywords: machine learning
cryptography
cryptanalysis
TL;DR: We demonstrate successful machine-learning based attacks against learning with errors problems with small, sparse secrets.

Abstract: Learning with Errors (LWE) is a hard math problem used in post-quantum cryptography. Homomorphic Encryption (HE) schemes rely on the hardness of the LWE problem for their security, and two LWE-based cryptosystems were recently standardized by NIST for digital signatures and key exchange (KEM).  Thus, it is critical to continue assessing the security of LWE and specific parameter choices. For example, HE uses secrets with small entries, and the HE community has considered standardizing small sparse secrets to improve efficiency and functionality.  However, prior work, SALSA and PICANTE, showed that ML attacks can recover sparse binary secrets. Building on these, we propose VERDE, an improved ML attack that can recover sparse binary, ternary, and narrow Gaussian secrets. Using improved preprocessing and secret recovery techniques, VERDE can attack LWE with larger dimensions ($n=512$) and smaller moduli ($\log_2 q=12$ for $n=256$), using less time and power. We propose novel architectures for scaling. Finally, we develop a theory that explains the success of ML LWE attacks.

SALSA VERDE: Errors with sparse small secrets
a machine learning attack on Learning With
Cathy Yuanchen Li FAIR, Meta
Emily Wenger
Zeyuan Allen-Zhu FAIR, Meta
The University of Chicago
Francois Charton'
Kristin Lauter"
FAIR, Meta
FAIR, Meta
Abstract
Learning with Errors (LWE) is hard math problem used in post-quantum cryp- tography. Homomorphic Encryption (HE) schemes rely on the hardness of the LWE problem for their security, and two LWEEbased cryptosystems were recently standardized by NIST for digital signatures and key exchange (KEM). Thus, it critical to continue assessing the security of LWE and specific parameter choices. For example, HE uses secrets with small entries, and the HE community has con- sidered standardizing small sparse secrets to improve efficiency and functionality. However, prior work, SALSA and PICANTE, showed that ML attacks can recover sparse binary secrets. Building these, propose VERDE, improved ML attack that can recover sparse binary, ternary, and narrow Gaussian secrets. Using improved preprocessing and secret recovery techniques, VERDE can attack LWE with larger dimensions (n = 512) and smaller moduli (log, 12 for n = 256), using less time and power. We propose novel architectures for scaling. Finally, we develop a theory that explains the success of ML LWWE attacks.
Introduction
Language models have been successfully applied to numerous practical science problems in recent years. For example, transformers [57] have been used to solve problems in mathematics 40 24]
theoretical physics (26), chemistry (50), and biology [46]. this paper, we present an application of transformers computer security: the cryptanalysis of Learning With Errors (LWE) [45), hard
math problem underpinning leading proposals for post-quantum public key cryptography.
Public-key cryptosystems are the main solution for secure communication over the Internet. Public keys can used encode messages or verify digital signatures or from user with the correspond- ing private key. Security relies on the fact that recovering the private key from the public data requires solving a computationally hard math problem. Most currently deployed public-key systems are based on RSA 47), which relies the hardness of factoring large numbers into products of primes. Unfortunately, large-scale quantum computers will enable implementation of Shor's algorithm [52). which can factor integers in quantum polynomial time and break such systems. As result, new hard problems are sought to serve as the basis of post-quantum public key cryptography (PQC). The US National Institute of Standards and Technology (NIST) ran year competition to define future PQC standards (2), and standardized 4 PQC systems July 2022 [17. Two of these rely on special cases of the same hard (and fhor-free) problem: Learning with Errors (LWE).
The Learning With Errors problem (LWE) assumes that is hard to recover a secret vector s, given many IWE samples (a, b). In L.W sample, each is random vector of integers modulo q is the dimension and q is the modulus), and a noisy modular inner product of a and the secret key s that is, b = a + mod with the error drawn from Gaussian distribution of
"Co-senior authors
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

width oe centered at O, ~ (O, o²)) and or < q. The hardness of LWE is related to the hardness of well-known lattice problems such as the (approximate) Shortest Vector Problem (SVP).
For example, given m samples (ag, b,), create a matrix Xmxn whose m rows the vectors a;- The unique shortest vector problem (uSVP) attack recovers the secret by finding the shortest vector in a lattice constructed from b, the columns of Amxx. and other parameters. The best known algorithms for solving SVP run in time exponential in the dimension n. Somewhat counter-intuitively, the smaller the modulus the harder the LWE problem. Approximate solutions can be computed in polynomial time with LLL 4T, but the approximation factor is exponentially bad (exponential in n.). We compare our results with uSVP attacks on LWE in $A.7
Most classical attacks on LWWE rely on lattice reduction 41 49
Machine learning (ML. attacks on LWE. SALSA 58 the seminal ML attack on LWE, uses a large collection of LWE samples {(a, b)] with the same secret to train transformer [57] that predicts b from a. SALSA presents methods for secret recovery via queries to the trained model, and observes that high model accuracy not needed: secrets are recovered as soon as the transformer starts to learn (training loss drops), SALSA is a proof of concept, recovering binary secrets with 3 or 4 nonzero bits for problems with dimension up to 128, small instances of LWE solvable via exhaustive search.
PICANTE builds on an observation from SALSA (158) Table 4]):
transformers trained on LWE samples {(a,b) with entries of a drawn from a restricted range instead of all of [0, q). can recover binary secrets with larger Hamming weights h (number of nonzero bits). So PICANTE introduces data preprocessing phase during which the LWE samples (a. b) are processed by BK7, lattice reduction algorithm, to obtain LWE samples with the same secret but smaller coordinate variance (and larger error, see $2). In addition to training the transformer on the preprocessed samples, PICANTE reduces the number of LWE samples required for the attack from 4 million in SALSA to 4n (e.g. 1400 for 350), and improves secret recovery. Overall, PICANTE can recover binary secrets for dimensions up to 350 and Hamming weight up to 60. This is a considerable improvement over SALSA, faster than the uSVP attacks we compare against, and out of reach for exhaustive search.
PICANTE has several limitations. First, it only recovers sparse binary secrets, an important but limited subclass of LWE. Homomorphic encryption (HE) may use binary secrets, but HE and other PQC schemes typically use ternary (8; E {-1, 0, 1}) or small ([sg) < k. A small) secrets. Second, PICANTE's preprocessing is costly dimension increases, making it difficult to scale PICANTE to dimensions larger than 350. For n = 512, log, Q = 45, PICANTE's preprocessing approach could not finish in month with full parallelization. Third, PICANTE only experiments with large modulus q: log, = 23 for n 256, log, = 27 for n = 300, and loga Q = 32 for n 350. Practical LWE-based systems use small q: LIZARD (11 recommends log, Q = 10 for n 608 with sparse binary secrets, and the HE standard 4 recommends log, q 25 for n = 1024 with ternary secrets.
Our work, SALSA VERDE, improves on PICANTE and makes the following contributions:
We introduce a two-bit distinguisher, a new secret recovery technique for sparse binary. ternary and small Gaussian secrets. VERDE fully recovers binary and temarry secrets equally well 3
We improve data preprocessing techniques, making them forty times faster and 20% more effective, enabling recovery of binary, ternary and small Gaussian secrets for dimension 512
We decrease the modulus q, showing VERDE outperforming uSVP attacks ($5)and $A.7).
We propose NoMod, a framework for understanding the success of ML-baaed LWE attacks ($5).
We present theoretical analysis to show heuristically that successful secret recovery depends only on Vh and the standard deviation of the distribution of the LWE data ($6) We experiment with encoder-only models and compare their success with seq2seq models ($7)
Key results. Our main finding is that small, sparse LWE secrets are weak. For dimension = 256. we can recover binary and ternary secrets with 10% sparsity (h/n) for log, q = 20, and with 3% sparsity when logg q = 12 (Table []. For 512, log, q = 41, we recover binary and ternary secrets with 2 11% sparsity. Furthermore, VERDE scales well to higher dimensions for small sparse secret recovery. Training VERDE models
3566/350/51 problems takes only 1.5/1.6/2.5 hours per epoch, a small proportional increase compared to the increase in n. Also, we find that VERDE runs faster than uSVP attacks, at the expense of using more compute resources in parallel (see A.7].
In T we report the timings for successful secret recoveries, for binaryfernary/Gaussia secrets, with varying n and log, The table records the highest h recovered for each column: for binary secrets,

---

h is the Hamming weight, and for ternary and Gaussian secrets, h is the number of non-zero entries. We record the amount of time needed for each stage of the attack, preprocessing (in hours/CPU, assuming full parallelization), model training (hours/epoch (# epochs)), and total attack time. For full parallelization, the number of CPU cores required million divided by 2n. Source code and parameters to reproduce our main experiments are included in the supplementary material. The full code base will be open-sourced.
Table 1. VERDE attack times (preprocessing, model training, and total), for dimension v. and loga 4- h = # pon-zero entries in recovered secrets, = binary, = ternary, g = Gaussian secret distributions.
[n. logg R)
(256, 12)
(256, 20)
(350, 21)
(350. 27)
(512, 41)
secret distribution
g
b
g
highest/ h
33
24
7
12
13
36
36
10
63
58
16
preprocessing (hrs/CPU)
1.5
1.5
1,5
7.5
7.5
7,5
16
16
16
216
216
216
840
840
840
training time (hrs) total time (lus)
12
7.5
1.5
166
25.6
3.2
27.5
2.5
4,5 13.5
10.5
15
9
17.6
41.6
17.6
218
234
220
858
868
843
Scope of results. Instances of cryptographic problems like LWE can be broadly categorized as easy (solvable via exhaustive search), medium-to-han (requiring significant resources to solve), or standardized (believed secure). VERDE attacks medium-to-hard LWE problems (parameterized by dimension n, Hamming weight h, modulus q). VERDE does not attack toy problems (like SALSA did), does it attack the NIST standard directly. Rather, VERDE demonstrates successful attacks on mreiium-to-hard LWE problems using tools from AI, improving our understanding of the security of proposed LWE-based cryptosystems.
2 SALSA VERDE Overview
In this section we describe the SALSA VERDE attack and relevant parts of its predecessor PICANTE.
Data preparation
Model training
Secret recovery
Rb,
RIA, s
E o a N(D.A) k) use 2.ni d'aingister Distinguisher
(ay
After each enoch
A₁
ReszzA
(RA, Rb)
y stops dbe. keep solving
1 4n LWE
< Resample aus to make (")ymatrics
Reduce with BKZ
@ Train transformer on
X Run secret recovery on trained mode
samples
BKZ-reduced samples
Figure 1. Overview of VERDE'S attack methodology
High-level overview. Like PICANTE, VERDE starts with 4n LWE samples with the same secret s. In practice, this data would be eavesdropped. VERDE then proceeds in three stages: preprocessing, model training and secret recovery (see Figure []. The preprocessing stage augments the 4n initial (a, b) pairs to 2 million, then runs lattice reduction to yield a training set of million samples with the same secret The preprocessed data is used to train transformer to predict b from a. After each training epoch (2 million LWE samples), the model is queried to form a secret guess. The attack succeeds if the secret guess is correct, tested via statistical methods without knowledge of the actual secret. Otherwise, the model is trained for another epoch, and secret recovery is run again.
Data preprocessing. VERDE'S ' preprocessing is similar to PICANTE's, with several improvements. First, create X matrices A, by sampling without replacement of the 4n original LWE samples. Then, we apply lattice reduction to the matrices A, to reduce the standard deviation of their entries (initially uniformly distributed over g)). This process generates 2n preprocessed samples (a', b"), with the same secret and is implemented in parallel to create a training set of 4 million samples.
During lattice reduction, PICANTE applies BKZ (as implemented in fpll (7 to the 2n 2n matrix:
W In A; BKZ finds a linear transformation [R; C.J such that the norms of the 2n
A; =
q. I. C,J.
rows of [R. generates 2n reduced LWE pairs (R,A,, R,b.) (modulo q). VERDE instead rearranges the rows of
[w W., R,A, + 1-- q. C.] are small. Applying R. to A, and b, PICANTE
0 g. In This reduces the number of operations A,
A; and applies lattice reduction to A'; w I I,
needed for lattice reduction and allows BKZ to run with lower floating point precision. These two improvements cut the preprocessing time significantly.
3

---

They also result in smaller R, norms (smaller enror in R,b;), which can be leveraged to further reduce the norm of R,A; + q C, by using a lower w parameter (w 10) than PICANTE (w = 15). Finally, VERDE replaces BK7. with two interleaved algorithms (BKZ. 2.0 [9 and the efficient reduction technique introduced in (15)), adaptively increases the blocksize and precision as reduction progresses, and introduces a stopping condition. For instance, for n. = 256 and loga 9 20, VERDE'S preprocessing is 45x faster, while improving the quality of the reduction by 20% (Table 2)
Table 2. Impact of successive improvements to preprocessing. n = 256, loga q = 20, Reduction factor of the standard deviation of entries of A;: lower is better. Time: # of hours to preprocess one matrix on one CPU.
preprocessing technique
reduction factor
time (hrs/CPU)
PICANTE
0.53
338
+ reordered A, rows
0,47
136
+ reduced floating point precision
0,47
24
reduced parameter from 15 to 10
0.43
38
VERDE (+ interleaved reduction, adaptive blocksize, early stopping)
0.43
7.5
Quality of reduction measured by the standard deviation of the entries of A,, Preprocessing time in Table 2 is the hours needed to process one matrix on single CPU. We list the time for all n, attempted in Tables and 19 For each dimension n and modulus q, we process million/n matrices in parallel across hundreds of CPUs, see SA.1 for details. Better preprocessing allows VERDE to scale to larger dimensions and retrieve secrets with larger h.
Transformer training. The 4 million reduced LWE pairs are used to train a transformer to predict b from a. The values b and the coordinates of a are integers in g). They are represented in base B = [q/8] (for log, q > 30, B- (g/16) and encoded as sequences of two tokens over a vocabulary 2f 000 (see $A.1for for a discussion of these choices). Model training is framed as a translation task, from a sequence of 2n tokens representing a to sequence of 2 tokens representing b (see [40] [2] for similar uses of transformers for mathematical calculations). The model is trained to minimize the cross-entropy between model prediction and the sequence of tokens representing b, using the Adam optimizer with warmup [39 and a learning rate of 10-5, For 250 and 512, each epoch uses 2 million LWE samples and runs for 1.5, 1.6, or 2.5 hours. Time/epoch doesn't 't vary with g or secret type. Our models train on one NVIDIA V100 32GB GPU and often succeed in the first epoch for low h. Number of epochs required are included in many tables throughout, including Tables Iaand 4
VERDE uses the same architecture as PICANTE: a sequence to sequence (seq2seq) transformer [57] with a one-layer encoder (dimension 1024, attention heads), and a 9-layer decoder (dimension 512, 4 heads). The last 8 layers of the decoder are shared (i.c. they form Universal Transformer (25)).
Iteration through shared loops is controlled by the copy-gate mechanism introduced in [22].
Seq2seq models allow output sequences to be longer than inputs, a useful feature for machine translation but not necessary our setting. For comparison, we also implement simpler encoder- only transformer, that is 4-yeyer BERT-like (dimension 512, 4 heads), together with rotary word embeddings (analogous to the rotary position embeddings (55) to account for the modular nature of the problem. On top of this, we also add an earth mover's distance (EMD) auxiliary objective. We compare this model's performance to that of the seq2seq model (37).
Secret recovery. Secret recovery runs after each epoch (2 million LWE samples). PICANTE used three recovery methods: direct recovery, cross-attention and distinguisher. Direct recovery struggles as dimension increases, because it relies on accurate model evaluations at special values which are out of distribution for the training set. Cross-attention is incompatible with encoder-only architectures and is consistently outperformed by the distinguisher on preDD--prproceeseed data. Thus, VERDE only uses the distinguisher, which works as follows: for any test vector agst and random K, if the i-th entry of the secret s; is zero, then (atest Ke.) . = acst 5 (where e; is the i-th standard basis vector). Therefore, for each i, the distinguisher computes the difference between model predictions on agea and a + Kc; for different aget- If differences are small, the corresponding s; is likely zero For ternary and Gaussian secrets, the distinguisher is modified (see $3)
For successful secret recovery, the trained model must generalize well to (atest) the vectors used for testing. In PICANTE, the distinguisher runs on random Aestt with coordinates uniform in [0. g). However, the model is trained on preprocessed Arain: with a non-uniform coordinate distribution. So PICANTE's 's distinguisher recovery requires that the model generalize outside its training distribution.

---

This is known to be difficult ML task. Instead, VERDE runs the distinguisher on a held-out subset of 128 preprocessed vectors a Since the test vectors have the same distribution as the training set, the trained model only needs to generalize in-distribution, a much easier task. This change in Aeett improves the performance of the distinguisher (see Table 14 in $A.4).
In practice, for each secret coordinate, the distinguisher computes the sum of the absolute difference e, for 128 vectors arst and a random K (0.3g. 0.7q) for each atest- The model makes a secret prediction s' by setting the bits to 1 on the h coordinates with the largest sums, and verifies s' by computing a s' on the original 4n LWE samples. If the secret is correctly predicted, this quantity should always be small. The statistical properties of this test are discussed in section A.2 of [42].
between model predictions at agst and aest KKe,
Having discussed VERDE'S background and described its methodology, we now present VERDE'S key results, as summarized in { We begin with results ternary and narrow Gaussian secrets.
3 Secret Distributions
One of VERDE'S major contributions is a method to recover secrets from sparse ternary and narrow Gaussian distributions, both of which are being considered for use in real-world cryptosystems [4]. Prior ML-bbased LWE attacks (PICANTE and SALSA) only recovered sparse binary secrets. Here, we describe VERDE'S ' method for recovering these more general secret distributions, and its performance on ternary and small Gaussian secrets for fixed dimension n 256 and log, q = 20. Throughout this paper, & denotes the number of nonzero entries in a secret, which is equal to the Hamming weight in the binary case. We define secret sparsity as the percentage of nonzero secret entries h/n.
Recovering ternary and small Gaussian secrets. In luttice-based cryptography, ternary secrets are vectors of dimension n, with entries equal to 0, 1, or -1 (with equal probability of and - in sparse secrets). Gaussian secrets are vectors s of dimension n, with entries drawn from a Gaussian distribution with small standard deviation a. In this paper, we use o = 3. The Homomorphic Eneryption Standard includes secure parameter choices for Gaussian secrets with o 3.2.
Ternary and Gaussian secrets introduce new challenges for ML-based attacks on LWE. The recovery methods in PICANTE distinguish zero from nonzero bits. In the binary case, this produces one guess S guess. which can be verified by checking that b - a Sguess is small. In the temary case, PICANTE would produce 2h secret guesses (about 12" guesses for Gaussian secrets), due to the additional - entries, and verification becomes very expensive as h increases. VERDE recovers ternary secrets using a two-step approach: first, partial recovery distinguishes zero from nonzero entries, then recovery guesses the sign of the nonzero bits.
Partial recovery. To identify nonzero bits, VERDE uses the binary secret distinguisher from ? (after 42 Section 4.3]). For each secret bit, it computes score from a sample of reduced LWE pairs. The h bits with the highest scores are candidate nonzero bits. VERDE assumes / is not known and runs the next step for all reasonable possible values of h, e.g. from 1 to n/20. Partial recovery alone is a major contribution, as we are not aware of existing attacks that can identify nonzero secret bits.
Full recovery (ternary secrets). To determine whether nonzero bits of a ternary secret are 1 or -1, VERDE introduces a novel two-bit distinguisher, leveraging the following observation. If two nonzero secret bits s; and 8j equal, then for any exchanging the coordinates a, and a, will result in the same b, and corresponding model predictions will be close. Otherwise, model predictions will be different (if s, + sy). Similarly, if s; 8j, for any and c # O. changing a; a; + c and aj + a c yields the same b, and close model predictions. The two-br bit distinguisher uses these techniques to compare each nonzero bit with all others, therefore defining two classes of nonzero bits. Letting one class of bits be or 1, VERDE produces two secret guesses to he verified.
Full recovery (Gaussian secrets). At present, we implemented full recovery only for binary and ternary secrets. However, full recovery of small Gaussian secrets is possible via the following adaptation of the two-bit distinguisher. The two-bit distinguisher groups nonzero secret bits into k classes believed to have the same value. In our case, the nonzero bits follow a Gaussian distribution with σ = 3, so we may safely assume that all non-zero secret bits are in 9, 9] (within 3 standard deviations) - i.e. k = 18. Since the secret is Gaussian, we expect the largest classes to correspond to the values- -1 and 1, followed by -2 and 2, and on. Therefore, we can intelligently assign
values to classes based on class size, and test the corresponding 2 512 secrets. We leave
5

---

implementation of this as future work and report the performance of partial Gaussian secret recovery. using knowledge to validate correctness.
Table 3. Partial and full ternary secret recovery. = 256, log, = 20. Epoch when secret is recovered.
h
5
10
15
20
21
22
23
24
25
partial recovery
8/10
6/10
6/10
2/10
3/10
2/10)
1/10
3/10
1/10
training epoch
0.0.0.0.0.0.1.7
0,0.1.111,1
0,0,0.1,2.8
0,2
0,1.3
2,5
9
0,4.7
2
full recovery
8/10
6/10
5/10
1/10
3/10
2/10
0/10
1/10
0/10
trining epoch
0,0,0,0.0.0.1,7
1,2.2,6,7,88
1,1,6,9.11
5
4,10,17
8,22
5,12
Table 4. Partial Gaussian secref recovery. n = 350, log, 4 = 27. Epoch when secret is recovered.
7
8
10
partial recovery
8/10
8/10
7/10
5/10
2/10
2/10
4/10
training epoch
0,0.0.0.I.11III11 0,0.0.1,2.333.77
0,0,1,2,2,5,10
2,2,3,7,10
0,2
1,9
1,5,6,12
VERDE'S performance across secret distributions. VERDE recovers temaary secrets with sparsity up to 10%.
35
type binary
with comparable performance on binary secrets. Table 3 provides details on partial and full ternary secret recovery
Nonzero entries
30
temary gaussian
25
for = 256 and log2 q = 20 and h 5 -55. For low values of h (h < 20), ternary secrets are partially recovered early during training (i.e. mostly in epoch or 1, during the first pass preprocessed data), and usually fully recovered the same epoch or shortly after. As h increases, more training is required for recovery, and the delay between partial and full recovery increases.
20
15
10
20
19
18
17
16
14
13
12
loga q
Figure 2. Best ls recovered vs. loga 4 and secret distribution. 256.
For small Gaussian secrets, VERDE only implements par- tial recovery (recovery of the nonzero bits). Table presents results for n 350 and log2 q 27. Recovered h are lower than in the binary case, and models require less training for low h.
Figure 2 compares VERDE'S performance across secret distributions for problems with = 256 and different moduli g. For each setting, we run 100 recovery experiments and report the highest h secret recovered in those attempts. Recovery is comparable for binary and ternary secrets. Small Gaussian secrets are significantly harder.
4 Large Dimension
The hardness of LWE increases as n grows. PICANTE recovered sparse binary secrets for dimension up to 350. VERDE pushes this limit to 512. for sparse binary, ternary, and narrow Gaussian secrets. For n = 512 and log, q = 41, VERDE recovers binary and ternary secrets with sparsity up to 0.12 (highest it = 63, 60) and Gaussian secrets with f up to 16. The longer VERDE'S preprocessing step runs, the higher h secrets it can recover. Recall that real-world schemes like LIZARD operate in dimension 608 (1 and HE in dimension
1024 (4) Those systems use significantly smaller q where LWE is harder: log, 9 = 10 and 27, respectively, compared to VERDE'S log, q = 41.
shows VERDE'S performance for dimension 512, after to 35 days of preprocessing, on the same set of matrices A,. For each preprocessing time, we measure the quality of lattice reduction via a "reduction factor," computed by taking the ratio of the standard deviation of reduced A; entries the standard deviation of random matrix with uniform coefficients 0 < a; < q, i.e. Addev(Auss))
VERDE'S performance in large dimension. Table Ishows
aaddev(Ass) with stddev( Amdd) viz This metric, used in
PICANTE for selecting BKZ parameters, is discussed in $ 6 As Table 5 demonstrates, the maximum recoverable h is strongly correlated to the quality of lattice reduction.
Preprocessing adjustments for large Scaling up to n 512 requires number of adjustments to our preprocessing methodology. For n 512, the first loops in BKZ 2.0 are very slow. To avoid this, use BKZ with smaller blocksizes than those used for 256 and 350 (see
A.I. Also, lattice

---

Table 5. Data preprocessing vs performance. n = 512. logg = 41. Highest values of h recovered, for
different reduction factors (lower factor better reduction).
preprocess time
reduction factor
binary h
ternary h
Gaussian /
7 days
0,519
16.17,17,20
17,20,20,21,21
8.8.8,8,10,10.11 11,11,11,2,12,12
10 days
0.469
21,22,23,28
22,24,.4,22,277,29
14 days
0,423
32.32.34.33.35,400
32.34,34,35,35
11.11.11,22.2.112
20 days
0.380
35.35.36,41,49
35,35.37 45,,4
13,13.13.16
28 days
0.343
40.43.45.44.55055...
40,41.41 44.4,4144444,44844888
13,13.14.16.16
35 days
0.323
48.48.49.55..57.59.66
45,46.50.55.58.66
14,16
reduction significantly slower for larger matrices. To mitigate this, for n 512, we use 448 LWE samples (instead of 512) when generating A; for lattice reduction, therefore reducing the matrix size from 1024 x 1024 to 960 x 960. Experimentally, we observe that using slightly fewer samples did not negatively impact our reduction factor attack performance.
5 Small Modulus
To define real-world parameters for lattice-based cryptography, standardization committees and communities (e.g. 44 (7)) select small enough modulus g (for fixed dimension n), that all known attacks are (heuristically) predicted to run in time at least 2128, therefore attaining the U.S. government minimum 128-bit security level. For classical lattice reduction attacks, the smaller the modulus, the more difficult the attack. This is because lattice reduction algorithms such as LLL and BKZ attempt to compute short vectors in Euclidean space, but eryptosystems operate modulo q. Smaller moduli result in smaller lattice volumes, meaning shorter target vectors are required to break the system. In our ML approach, we also observe that VERDE less likely to succeed when is smaller (see Table 6). Nevertheless, VERDE outperforms the uSVP attack (+A.7).
Table 6. Highest h recovered, 256, 350. Secret distributions are b binary, termary, g Gaussian.
Nonzero entries,
25
20
reduction factor
recovered h
loga
g
10
256, 20
0.43
7
5
256,
0.53
7
256.
0.63
20
18
16
14
12
256, 14
0.71
log2
256, 12
0.77
6
5
Figure 3. h of recovered secrets log, g 256. 10 random binary secrets atlempted for each h. One green represents successful recovery.
350, 27
0.38
36
36
10
350, 21
0.61
12
13
5
PICANTE vs. VERDE'S performance on small q. PICANTE attacks larger moduli: it can recover
binary secrets with h 31 for log, q 23 and 256, and h 60 for log, 32 and n 350. Table VERDE'S highest recovered h (in 10 random attempts) for dimensions 256 and 350 and different q for binary, ternary, and narrow Gaussian secrets. First, note that VERDE recovers binary secrets with = 33 for n = 256 and log, & = 20, but also, VERDE succeeds for much smaller 9. small as log2 9 12, wooldd parameter setting, demonstrating that VERDE significantly outperforms PICANTE. However, for smaller g. VERDE recovers only secrets with smaller h. As with classical attacks, the likely culprit lattice reduction: the reduction factor after preprocessing is 0.71 for log, g 12 versus 0.43 for log, 20, and for recovered binary secrets drops from 33 6. Section provides thcoretical explanation of this phenomenon.
Figure 3 visualizes VERDE'S success rates for = 256 with binary secrets. For every value of q and h. we run VERDE on 10 binary secrets, using the same preprocessed data. VERDE'S success rate decreases as increases. Attempting 10 random binary secrets for n = 256, log, 9 = 12, VERDE recovers secrets for up to h = 6 but not h 7.8 (Table However, with more attempts, VERdE recovers 1/10 1/100 binary secrets for h = 8. Experiments with different random seeds (see (A.2) suggest that model initialization alone is not responsible for how success rate trends with h.
Explaining success for smaller y via NoMod. Table indicates, given n and h, secrets are harder to recover for smaller q. This suggests that the modular operations in the computation of b

---

Table 7. NoMod % before/after permuting the columns of A. n. 256, logz 9 = 14, binary secrets. Each column is random secret for each h = 6, 7, Entries are the NoMod %. Green = secret recovered: red or black = failure.
Succeed? True
30
Count
25
z0
15
method
NoMod percentages und recovery success
original
56
61
60
61
56
52
67
67
76
67
0.4 0.5
0.6
0.7
0.8
permuted
57
67
56
67
62
67
60
60
.22
56
Proportion of NoMod training data
original permuted
60
60
52
49
60
75
55
60
55
56
Figure 4. Effect of NoMod data on secret recovery for n 256, binary secrets. Count = # of experiments.
67
52
60
75
60
73
60
71
59
66
original
60
74
74
66 60 66
55
60
63
55
permuted
55
55 60 52 55 60
55
49
60
60
from a might account for the difficulty. To investigate this, we evaluate, for a given known binary secret s. the percentage of samples where computing b did not require the modular operation, for the 4 million samples in our training set. More precisely, we represent the mod coordinates of a b without modular operations. If b was
and b in the interval /2/ q/2), and compute computed without modular operations, then x is equal to the error for that sample, which is small. Otherwise is equal to the error plus a multiple of q. For each (a, b). if [x| < q/2, then no modular operation was performed. We define NoMod to be the percentage of such x in the training set.
Figure 4 shows the distribution of secret recoveries, for varying NoMod, for 210 experiments with dimension n = 256 and log, q = 20. Clearly, recovery occurs when NoMod exceeds a threshold value, empirically observed to be 67%. These results confirm our hypothesis that modular arithmetic is the major cause of failure to recover secrets, and help explain the observation (42) $6.4) and $A.2) that some secrets are never recovered, matter how many model initializations are tried. For a given secret, NoMod is a property of the training data, not of model initialization, and multiple initializations only seem to help when NoMod is close to the recovery threshold.
trick for improving attack success. The NoMod percentage can only be calculated if the secret is known, so it cannot aid real-world attack settings. However, our NoMod observations suggest that, if recovery fails for a given secret s, the failure may be due to low NoMod factor in the preprocessed training set. This reveals a strategy for potentially recovering such secrets. If an initial run of VERDE fails for a secret s, start over with the (un- preprocessed) matrices A,, sampled from the original LWE samples. For each of these, apply random permutation 1I to the columns and preprocess the permuted matrices. This creates a new dataset of A' with corresponding i', associated to a permuted counterpart s' of the original secret If the NoMod of s', D' and A' is higher that that of b and A (though this cannot be measured), s' can be recovered. If the attack succeeds, S can be restored by applying the inverse of permutation II. Table presents the impact of permutations NoMod for 10 secrets and h = 6, 7, 8 for n 256 and log, 4 14. Some secrets become recoverable after using the permutation trick.
6 A Theoretical Scaling Law for VERDE
Intuition. The NoMod experiments provide key insight about the hardness of secret recovery in SALSA-based attacks on LWE They suggest that secret s can be recovered from training set if over 67% of the {z = a s - b} are concentrated in the interval of length 9. If the random variable x Gaussian (a reasonable assumption for h >> 1, since the entries of a are random and bounded), 68% of its values will be within one standard deviation of its mean, i.e. spread over two standard deviations. Therefore, for the secret to be recoverable, the standard deviation of x should satisfy o₂ S 9/2. If is a binary secret with Hamming weight h, and the entries of a have standard deviation da. have x x a s and 0g Re Vho, + a. vho.. Therefore, is recoverable if Vho, & 9/2. or O. I 7
2/T
Scaling Laws. We now apply this insight to the experimental results of ML-based attacks on LWE. Consider the original SALSA attack, which does not utilize data preprocessing. Since the entries of a are uniformly distributed over (0, [0,4). a, - Replacing in o. S 2 yields h < 3, the main experimental result of SALSA. If we constrain the entries of a to be in [0, ag) (Table in (58). we 3 have o, -9_ and la < 2 Applying this formula for a E 0.6, 0.55, 0.5, 0.45, we obtain maximal recoverable Hamming weights of 8, 10, 12 and 15, which closely match SALSA experimental results.
8

---

These results shed light on the role of preprocessing in PICANTE and VERDE. When the standard deviation of a is reduced by factor a, maximal recoverable increases by a factor d However, the formula v , underestimates actually recovered by a factor of 2. For instance, from the reduction factors from Ta we should expect recovered à to range from 11 to 29 as preprocessing time increases from 7 to 35 days, but actual recovered ranges from 20 to 63. As seen in $5 the preprocessing step makes some secrets easier recover for the same h, VERDE performs better than predicted by theory for some secrets (at the expense of other secrets). Finally, note that the formula for the standard deviation of is the same for ternary and binary secrets. This accounts for the observation in s that ternary secrets are of similar difficulty for VERDE as binary secrets.
7 Model architecture
VERDE'S baseline model uses a seq2seq architecture as in SALSA and PICANTE. Here, we compare it the new encoder-only model discussed in $2 Specifically, this new model is based on the DeBERTa [34] model but replaces its "relative positional embeddings" with rotary word embeddings, in the spirit of rotary positional embeddings (RoPE) [55] but applied to the integer words. It has 4 layers, 4 heads and 512 dimensions. On top of the cross-entropy loss, we add an auxiliary. squared earth mover's distance (EMD) loss to compare model's softmax distribution with the target b. This encourages the model to make predictions that are at least close to the targets, if not exact matches. Trained with the auxiliary EMD loss, the model also replaces the beam search used in the distinguisher with novel EMD-based distinguisher that compares the difference between the distributions produced by the model on aret and agst + ke,.
Table 8. Performances of seq2seq and encoder-only models. 256, log, 9 = 12; 512, log2 9 41. For binary and temary secrets, we run 10 secrets per and indicate the epochs of full recovery.
n, secret
256, binary
256, ternary
512, binary
512, ternary
h
5
6
4
6
57
59
63
55
58
60
Seq2seq Encoder-only 20,23,27
7
4,7
0,5,7,18
0,0,1
7
16
11
16,23,28
0, 0,16,27
1,1,2,6
2
2
3 3
6 5
Overall, we find that the performance of the two models are comparable (see Table 88. The encoder-
only model requires more training epochs before recovery for 256, logz q T2, but requires fewer epochs for n = 512, and may scale well to larger n. Furthermore, we observe that the EMD distinguisher still enables full recovery of ternary secrets with high h.
8 Related Work
ML for cryptanalysis. Numerous proposals leverage ML for cryptanalysis, either indirectly or directly. We call approaches which use ML as part of (but not the main element of) the cryptanalysis process indirect approaches. Indirect approaches typically use ML models to strengthen existing cryptanalysis approaches, such as side channel or differential analysis [18). Most relevant to this work is a recent paper showing the successful use of ML algorithms in side-channel analysis to attack Kyber, one of the NIST standardized PQC proposals (28.. Direct ML-based cryptanalysis schemes train models to directly recover cryptographic secrets from plaintext/ciphertex pairs or similar information. Such approaches have been studied against variety of cryptosystems, including
block ciphers 22 18
38 8), hash functions (30 and substitution ciphers 11 [44) 7 31 The
two basda LWE attacks described in S SALSS
58 and PICANTE [2]. fall under this heading.
Use of transformers for mathematics. In recent years, language models have been used solve math problems beyond the cryptanalysis applications explored in this work. Much prior work has considered how well language models can solve written math problems [35 48
More recently, (32
showed large transformers could achieve high accuracy on elementary/high school problems, and (59
explored the accuracy of GPT-3 [I] on math word problems. Language models have also been applied to formalized symbolic math problems. After [40] demonstrated that transformers can solve such problems with high accuracy, follow-up work has explored transformers' use theorem proving dynamical systems 13. SAT solving [51). transport graphs [4], and symbolic regression Finally, some have proposed customizing model architectures to enable specific arithmetic operations
43
10 23
33 [6] 44).

---

Discussion
We present VERDE, a ML-based attack on LWE with sparse small secrets. VERDE improves data pre- processing and secret recovery, enabling significant performance gains over prior work, SALSA [58] and PICANTE 42 In particular, VERDE can recover secrets with more general distributions (ternary, small Gaussian), larger dimensions n. smaller moduli 9. and higher h. In our implementation. VERDE outperforms the uSVP attack, requiring less time but more compute resources (details in Appendix A.7). Most importantly, this work provides key theoretical insights into observed attack performance, paving the way for targeted future work. Note that even if we recover secrets with seemingly low probability, such recover all secrets successfully, such as we recover one out of ten secrets with our attack, this is still enough to make these cryptosystems unsafe to use with low weight secrets (unless there is way to check for vulnerability to our attack without running the attack).
seed out of ten succeeds for that secret (1/10), or if we do not
Limitations and broader impact. Despite significantly advancing the state-of-the art in ML-based LWE attacks, VERDE cannot yet break standardized LWE-based PQC schemes, limiting its real- world impact. Because of this, our paper raises no immediate security concerns. Nevertheless, we have shared copy of our paper with the NIST PQC group to make them aware of this attack.
Future work. Scaling VERDE to attack real-world systems requires work in several directions: increasing dimension n, reducing modulus q. and increasing h. the number of nonzero entries in recoverable secrets. Continued innovations in model architecture (a la 7 may allow attacks in higher dimension n, while the theoretical scaling law of 6 provides helpful guidance for improving g and h. Given our new insight and analysis of the importance of the NoMod percentage, we conclude that the reason that small q hard for the transformers with our current approach is that they are not good at modular arithmetic (not yet, anyway this is an area for future work and improvement). In addition, our preprocessing not well-suited what precisely needed and relies on existing lattice reduction algorithms which scale poorly with and q.
This suggests two avenues for improvement: first, develop model architectures that perform modular arithmetic better. Limited existing work has studied the application of ML to modular arithmetic more broadly [44] 333, Second, alternative preprocessing techniques should be developed to directly concentrate the distribution of random vectors, without relying on lattice reduction methods. With the goal of reducing the standard deviation of the training data, around any center, techniques from the broader math community may prove helpful.
We thank Jana Sotáková for her contributions to developing the attack on ternary secrets, Hamming reduction techniques, and Section A.3. We also thank Mark Tygert for his helpful input.
Acknowledgements.
10

---

References
[1] Ezat Ahmadzadeh, Hyunil Kim, Ongee leong, and Inkyu Moon. Novel Dynamic Attack on Classical Ciphers Using Attention-Basee LSTM Gncodde-Decoderr Model. IEEE Access, 2021.
Status report on the [2] Gorjan Alagic, Jacob Alperin-Sherift Daniel Apon, standardization process. US second round of the nist post-quantum cryptography Department of Commerce, NIST, 2020. httpp:://ww.. nist howppi..oo/publiiciionn////// Ceatus-reporee second- process
www.erreesooooo-ooooteeeee -iandd-istt---e nist-post- quantum wuwpauawwwcccgggggoeaaaaaaaaaaaa
[3] Mohammed M Alani. Neuro-cryptanllysis DES and triple-DES. In Proc. of NeurIPS, 2012.
[4] Martin Albrecht, Melissa Chase, Hao Chen, et al. Homomorphic encryption standard. In Protecting Privacy through Homomorphic Encryption, pages 31-62. Springer, 2021. https
//eprint. iacr. org/ 2019/9319
[5] Martin R. Albrecht. On Dual Lattice Attacks Against Small-Secret LWE and Parameter Choices in HElib and SEAL.. In -ean-Sébastien Coron and Jesper Buus Nielsen, editors, Advances Cryptology - EUROCRYPT 2017, pages 109-129, Cham, 2017. Springer International Publishing, https: btttss://eprinn iacr org/ 2017/047
[6] Martin R. Albrecht, Rachel Player, and Sam Scott. On the concrete hardness of learning with errors. Journal of Mathematical Cryptology, (00)169-2033 2015. https://eprint. iacr org/2015/045
[7] Nada Aldarra and Jonathan May. Can te--ennune-------nnee-e--- models crack substitution ciphers? 2020. https: //axxi org/abs/2012..5222
[8] Seunggeun Back and Kwangjo Kim. Recent advances of neural attacks against block ciphers. In Proc. of SCIS, 2020.
(9] Adrien Benamira, David Gerault, Thomas Peyrin, and Quan Quan Tan. A deeper look at machine cearning-bssed cryptanalysis. In Proc. of Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2021.
[10] Luca Biggio, Tommaso Bendinelli, Alexander Neitz, Aurelien Lucchi, and Giambattista Paras- candolo. Neural symbolic regression that scales. 2021. attps://arxiv..t Serrg/abs/2100
06427
[11] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, et al. Language models are few-shot learners. In Proc. of NeurlPS, 2020.
[12] François Charton. Linear algebra with transformers, 2021. https://arxiv.org/abss. 01898
[13] François Charton, Amaury Hayat, and Guillaume Lample. Learning advanced mathematical computations from examples. 2020. hattps://arxiii www//oggg/b......o.... aas/ab/6..00000
[14] François Charton, Amaury Hayat, Sean T. McQuade, Nathaniel J. Merrill, and Benedetto Piccoli. A deep language model to predict metabolic network equilibria. 2021. https
//arxiv. org/ abs/2112 03588
[15] François Charton, Kristin Lauter, Cathy Li, and Mark Tygert. An efficient algorithm for integer lattice reduction, 2023.
[16] Hao Chen, Lynn Chua, Kristin Lauter, and Yongsoo Song. On the Conerete Security of LWE with Small Secret. Cryptology ePrint Archive, Paper 2020/539, 2020. https: /ttp:sit////tttt./e iacr
org/2020/539)
[17] Lily Chen, Dustin Moody, Yi-Kai Liu, et al. Announcing Four Candidates to be Standardized. Plus Fourth Round Candidates. Department of Commerce, NIST, 2022.
PQC Standardization Process:
2022/
pqc- coc--canddatte--ttee to soo-bb-standdee standardized and- rouuu-----

---

[18] Yi Chen and Hongbo Yu. Bridging Machine Learning and Cryptanalysis via EDLCT. Cryptology ePrint Archive, 2021. https://eprint. iiarr.ir.. org/2021/705
iacr.
[19] Yuanmi Chen and Phong Q. Nguyen. BKZ 2.0: Better Lattice Security Estimates. In Proc. of ASIACRYPT 2011, 2011.
[20] Jung Hee Cheon, Minki Hhan, Seungwan Hong, and Yongha Son. A Hybrid of Dual and Meel-in-the-Middle Attack on Sparse and Ternary Secret LWE. IEEE Access, 2019.
[21] Jung Hee Cheon, Duhyeong Kim, Joohee Lee, and Yongsoo Song. Lizard: Cut Off the Tail! A Practical Post-quantum Public-Key Encryption from LWE and LWR. In Dario Catalano and Roberto De Prisco, editors, Security and Cryplography for Networks, pages 160-177, Cham, Springer International Publishing- hattps://eprint:: iacr org. /twgg////////// 1126 pdff
2018.
[22] Róbert Csordás, Kazuki Irie, and Jürgen Schmidhuber. The Neural Data Router: Adaptive Control Flow in Transformers Improves Systematic Generalization. In Proc. of ICML, 2022.
[23] Stéphane d' Ascoli, Pierre-Alexande Kamienny, Guillaume Lample, and François Charton. Deep symbolic regression for recurrent sequences. 2022. https://arxii: www.:oog///aaaa.eeeoo 04600
[24] Alex Davies, Petar Veličković, Lars Buesing, Sam Blackwell, et al. Advancing mathematics by guiding human intuition with AI. Nature, (7887), 2021.
[25] Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. Uni- versal transformers. Proc. of ICLR, 2019.
[26] Aurélien Dersy, Matthew D. Schwartz, and Xiaoyuan Zhang. Simplifying polyoggarttmss with machine learning, 2022, https: www.aaiwv..ooroaaaaa htwpg/bb//2206.000/
[27] The FPLLL developmet team. fplll. a lattice reduction library, Version: 5.4.4. Available at httpss//gttbubb.com/pp//////
2023.
[28] Elena Dubrova, Kalle Ngo, and Joel Gärtner. Breaking a fifth-order masked implementation of crystals-kyber by copy-paste. Cryptology ePrint Archive, 2022. https:///pprntt. iacr org/2022/1713
[29] Aron Gohr. Improving attacks round-reduced speck32/64 using deep learning. In Proc. of Annual International Cryptology Conference, 2019.
[30] Sergij V Goncharov. Using fuzzy bits and neural networks to partially invert few rounds of 19911023311010888
some cryptographic hash functions. 2019.
[31] Sam Greydanus. Learning the enigma with recurrent neural networks. 2017. attps://arxis org/abs/1708.079
[32] Kaden Griffith and Jugal Kalita. Solving Arithmetic Word Problems with Transformers and Preprocessing of Problem Text. 2021. http://aww....r//aa////..0....
[33] Andrey Gromov. Grokking modular arithmetic, 2023. https://arxiv.org wwwpxxiv.rgg/p///22
02679.po .dff
[34] Pengcheng He, Xiaodong Liu, Jianfeng Gao, and Weizhu Chen. Deberta: Decoding-enhanced BERT with disentangled attention. In Proc. of ICLR, 2021.
[35] Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Computation, 1997.
[36] Lukasz Kaiser and Ilya Sutskever. Neural GPUs learn algorithms. 2015. https://arxi: org/ ht////b///55// 1t1.//11111100 08228
[37] Ravi Kannan. Minkowski's Convex Body Theorem and Integer Programming. Mathematics of Operations Research, 12:415-446 4400 1987.
12

---

[38] Hayato Kimura, Keita Emura, Takanori Isobe, Ryoma Ito, Kazuto Ogawa, and Toshihiro Ohigashi. Output prediction attacks on block ciphers using deep learning. In Proc. of Applied Cryptography and Network Security Workshops, 2022.
[39] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Proc. of ICLR, 2015.
[40] Guillaume Lample and François Charton. Deep learning for symbolic mathematics. In Proc. of ICLR, 2020.
[41] H.W. jr. Lenstra, A.K. Lenstra, and L., Lovász. Factoring polynomials with rational coefficients. Mathematische Annalen, 261:515-534, 1982.
[42] Cathy Li, Jana Sotáková, Emily Wenger, Mohamed Malhou, Evrard Garcelon, Francois Charton, and Kristin Lauter. SALSA PICANTE: machine learning attack on LWE with binary secrets, 2023.
[43] Stanislas Polu and Ilya Sutskever Generative language modeling for automated theorem proving. 2020. http:://///avvv.oooaaa/o
03393
[44] Alethea Power, Generalization beyond overfitting on small algorithmic datasets, 2022. https:://arrt /ttp///axvvvvv./////// org/
Yuri Burda, Harri Edwards, Igor Babuschkin, and Vedant Misra. Grokking:
abss2201.022 02177
[45] Oded Regev. On Lattices, Learning with Errors, Random Linear Codes, and Cryptography. In Proc. of the Seirth-Seventh Annual ACM Symposium on Theory of Computing. 2005. https 7
cs- DS 0300000.000500 bib
[46] Alexander Rives, Joshua Meier, Tom Sercu, Siddharth Goyal, Zeming Lin, Jason Liu, Demi Guo, Myle Ott, C. LLwrence Zitnick, Jerry Ma, and Rob Fergus. Biological structure and function emerge from scaling unsupervised learning to 250 million protein sequences. Proceedings of the National Academy of Sciences, 2021.
[47] Ronald Rivest, Adi Shamir, and Leonard Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 1978.
[48] David Saxton, Edward Grefenstette, Felix Hill, and Pushmeet Kohli. Analysing Mathematical Reasoning Abilities of Neural Models. 2019.
[49] C.P. Schnorr. A hicrarchy of polynomial time lattice basis reduction algorithms. Theoretical Computer Science, 53(2):201-25) 224, 1987.
[50] Philippe Schwaller. Teodoro Laino, Théophile Gaudin, Peter Bolgar, Christopher A. Hunter, Costas Bekas, and Alpha A. Lee. Molecular transformer: A model for uncertainty-calirateed chemical reaction prediction. ACS Central Science, 5(9):1572-1583, 2019.
[51] 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. 2021. https://arxti:: http//aaxxivrgrr/a///////// abs/ 2110/217700000 07016
[52] Peter W Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th Annual Symposium on Foundations of Computer Science, 1994.
[53] Jaewoo So. Deep learning- based cryptanalysis of lightweight block ciphers. Security and Communication Networks, 2020.
[54] Shivin Srivastava and Ashutosh Bhatia. On the Learning Capabilities of Recurrent Neural Networks: A Cryptographic Perspective. In Proc. of ICBK, 2018.
[55] Jianlin Su, Yu Lu, Shengfeng Pan, Bo Wen, and Yunfeng Liu. Roformer: Enhanced transformer with rotary position embedding, 2021. https://arxiv..r owapsiiv..rrr./. abs/ 098644
[56] Andrew Trask, Felix Hill, Scott Reed, Jack Rae, Chris Dyer, and Phil Blunsom. Neural arithmetic logic units. 2018. https://arxiv: //tp:i////xivvee wwtp://g///aaaeaaae.o..ooeseeeea 1800 0008/000880088888888
13

---

[57] 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.
[58] Emily Wenger, Mingjie Chen, François Charton, and Kristin Lauter. Salsa: Attacking lattice cryptography with transformers. Proc. of NeurIPS, 2022.
[59] Mingyu Zong and Bhaskar Krishnamachari. Solving math word problems concerning systems of equations with GPT-3. In Proc. of AAAI, 2022.
14

---

A Appendix
A.1
Parameters
Table LWE, preprocessing, and training parameters. adaptive increase preprocessing parameters, we start with blocksize &n and LLL-delta ÖLLLI, and upgrade to 32 and 8LLL2 at later stage. Parameters base B and bucket size r are used to tokenize the numbers for transformer training.
log2
9
81
ÓLLL1
32
ÓLLL2
base B
bucket size
12
3329
35
0.99
40
1
417
14
11197
35
0.99
40
1
1400
256
42899
0.99
1
5363
18
222553
35
0.99
40
0.99
27820
16
20
842779
35
0.99
40
0.99
105348
64
21
1489513
30
0.96
40
0.99
186190
128
350
27
94056013
30
0.96
40
0.99
5878501
4096
512
41
2199023255531
18
0.93
22
0.96
137438953471
134217728
VERDE runs data preprocessing with the parameters shown in Table 9 in parallel using multiple CPUs. We fully parallelize when the time to process one matrix is greater than 24 hours-ee e.g.. for n = 350, log, 9 = 27, we used 5000 CPUs. Otherwise, we parallelize on fewer CPUs depending on the attack time allowed e.g., preprocessing is completed on 270 CPUs in less than 4 days for 72 = 256, log, q = 14, and on 990 CPUs less than 3 days for n 256, loga = 18.
In VERDE, the tokenization used by the transformer mirrors the strategy in $4 of 42 but uses smaller bases and larger bucket sizes r for better performance (Table 9, 10
42 Decreasing B
is further supported by Table T0 evaluated on low modulus data using VERDE'S preprocessing
(n = 256, log, 9 = 16). Full ternary secret recovery and partial Gaussian secret recovery both improve with smaller B 5363.
Table 10. Secret recovery for different bases. 256,, log, == 16. We show full ternary secret recovery and partial Gaussian secret recovery when using B 7150 and 5363 the datasets and secrets.
ternary
Gaussian
h
10
11
12
3
4
5
6
7150
2/10
0/10
1/10
0/10
1/10
5/10
6/10
1/10
1/10
B = 5363
2/10
0/10
2/10
0/10
2/10
5/10
6/10
1/10
3/10
A.2 More seeds for initialization
The ML attacks benefit from running multiple times with different seeds, or initializations, as was demonstrated in PICANTE 42 Section 6.4). More seeds improve both the success probability and the number of epochs required. Table II shows how binary secret recovery improves with more seeds, for different Hamming weights h when 256 and log, 4 12.
Table 11. Secret recovery with 1 seeds. n 256, logz 9 12, binary secrets. For I seed, epoch is the epoch secret recovery; For seeds (ran on same secrets as seed experiments), epoch is lowest epoch secret recovery among the 5 initializations for each secret.
h
3
4
5
recovery, 1 seed epoch
5/10
1/10
1/10
1/10
0,0,0,8.17
0
17.
13
recovery, 5 seeds epoch
7/10
3/10
1/10
2/10
0,0.0.7.7.8.17
0,5,5
4,7
Table 12 shows the results for ternary secrets on 512, log, y = 41, where we run 5 initializations for each secret. While most initializations partially recovered the secret, only few got full recovery within 20 epochs. Full recovery benefits from more initializations, especially for high h.
15

---

Table 12. Ternary secref recovery with initializations. n 512. '., recovery did not occur in - 20 epochs.
45
46
50
55
58
60
epoch of partial recovery
4,4,6,6,7
1,1,1,1,1
3,4,5,7,-
5,6,6,6,7
106,8.10
5,8,8,8,12
epoch of full recovery
10,-,,--
5,7,-,--
4.10,14.1,--
16,-.--
11.11,-8
A.3 Comparison with PICANTE
To demonstrate the power of the new preprocessing in SALSA VERDE, we run a set of experiments
on = 256, log2 q 23, where PICANTE also showed success. Using blocksize 3 40, each matrix is processed by VERDE in about 1.5 days; PICANTE took 2.2 days/matrix. VERDE achieves a reduction factor of 0.25, compared to 0.33 in PICANTE. As shown in Table T the difference in the preprocessing step is even more striking for lower q-
The highest h recovered by PICANTR was h 31 in 4 out of 20 experiments; VERDE recovered = 43. In Table [3] we see that for h = 26 31, VERDE significantly outperforms PICANTE in both the success rate and the number of epochs required. In other words, better preprocessing results in lower training time and better secret recovery.
Table 13. Epochs of secret recovery for PICANTE vs. VERDE. = 256 and logg = 23. '.' means secret not recovered. 5 secrets per h, except for PICANTE h 31 (20 secrets).
h
26
27
28
29
30
31
PICANTE
2,3,4.7.-
10.-,---
5, 0,0,0.1,2
5,9,11,,,
17.20.32,--
6.22.66.27 (out of 20 secrets) 1,2,3,4.-
VERDE
0,0,2.2,7
2,6,-.--
0,1.1.I.-
0,1,2.3,-
A.4
Distinguisher tested on reduced data outperforms random data
We compare the performance of running the distinguisher on the preprocessed data that were held out from the training set (Distæez) with running on random vectors (Distmma)) We run both set of experiments with the same model initialization seeds, and record success for the method(s) that recovers the secret at the earliest epoch. Table 14 indicates that DistaKz. performs better.
Table 14, Secret recovery by rumning the distinguisher on the random vectors and bkz preprocessed data. 25,, logg 9 23, on data processed using PICANTE'S approach.
27
28
29
30
31
DisIBKz
2/S
1/5
1/5
0/5
0/5
Distand
1/5
0/5
0/5
0/5
A.5 Dimension reduction techniques
Most of the entries in sparse secret are zero, prior work [5] has suggested the idea of randomly assuming a subset of the entries to be zero and removing them to reduce the dimension of the lattice problem. The assumption will be correct with some probability depending on the secret's sparsity. Here we explore an improvement on this strategy: we use the partially trained model to glean signal on which entries should be kicked out. We can either try to kick out zeros, which we call dimension reduction, or in the binary case, kick out 1s, which we call Hamming reduction, or combined.
This technique will be better than random when the model has begun to learn information about the bits, reflected in their relative rankings. Specifically, the ranking strategies described in 42 Section 4.3] are used to compute scores which estimate the likelihood of secret bits being 1. Once the model has started to learn, we can assume that the highest ranked bits will correspond to secret bits which are equal to 1, and the lowest ranked bits will correspond to zeros. So we use this information to reduce the dimension of the problem by kicking out low-ranked bits which we guess to be zero or high-ran ranker bits which we guess to be 1. Then, retrain model samples and hope to recover the secret. the original kicked out bits were correct and the model recovers the secret of the smaller dimensional problem, then we find the original secret.
the smaller dimensional
Dimension reduction. Since there are many more Os than 1s in sparse secrets, we can potentially reduce the dimension significantly. Once we remove the bits with low scores, we can simply re-run
16

---

training on the dataset with (a', b) where a' are the samples with the corresponding bits removed. If the indices have been identified incorrectly, then the reduction will fail. For n 256, log2 9 14. VERDE attempted 10 binary secrets with h 10 and did not recover the secret. Then we tried dimension reduction on these experiments and recovered one secret.
Hamming reduction. Kicking out 1s from the secret is particularly valuable, given the theoretical analysis of the VERDE in Section If nonzero bits are indeed ranked the top by the model, straightforward approach of kicking out the top-ranked bits and retraining on the smaller dimension and Hamming weight will likely yield improved secret recovery.
But in case some of the top-ranked bits are not equal to 1, we propose the following strategy. Suppose S is a small set of indices for bits with the highest scores. We construct the following problem: let s be s with bits in S flipped, and a' be a with a, negated for E S. Equivalently, for i E S, af = 04 and sy 1 8;- Then, the corresponding
b' = aaass
Σ 048;
Σ d.s
Σ 048;
-1a(1 --a(11 8:) = b Σ at- iES
iES
If more than half of the indices in S are 1, then s' has smaller Hamming weight, hence the instance (a', = Eies a4) is likely easier. If exactly half of the indices in S are then has the same as s, but the new instance (a', aa',bl b') will have different NoMod and may recoverable.
A.6 Attacking sparse secrets in larger dimensions
For sparse secrets even larger dimensions, we can apply our attack after using combinatorial techniques to exploit the sparsity of the secret. The approach would be to combine VERDE with the techniques from [5] 20] as follows: Randomly kick out & entries of the secret, assuming they are zero, which will be true with some probability. This reduces the LWE problem to smaller dimension where VERDE can recover the secret. The expected cost of the attack would be VERDE'S ss cost multiplied by 1/p, where y (== A is the probability that the assumption that the A entries are 0 is correct.
A.7 Comparison with lattice reduction/uSVP attacks
In this section we compare VERDE with classical lattice reduction attacks in two ways. The LWE Estimator [6] gives heuristic predicted running times for the best-known lattice reduction attacks. But even the authors of the LWE Estimator claim that the estimates are often wrong and unreliable. So compare VERDE to the Estimator results but also compare concrete running times in the case n = 256, achieved by implementing the uSVP lattice attacks ourselves, on the same machines where we run our ML-based attacks. Unfortunately, many attacks listed by the LWE Estimator lack practical/accessible implementations. and we lacked the time and resources to implement all of these and run comparisons. Thus, we focus our concrete comparisons on the uSVP attack, which the Estimator predicts to be the best method for larger n such as = 512. We leave comparison of VERDE against other lattice reduction attacks as important future work for the broader lattice community, as practical attack run- times are poorly understood, especially for small sparse secrets.
Table Concrete comparison VERDE and uSVP attacks for 256, binary secrets, varying and VERDE'S 's total attack time is the sum of preprocessing and training time (with recovery included). Preprocessing time assumes full parallelization, and training time is the number of epochs to recovery multiplied by epoch time (1.5 hours/epoch). fail means successful secret recovery for vSVP compare
LWE parameters
VERDE attack time Training
uSVP attack time (hrs)
log, !
h
Preprocessing (hrs)
Total (hrs)
12
8
1.5
epochs
4.5
fail
14
12
2.5
2-5 epochs
5.5-10
fail
16
14
8.0
epochs
11
fail
18
18
7.0
epochs
11.5
558
18
20
7.0
1-8 epochs
8,5-19
259
20
22
7.5
5 epochs
15
135-459
20
23
7.5
3-4 epochs
12-15
167-330
20
24
7.5
4 epochs
13.5
567
20
25
7.5
epochs
15
76- 401
17

---

Table 15 presents our concrete comparison between VERDE and the uSVP attack on binary secrets for n 256. To summarize the comparison, VERDE outperforms the uSVP attack in two senses: VERDE fully recovers sparse binary and temary secrets for and q in some cases where the uS attack does not succeed in several weeks or months using fplll BK7. 2.0 [19] with the required block size; and 2) in cases where we improve the uSVP implementation enough (see below) to run with the required large block size, we find that in all cases, VERDE recovers the secrets much faster.
Summarizing classical lattice reduction attacks. Table 16 gives the estimated heuristic cost and specifies the block size for attacking sparse binary and ternary secrets for 256, 350, 512 and various with the best known classical lattice reduction attack.
Table 16, Estimated cost of best classical attack (L.WE Estimator). For VERDE'S highest h, we run the LWEE Estimator and report the estimated cost and block size 3 for the best predicted attack.
binary secret
ternary secret
71
logg
h
best attack
rop
h
best attack
rop
B
12
8
dual mitm hybrid dual hybrid
24300
40
dual mitm hybrid
243.8
40
14
12
247.2
40
13
dual hybrid
247.7
41
256
16
14
dual_hybrit
2
40
16
dual hyal_hybrid
247.4
41
18
23
hdd_hybric
247.1
45
23
dual_hybrid
2
41
20
36
bdd
24.0
45
33
bdd
2
46
12
dual mitm hybrid. bdd__itm___a mitmmmybrid bdd
2884
dual_mitm_ __ybrrd
48.99
350
27
36
24.0
47
38
bdd, bdd_hybrid
24.1
43
512
63
usvp/bdd
22.9
40
60
usvp/bdd
242.9
40
Table 17. Estimated cost and block sizes of uSVP. Gaussian secrets with h nonzero entries.
256, log, q 16, 18, 20, for binary, ternary, and
binary rop
termary rop
Gaussian rop
loga
/
h
8
h
16
12
254.7
86
12
254.9
87
6
260.3
138
18
18
249.5
67
19
249.8
68
7
259.6
102
20
25
45.44
52
24
24..4
52
7
253.5
80
Table 17 gives the same information for the uSVP classical lattice reduction attack, focusing on 256 for some of the larger q and h where VERDE succeeds.
uSVP attack performance, binary secrets. For n = 256 and log2 = 20, we run the concrete uSVP attack using fplll BKZ 2.0 with Kannan's 's embedding and parameters (377 [6]). With block size 50 and 55, secrets are not recovered in 25 days, and block size 60 or larger cannot finish the first BKZ loop in days. We propose two improvements we rearrange the rows of the vSVP matrix as in VERDE; 2) we use the adaptive float type upgrade as in VERDE. In addition, after each BKZ loop, also the secret validation obtained from the shortest vector found so far, and terminate we get a secret match.
get these attacks to run faster and better: 1)
With rearranging the rows but without the adaptive float type upgrade, we have to use higher precision because otherwise the attack fails due to low precision after running for 23 hours. The attacks run quite slowly with high precision and did not recover secrets after 25 days, except in one case where binary secret with / = 22 was recovered with block size in 414 hours, roughly 17 days.
With rearranging the rows and the adaptive float type upgrade, we ran 256 and log, 20 with block size 50 55 for binary/temary secrets, and n 256 and log, 18 with block size 65 for binary/ternary secrets. See Table T8 for running times and h. For example, for log, secret with h = 25 was recovered in 280 hours, roughly 12 days, and for log, g = 18, a binary secret with h 20 was found in R 11 days. When the block size used is lower than predicted by the estimator (50 instead of 52 for log, g = and 65 instead of 67 for log, q = 18, see Table the uSVP attack succeeds in recovering only few secrets out of many which were tried.
20, a ternary
18

---

Table 18. uSVP concrete attack time, n 256, Upper: log, 9 = 20, lower: log, = 18. For each h, block size and secret distribution, we run 5 experiments on different secrets and show the secret recovery time (in hours). '
means no success in 25 days.
256, log2 9 20
blocksize
secret
h 22
23
24
binary
451, 531
50
ternary
261,
binary
135, 451,459 459
167, 323, 330
567
76, 280,
55
ternary
43, 241, 432
234, 296
226, 257, 337
280
n
256, log, 9 18
blocksize
secret
h 11
h 12
17
h 18
19
h 20
binary
32
558
259
65
ternary
324, 553
109
594
The concrete experiments allow us to validate to some extent the predictions of the Estimator in many cases, giving confidence in the comparison with VERDE. Running the uSVP attack with block size 70 or larger didn't finish the first BKZ loop in 3 days, so we expect longer attack time for Gaussian secrets and for binary and temary secrets with lower q.
Gaussian secrets. VERDE achieves partial Gaussian secret recovery for small h, reducing the secret recovery to lattice problem in tiny dimension (h). Because the preprocessing time and per epoch time does not vary with secret distribution, VERDE'S attack time on Gaussian secrets is comparable binary secrets (see Table 15 T9p. We note that preprocessing takes longer for log2 = 27 due to precision issues. This is an important observation because lattice problems supposed to be harder for smaller q. In contrast, with classical attacks, the Estimator predicts significantly larger block sizes required, and longer running times (Table than for binary secrets. VERDE compares favorably to classical attacks on Gaussian secrets, especially the problem is harder), e.g., VERDE recovers Gaussian secrets with h = 5 6 in 4.5 - 15 hours for n 256, log, q 12, where the cost of best classical attacks is predicted to be 291 rop.
350 and
small g (where
Table 19. VERDE'S performance on LWE problems with n = 256 and 350, Gaussian secrets, varying and h. Preprocessing time: hours process one matrix. Total attack time: sum of preprocessing time (assuming full parallelization) and training time (number of epochs multiplied by hours per epoch, see
LWE parameters
VERDE attack time
n
logg 9
Preprocessing (hrs)
Training
hrs/epoch
Total (hrs)
5-6
1.5
2-9 epochs
4.5-15
14
5-6
2.5
2-21 epochs
5.5-34
256
16
9
8.0
2 epochs
1.5
11
18
7.0
3 epachs epochs
11.5
10
7.5
21
16
1-5 epachs
18-24
350
1.6
10
216
2-13 epochs
219-237
Table 20. LWE Estimator: best classical attack on Gaussian secrets on various g. n 256 and 350. For VERDE'S highest h, we show the best classical attack. the attack cost (rop), and predicted block size 3 from the LWE Estimator.
72
log, q
best attack
rop
3
12
bdd / bdd hybrid
201.0
214
14
bdd / bdd hybrid
277.7
166
256
bdd / hdd_ hybrrd
287.1
128
18
9
bdd
207.7
93
20
10
bdd / bdd hybrid
201.9
21
bdd
285.2
120
350
27
10
bdd / hdd _
250.2
68
19


Reviews:
[{"review_id": "chHMWCC148", "reviewer": "Reviewer_wmYQ", "summary": "This paper continues a recent line of work on leveraging machine learning (specifically, transformers) for cryptanalysis. The focus is specifically on the learning with errors (LWE) problem. The LWE problem is one of the core problems in lattice-based cryptography, and the basis for many of the recently standardized post-quantum cryptographic systems. The paper targets one particular version of LWE (with *sparse* secret keys).\n\nThe (search) LWE problem is to learn a noisy linear function, where the noise is over a ring: given samples (A, s^T A + e mod q) for a secret vector s, random (wide) matrix A, and small (discrete) Gaussian noise e, recover the secret s. The variant of LWE considered here is where the secret s is sparse. While this is not the standard version of LWE, it is used as an optimization for some fully homomorphic encryption (FHE) schemes.\n\nCompared to previous approaches (Salsa and Picante), this paper describes generalizations to a ternary and (sparse) Gaussian error distributions as well as a better preprocessing step (responsible for generating more examples via the given LWE challenge, which is in turn used to train the transformer). The paper provides some empirical measurements showing that the attack is successful in recovering the secret for some small instances.", "questions": "As mentioned above, using a *sparse* Gaussian secret key distribution seems unusual for LWE? Do you have examples where this is used or preferred over a binary/ternary key distribution (sparse Gaussian secrets are not captured by reductions to worst-case lattice problems, and do not seem to confer better efficiency than just using binary/ternary keys).\n\nWhen you compare the running time of your attack to the estimated security level of the instances you consider, can you also report the running time in terms of the number of bit operations (or CPU cycles) for the attack? From Table 15, it looks like you assume full parallelization, so it is not clear how the running time translates to the actual amount of compute used. Does your algorithm suggest that the security level for small LWE instances (as determined by the LWE estimator) is much lower than currently reported? How big is this gap? I think analyzing this would require computing the actual amount of compute (taking into consideration the parallelism) used in the attack and not just a run time measurement.\n\nWhen you compare the effectiveness of your attack against known classical algorithms, are you comparing against the best state-of-the-art attacks (it seems the lattice estimator suggest different algorithms in Table 16)? Are the algorithms you compare against tuned for standard LWE instances (e.g., with uniform or Gaussian secret keys)? I would like to understand the extent to which this is an apples-to-apples comparison.\n\nOn a similar note, are you comparing against approaches with similar levels of compute? Your algorithm assumes full parallelization; does this apply to the previous algorithms you compare against?", "limitations": "I found the comparisons with other classical approaches to be one of the more interesting aspects of this work, and would have liked to see some of this discussion in the main body of the paper. It would be great if the paper could provide some more fine-grained information on the amount of compute needed for the ML-based approaches and what the implications these attacks have for improving our hardness estimates for LWE with sparse secret distributions.\n", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Studying and understanding the hardness of lattice assumptions is an important problem in cryptography, especially given the current move towards standardizing and implementing post-quantum cryptography. This paper improves upon an ML-based approach for understanding the hardness of certain LWE instances.\n\nWhile previous approaches considered the more restrictive setting of LWE with sparse binary secrets, this paper extends the analysis to support LWE instances with sparse ternary secrets. This is a more useful setting as this is a more common mode used in certain FHE implementations (though far from what I would consider a \"standard\" LWE instance). The idea is to first use the binary distinguisher approach from prior work (which focuses on identifying the zero vs. non-zero indices of the errors) and then applies a post-processing step that identifies whether two non-zero entries in the candidate secret are equal or not (to identify the set of coordinates that are 1 vs. -1).\n", "weaknesses": "I found the contributions in the paper to be somewhat incremental relative to the previous work. The main improvements seem to be better preprocessing relative to the previous Picante system. While I appreciate that there is a significant speed-up in the new approach for generating LWE samples from a small initial challenge, the core idea is very similar: resample followed by lattice reduction. A more refined application of lattice reduction compared to Picante yields the performance improvement.\n\nThe second feature that distinguishes this work from prior work is the extension to ternary and sparse Gaussian secret key distributions. The extension to ternary builds on the binary distinguisher approach of prior work and essentially add a post-processing distinguisher that decides whether two components are equal/unequal. This technique is very tailored to the ternary case, and it is not clear how general it is or whether this has implications on more standard LWE secret key distributions (e.g., uniformly random or (non-sparse) discrete Gaussian).\n\nFrom a cryptographic perspective, I view LWE with sparse binary/ternary secret keys to be a very risky assumption. The known reductions from LWE to worst-case lattice problems (e.g., gap shortest vector problem) apply only to LWE with uniform secrets (and also LWE with discrete Gaussian secrets). I do not see a solid basis for the hardness of LWE with very sparse binary/ternary secrets, except for the fact that we do not yet know how to break these assumptions. From this perspective, I am not sure if the results in the paper provide insight on the hardness of the standard LWE assumption where we have better evidence for hardness (and which is the basis of schemes in the NIST post-quantum standardization process).\n\nThe paper describes attacks on LWE with sparse Gaussian secrets, but this seems like an unusual choice. Normally, when we consider LWE with Gaussian secrets, there is no sparsity condition. Are there concrete settings where this version of the LWE assumption is used? The attack here seems to rely on identifying the non-zero entries (using the binary distinguisher approach from earlier) and then brute force guessing the values in the non-zero indices. This seems rather inefficient and unlikely to scale to even somewhat-dense solutions. The attacks in the paper only consider a very sparse regime, which again corresponds to a setting where I consider an attack to not be particularly surprising.\n\nFrom the machine learning perspective, I think the paper mostly relies on existing models and architectures as opposed to introducing new architectures tailored for cryptanalyzing LWE. I think this is a fine approach to take, albeit one with less novelty from a machine learning perspective.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**I found the contributions in the paper to be somewhat incremental relative to the previous work.**\n\n6 main contributions are listed in the introduction, none of which are incremental. Besides the new secret recovery technique for sparse binary, ternary, and small Gaussian secrets, and the improved data preprocessing techniques (40x faster and 20% more effective), Verde also includes:\n* Results for increased dimension n and reduced modulus q that outperform classical attacks, and achieve a new state-of-the-art on medium-to-hard LWE instances with small sparse secrets \n* NoMod, a framework for understanding the success of ML-based attacks\n* Theoretical analysis to explain successful recovery\n* A new encoder-only model architecture, with comparison to old architecture\n\n**The extension of secret recovery] technique is very tailored to the ternary case**\n\nWe believe that the new distinguisher can work with any small secret. Suppose secret coordinates can take $k$ different values, in dimension $n$, there are $k^n$ possible secrets. The new distinguisher clusters the $n$ secret positions into $k$ classes having the same secret value. For uniform small secrets, the number of possible secrets becomes $k!$. \n\nIf the secret distribution is not uniform, we can leverage the frequency estimates that the distinguisher provides for each class. For instance, for Gaussian or binomial secrets, where $$Prob(0) > Prob(1)=Prob(-1) > Prob(2)=Prob(-2) \\dots$$\n\nwe can associate the largest class to zero, the two next to $-1$ and $1$, &c. This results in $2^\\frac{k-1}{2}$ possible secrets. (Also see the last point from the discussion in our general rebuttal) \n\n**From a cryptographic perspective, I view LWE with sparse binary/ternary secret keys to be a very risky assumption.**\n\nWe agree that binary and sparse binary secrets are much weaker than random secrets and that the associated hardness assumption is suspicious.  Yet, they are desirable solutions from a practical point of view, because they run faster, are easier to implement, and allow bootstrapping in homomorphic encryption. For this reason, in the absence of concrete attacks such as the ones our paper suggests, practitioners will push ahead with implementations of cryptosystems based on these risky assumptions.  That is precisely why it is so important to develop attacks like Verde, so the practical vulnerabilities of such systems can be better understood. \n\n**using a sparse Gaussian secret key distribution seems unusual for LWE**\n\nThe NIST 2022 standardized schemes use a binomial secret distribution, very close to the Gaussian distribution with width 3, but not sparse.  The 2018 HomomorphicEncryption.org standard proposes both ternary secrets and Gaussian secret distribution with width ~3.  The HE standard does not propose sparse versions, but the community continues to push for sparse versions in the standard, to enable bootstrapping and performance improvements.  We study sparse secrets in our paper because that’s where our current techniques apply best, with the aim to extend to general binary, ternary, and Gaussian secrets in future work.  Sparse ternary secrets are explicitly proposed in several HE application papers, cited in our paper.\n\n**it looks like you assume full parallelization, so it is not clear how the running time translates to the actual amount of compute used.**\n\nIn table 15, parallelization only applies to preprocessing, and assumes that each $n\\times n$ matrix is reduced on one CPU core. The number of matrix lines needed for VERDE is $2$ million, and so for $n=256$ the number of cores is $2,000,000/256= 7813$. For $n=256$ and $\\log q > 16$, our attack only outperforms uSVP because we can trade compute for time during preprocessing and uSVP cannot. For smaller $q$, we could not recover the secret using uSVP. Also, we could recover secrets for $n=512$ and $h=63$., but know of no concrete uSVP attack that achieves such results.\n\nFor VERDE, estimating the number of cycles is made difficult by the training stage, which is performed on a GPU.  For uSVP, the LWE estimator gives estimates that can be compared to our preprocessing stage, but they are only estimates, not successful attacks, and it is hard to translate them into concrete running times for comparison. Comparing concrete attack time on the same machines, using the same implementation of BKZ, is the best we can achieve.\n\n**are you comparing against the best state-of-the-art attacks?**\n\nSee Appendix A.7 for a discussion of this exact point (lines 620-641, pages 17-18).  We introduce 3 improvements to existing uSVP implementations, to get them to run and allow for apples-to-apples comparison. We provide two benchmarks: \n1. Comparing to predictions from the LWE Estimator, \n2. Improving and running implementations of uSVP attacks to validate estimates from the Estimator and provide direct comparisons to our approach in the same hardware/software set-up.  (The estimator does not actually run successful attacks.) \n\n**Your algorithm assumes full parallelization; does this apply to the previous algorithms you compare against?**\n\nPICANTE uses full parallelization of the preprocessing step. SALSA is not comparable, because it operates without preprocessing, and on much smaller instances. For the preprocessing step, table 2 provides a comparison between PICANTE and VERDE preprocessing run on the same machines. For the training step, we are using similar architectures and GPUs as PICANTE (V100 with 32GB video memory). Levels of compute should be in the same ballpark.\n\n**I found the comparisons with other classical approaches to be one of the more interesting aspects of this work, and would have liked to see some of this discussion in the main body of the paper.**\n\nWe agree it would be better to include the comparison work in the main body of the paper, and we can provide more fine-grained info and move that into the main body if accepted.\n"}, {"review_id": "B2BHGMA0bb", "reviewer": "Reviewer_StdV", "summary": "The authors present VERDE, an improved ML based attack on the LWE problem, a source of mathematical hardness underpinning post-quantum cryptography schemes such as Homomorphic Encryption. Their method improves upon prior versions of this form of attack, SALSA and PICANTE, by improving the runtime characteristics of the preprocessing and the performance and generality of the secret recovery step. Additionally, their error analysis yields insights into the hardness of SALSA-style attacks on the LWE problem, revealing an avenue for potential improvement based on improving the distribution of the training data to increase the chance of success for such attacks.", "questions": "- Can slightly more detail be provided about full recovery in the Gaussian case? \"This is feasible via other methods\" leaves reader wondering whether identifying non-zero entities is in fact most of overall lift. A more detailed explanation for how to complete recovery in the gaussian case should be included, else claims that VERDE covers the gaussian case should be qualified elsewhere.\n\n- To strengthen the already decisive insight of the NoMod analysis, can anything be said analytically about the likelihood of a given permutation achieving a high NoMod percentage given the observation of failure on the initial un-permuted version? Working this analysis might reveal an avenue for further tuning of the permutation procedure to increase the success of this trick. Alternately, this could provide an avenue for robustness analysis of this attack under certain assumptions about the distributions of training data.", "limitations": "- Key limitation, as the author's state, is gap between the settings they can attack successfully, and the realistic parameter schemes in standardized PQC. However, this is not actually any failure of the authors, and they do in fact achieve results at more realistic settings than prior work.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- Introduces key performance improvements to the existing previous art by subtle but impactful modifications: reducing the complexity of the preprocessing matrix operations, and improving their floating point error tolerance.\n\n- Secret discovery procedure is improved by applying a simple (but not trivial) fact from machine learning - generalization to a shifted distribution is hard. Switching to verification on a held out set of preprocessed vectors. i.e. \"in-distribution\", yields improved performance.\n\n- Secret discovery procedure is extended to ternary secrets by taking a novel two step approach, where step one is similar to the binary secret recovery problem. (novelty is taken for granted, not very familiar with literature)\n\n- (Highlight) Error analysis yields NoMod, which allows them to first descriptively develop an explanation for different success rates as a function of modulus, but then further admits a potential improvement via attempting to increase the NoMod factor of a given training set by permutation.", "weaknesses": "- The encoder-only model architecture proposal empiricals are mixed, and theoretical or intuitive justification is missing. Would be useful to include training runtime differences in Table 8 or their own table, my sense is that epochs until success doesn't tell full story since training complexity for the two architectures is likely different. Claim that the encoder only model may generalize to larger n is not sufficiently supported by Table 8, could be omitted, or such discussions moved to future work section as more experimentation is necessary. \n\n- (Minor) Rationale for omission of other secret recovery techniques - direct, cross-attention - is not fully convincing. Latter could be included for the seq2seq architecture as they are proposing the encoder-only variant in this work, rather than adopting it as a baseline.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**The encoder-only model architecture proposal empiricals are mixed, and theoretical or intuitive justification is missing.**\n\nThe intuition for moving to encoder-only architectures is the fact that model output is only two-token long. This suggests that an autoregressive decoder is not needed, and simpler architectures are possible. \nAlso, decoder models such as GPT 3.5/4 are known to have difficulties to generate direct answers to certain --- sometimes even simple --- problems without generating chain of thoughts first. Our situation is analogous, since we are generating just one or two output tokens, so we want the transformer to have full thinking power before outputting the answer. Letting the transformer be encoder-only can be more directly tackling our LWE problem, by reducing the unnecessary components, and letting the transformer, in all layers, have more incentive to let all pairs of input tokens interact.\nAn additional potential benefit is the fact that encoder-only models have less parameters, and should be easier to train as dimension scales up.\n\nWe will consider moving the encoder-only discussion to the appendix, and reinforcing the sections on full secret recovery, and comparisons with classical attacks.\n\n**Rationale for omission of other secret recovery techniques - direct, cross-attention - is not fully convincing.**\n.\nThe main reason for abandoning direct secret recovery was that it almost never recovers secrets in large dimensions when preprocessing is used. We believe this is due to the requirement that the transformer correctly predicts b for values of a with only one non-zero coordinate. As dimension and modulus increase, these points get further from the training distribution, which includes no points with many small coordinates. Direct secret recovery therefore implies OOD generalization. The modified distinguisher used in VERDE, on the other hand, only assumes correct prediction around the training samples, i.e. in-domain generalization, a weaker requirement.\n\nOn average, we found that cross-attention performs as well as the modified distinguisher. We removed it to make the encoder-only architecture possible. We will clarify these points in the revised edition. \n\n**Can slightly more detail be provided about full recovery in the Gaussian case?**\n\nYes. See our general rebuttal, point 2\n\n**To strengthen the already decisive insight of the NoMod analysis, can anything be said analytically about the likelihood of a given permutation achieving a high NoMod percentage given the observation of failure on the initial un-permuted version? Working this analysis might reveal an avenue for further tuning of the permutation procedure to increase the success of this trick. Alternately, this could provide an avenue for robustness analysis of this attack under certain assumptions about the distributions of training data.**\n\nThank you for this insightful suggestion. Intuitively, a high NoMod happens when the ones in the secret correspond to the coordinates of **a** that were most reduced during preprocessing. We can compute column reduction from the preprocessed sample, and therefore classify the columns in two groups: “easy” (heavily reduced) and “hard” (less reduced). The NoMod analysis suggests that unrecoverable secrets have many ones in the hard columns. A good permutation would therefore exchange the hard columns with easy ones, in the hope that they contain less one bits after reductions. This could help reduce the number of permutations that need to be considered to recover the secret (an important point, since a new BKZ reduction  must be performed for each permutation considered). Note also that this supposes that we can predict (before or early during reduction)  which columns will be reduced. This is a matter for future work. \n\n**Key limitation, as the author's state, is gap between the settings they can attack successfully, and the realistic parameter schemes in standardized PQC. However, this is not actually any failure of the authors, and they do in fact achieve results at more realistic settings than prior work.**\n\nSee out general rebuttal, point 1\n"}, {"review_id": "A1XZSAedyf", "reviewer": "Reviewer_XtRr", "summary": "The authors propose an ML based attack scheme for the learning with errors post quantum cryptography scheme. Their proposed attack is able to recover sparse, binary, and ternary Gaussian secrets in a more efficient fashion than the Salsa and Picante schemes in prior work. ", "questions": "Please see my questions under Weaknesses.", "limitations": "The authors have stated the need for post quantum cryptography, and thus, the societal impact of breaking classical cryptography via Shor's algorithm. Their work contributes to the task of finding the best post quantum crypto scheme which does not depend on factoring large numbers into products of primes.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "I have to admit that I am not an expert in post quantum cryptography, nor I am familiar with previous literature. Therefore, I am not able to confidently appreciate the strengths of the paper with respect to prior work. I like the clarity of the presentation in most parts; the paper is written well and provides a decent introduction to the problem of learning with errors.", "weaknesses": "1. To me the purpose of the paper is not clear. The authors claim that they improve on previous schemes. But these schemes have already demonstrated that LWE is breakable and won't be used in practice anyway, so what is the novelty of the paper? This should be made clear in a better way.\n\n2. It seems that the difference to previous schemes is just a different matrix factorization in combination with techniques from [14] and [17], as explained in Section 2. I don't think that this contribution alone is sufficient for acceptance to NeuRIPS.\n\n3. The part of the paper related to learning is not well developed and presented as an afterthought, despite the choice of the architecture may significantly affect the performance. The proposed scheme leverages the same architecture as in previous works without giving any rationale why a transformer architecture is the best choice and why attention is necessarily required. It seems that in the LWE encoding the noise sequence is drawn iid from a Gaussian distribution, so I don't understand why the learning architecture needs to impose a Markovian structure.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**To me the purpose of the paper is not clear. The authors claim that they improve on previous schemes. But these schemes have already demonstrated that LWE is breakable and won't be used in practice anyway, so what is the novelty of the paper?**\n\nThe general context of this paper is the current standardization of LWE-based cryptosystems, as possible replacements for public key algorithms such as RSA which are vulnerable to Shor’s algorithm. In its strongest form (non-sparse secrets with coordinates uniformly sampled in [0,q)), LWE is not breakable. However, sparse secrets have been considered because they make computation faster, and binary secrets are desirable because they enable homomorphic encryption (HE): performing computations on encrypted data. As of today, one of the schemes proposed for HE involves sparse ternary secrets with dimension 1024 or more. Previous work (PICANTE) suggested that ML-based attacks can succeed for dimension up to 350 and binary secrets. The purpose of this paper is to scale these attacks, to recover larger dimensions (512), lower values of q, and ternary secrets. As such, it establishes a new state of the art on medium-to-hard LWE problems, with sparse binary or ternary secrets.\n\nSee also part 1 of our general rebuttal. We will clarify this in the introduction of the revised paper.\n\n**It seems that the difference to previous schemes is just a different matrix factorization in combination with techniques from [14] and [17], as explained in Section 2.**\n\nOur introduction lists 6 contributions. Together with the acceleration of preprocessing described in section 4, we make the other important contributions: \n* The two bit distinguisher discussed in section 3, which allows to recover new classes of sparse secrets: ternary, and small secrets (when extended with the techniques described in our reply to reviewers X and Y). We demonstrate that ternary secrets are as easy to recover as binary. \n* We provide a theoretical analysis of these techniques, in section 5 and 6. First, we explain (via the NoMod statistics) why some secrets are harder to recover than others. Then we discuss the impact of preprocessing on recovery, and how it scales with the Hamming weight.\n* We scale previous attacks to larger dimensions (512) and lower modulus (lg q=12), establishing a new SOTA (see discussion in section A.7)\n* We demonstrate that seq2seq architectures can be replaced by encoder-only models, without adversely affecting the performance of the attack.\n\n**The part of the paper related to learning is not well developed and presented as an afterthought, despite the choice of the architecture may significantly affect the performance. The proposed scheme leverages the same architecture as in previous works without giving any rationale why a transformer architecture is the best choice and why attention is necessarily required. It seems that in the LWE encoding the noise sequence is drawn iid from a Gaussian distribution, so I don't understand why the learning architecture needs to impose a Markovian structure.**\n\nWe believe that an attention-based encoder is necessary, because predicting $b=\\textbf a \\cdot •textbf s+e$ (with **s** an unknown vector) from **a**, a random vector, requires understanding how the different coordinates of **a** interact during the calculation of b. The authors of SALSA also mention the failure of MLP and LSTM. On the other hand, we agree that the auto-regressive decoder introduced in SALSA is not necessary, because the choice of a base larger than the square root of $q$ means that the model output only has two tokens. \n\nDecoder models such as GPT 3.5/4 are known to have difficulties to generate direct answers to certain --- sometimes even simple --- problems without generating chain of thoughts first. Our situation is analogous, since we are generating just one or two output tokens, so we want the transformer to have full thinking power before outputting the answer. Letting the transformer be encoder-only can be more directly tackling our LWE problem, by reducing the unnecessary components, and letting the transformer, in all layers, have more incentive to let all pairs of input tokens interact.This was the main driver for our investigation of encoder-only models. \n\nAn additional benefit of an encoder-only model is that it uses less parameters, which might help scaling to larger dimensions (and longer input sequences). We will clarify our reasons for introducing the encoder-only architecture. \n"}, {"review_id": "ZqvY6yAdmF", "reviewer": "Reviewer_j97t", "summary": "This paper considers the problem of adapting machine learning for the cryptanalysis of LWE --- an important cryptographically hard problem that forms the basis of several modern post-quantum cryptosystems. The LWE problem requires recovery of a secret \\bf{s} given many noisy inner products b = \\bf{a} \\cdot \\bf{s} + e mod q.  LWE is also an ideal candidate problem for cryptanalysis using ML techniques because of the linear structure in the computation. \n\nThe high-level approach is to train an ML model using samples {(\\bf{a}, b)}. Next, this trained model can predict a value close to \\bf{a} \\cdot \\bf{s}  mod q for new values of \\bf{a}.  Finally, this prediction can recover \\bf{s}. This approach was first considered in prior work Salsa/Picante. Salsa could only work for binary secrets with 3/4 non-zero entries. In contrast, Picante supplemented the above approach with some insights from lattice algorithms. Specifically, Picante showed that by appropriately using BKZ lattice reduction algorithm in preprocessing, they could attack binary secrets but with larger non-zero entries. \n\nHowever, a significant gap remains between the parameter choices these attacks can handle and those used in LWE-based cryptosystems. This paper makes progress in reducing this gap.", "questions": "- How do you quantify that your attacks are better than classical lattice reduction attacks? I missed the concrete performance comparison on the same. Could the performance boost be attributable to more optimizations/use of hardware specialized for ML tasks? \n- Several choices in the paper seem unexplained. For example, the authors on page 5 say that they use \\sigma = 3 and that FHE standards suggest \\sigma = 3.2. I understand the authors are using a \\sigma close to what is suggested, but why not use 3.2? ", "limitations": "- The improvements in the paper are still not significant enough to show that ML/transformers can help significantly improve the attacks against LWE. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "+ The paper makes progress on various strengths. \n+ The paper can beat state-of-the-art lattice attacks not using ML. This demonstrated that ML could play a crucial role in the pipeline for improvement on lattice attacks. \n+ I like the effort in trying to give a theoretical explanation of why the attacks only seem to work for working", "weaknesses": "- The paper is a bit dense and talks about various parameters. Having some text that helps provide a unifying framework from the various parameter choices the authors try to use will be helpful. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**The paper is a bit dense and talks about various parameters. Having some text that helps provide a unifying framework from the various parameter choices the authors try to use will be helpful.**\n\nWe agree. Section A.1 in the appendix provides some background on the LWE instances and preprocessing parameters, but we will complete it with the training parameters, have a more detailed discussion of parameter choices and add it to the main.\n\n**How do you quantify that your attacks are better than classical lattice reduction attacks?**\n\nThe comparisons are in the appendix, notably sections A.3 and A.7.\n\nTable 15 shows that, for dimension 256, when run on the same machines, and using the same lattice reduction library, our techniques, once parallelized, run faster than classical uSVP attacks. For larger dimensions, we were not able to successfully run uSVP attacks (e.g. they never terminated), whereas we could recover secrets using our techniques. Estimates of the time needed for classical reduction attacks, for n=350 and 512, are in table 16 and 18. Finally we provide comparisons for gaussian secrets in tables 19 and 20. \n\nFinally, for dimensions up to 350,  some comparisons with classical attacks were included in PICANTE, and we prove (in section A.3 of the appendix) that we are better than PICANTE.\n\n**Several choices in the paper seem unexplained. For example, the authors on page 5 say that they use $\\sigma = 3$ and that FHE standards suggest $\\sigma = 3.2$. I understand the authors are using a $\\sigma$ close to what is suggested, but why not use 3.2?**\n\n$\\sigma=3$ was used in SALSA and PICANTE, which are the main baselines we use for comparison. We agree that a choice of $3.2$ would have been preferable. Still, we believe that the small difference in error variance has little impact on our results (especially since the preprocessing step amplifies error).\n\n**The improvements in the paper are still not significant enough to show that ML/transformers can help significantly improve the attacks against LWE.**\n\nSee point 1 of our general rebuttal. We believe that VERDE establishes a new state of the art on medium to hard LWE instances with sparse binary and ternary secrets (which are considered for standardization). Also, table 15 in appendix A.7 indicates that we outperform classical uSVP attacks.\n\n"}, {"review_id": "iKhe0SJXIE", "reviewer": "Reviewer_heZ1", "summary": "This paper introduces a novel ML attack that has the capability to recover sparse binary, ternary, and small Gaussian secrets. The proposed approach exhibits effectiveness in attacking LWE systems with larger dimensions and smaller moduli, while requiring less preprocessing time.", "questions": "Please refer to the weaknesses section.", "limitations": "Please refer to the weaknesses section.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written.\n2. The SALSA VERDE achieves a harder attack with larger dimensions and smaller moduli, which makes the attack more practical on LWE-based systems.\n4. The improved preprocessing method significantly speeds up the attack process, improving its efficiency.\n5. The authors provide a theoretical explanation for the performance of the attack, adding to its overall understanding.", "weaknesses": "1. It would be beneficial to include an explanation or insights regarding the reasons why full recovery of Gaussian secrets is infeasible.\n\n2. More ablation experiments and comparisons should be conducted to showcase the individual contributions and benefits of each proposed enhancement.\n\n3. Regarding the model architecture, additional results or explanations are necessary to justify the replacement of the positional embedding method and beam search, especially when the performances are similar.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**It would be beneficial to include an explanation or insights regarding the reasons why full recovery of Gaussian secrets is infeasible.**\n\nFull recovery of Gaussian secrets is feasible. Point 2 of our general rebuttal describes three possible approaches. We will include these in the revised version of the paper.\n\n**More ablation experiments and comparisons should be conducted to showcase the individual contributions and benefits of each proposed enhancement.**\n\nSuch results already exist, but they are scattered throughout the paper. In particular, the impact of new preprocessing techniques is presented in table 2. The impact of improved preprocessing reduction on secret recovery is presented in table 5. The impact of the new distinguisher is in Table 14 of the appendix,  the effect of the ternary distinguisher is discussed in section 3, and that of the encoder only model in table 8. We will streamline these results, and add a synthesis in the discussion of the revised paper.\n\n**Regarding the model architecture, additional results or explanations are necessary to justify the replacement of the positional embedding method and beam search, especially when the performances are similar.**\n\nWe agree that additional work is needed on the encoder-only approach. We found it interesting to report that such architectures can succeed: so far, all previous papers used seq2seq transformers.\n\n\n"}]

Author rebuttal:
We thank the reviewers for their comments and suggestions. In this general rebuttal, we address two questions that were mentioned in several reviews: how this research impacts the security of LWE, and how to perform full secret recovery of Gaussian secrets.


## 1- General context for VERDE and how it impacts LWE
**(Reviewers wmYQ, XtRr, j97t)**

With respect to problem complexity, instances of cryptographic problems like LWE fall broadly into three buckets:
* Easy: solvable via exhaustive search
* Medium to hard: requiring significant to unrealistic resources to solve
* Standardized: believed secure

SALSA Verde attacks **medium-to-hard** LWE problems (parameterized by dimension $n$, Hamming weight $h$, modulus $q$) and outperforms State-Of-The-Art (SOTA) attacks for LWE with small sparse secrets. Verde is not attacking toy problems (like SALSA did), nor is Verde attacking the NIST standard directly. Rather, Verde provides improved attacks using tools from AI, improving our understanding of the security of proposed LWE-based cryptosystems.

For example, Verde recovers secrets when dimension $n=512$ and Hamming Weight $h=63$ with modulus $q$, $\log q= 41$ (more than $2^{270}$ possible binary secrets; brute force attacks are impossible). In this setting, SOTA attacks (e.g. uSVP) did not succeed for $n=512$, but for smaller dimensions, $n=256$ and $n=350$, we provide extensive comparisons in Appendix A.7 showing Verde’s  speed-up over SOTA.  Thus, Verde is the new SOTA for attacking **medium-to-hard** LWE lattice problems with sparse binary secrets. 

We will clarify this in the introduction and add comparison with brute force attacks.


## 2. Full Gaussian secret recovery
**(Reviewers StdV, heZ1)**

Three different techniques can be used for the full recovery of Gaussian secrets.

First, we can use the non-zero secret bit recovery techniques described in the paper to discover the $h$ non-zero coordinates of **s** ($i_1,\dots  i_h$ henceforth). When computing $b=\textbf a\cdot \textbf s+e$, all other coordinates of **a** have no impact (they are multiplied by zero in the dot product). Therefore, we can reduce the problem to an equivalent LWE instance of dimension $h$: replacing **a** by $\textbf a_{red} = (a_{i_1}, \dots a_{i_h})$, **s** by $\textbf s' =( s_{i_1}, \dots s_{i_h})$ and observing that $b = \textbf a_{red}\cdot \textbf s’ +e$. The reduced problem becomes non sparse, and has larger error, but if the dimension $h$ is low (i.e.is the secret is sparse enough) , we can recover **s’** (and therefore **s**) using classical lattice reduction attacks.

Second, we can adapt the ternary attack to the Gaussian case. For small Gaussian secrets, the values of non-zero secret bits follow a Gaussian distribution with a standard deviation of $3$. This means that $99.7$% of non-zero secret bits take values between $-9$ and $9$. For the values of $h$ considered in this paper, we may safely assume that all secret bits are in $[-9,9]$. The two-bit distinguisher, introduced for ternary secrets, allows us to classify all secret positions into $k<<n$ groups of bits, which share a common secret value (i.e. zero "bits", 1 "bits", -1 "bits", 2 "bits" ...). In the sparse case, this allows to recover the $0$ class (which will be the largest group). Then, we can either: 
* if $k$ is small, enumerate and test all possible secrets (there are $\frac{18!}{(18-k)!}$ of them)
* assign $-1$ and $1$ to the two largest remaining classes ($2$ possible choices), then $-2$ and $2$ to the next, etc… and test the corresponding $2^{\frac{k-1}{2}}$ secrets
* mix the two previous approaches: guess the bits with smallest absolute value from their frequencies, and enumerate on the smallest ones.

Using these techniques, we build a short list of possible secrets, that can be tested on LWE data using the methods presented in section 3, lines 158 et seq. 

Third, we can improve the ternary distinguisher to distinguish secret coordinates of opposite signs. The ternary distinguisher can tell whether two secret values are equal by swapping two positions of **a** ($a_i$ and $a_j$), and comparing the model predictions at $\textbf a(\dots a_i \dots a_j \dots)$ and $\textbf a’(\dots a_j \dots a_i \dots...)$. If the corresponding secret bits, $s_i$ and $s_j$ are equal, the prediction of **a** and **a’** should be equal, or very close. Now consider **a”**$(\dots -a_j \dots  -a_i \dots)$. Model predictions for **a** and **a”** should be close if the corresponding secret values are opposite ($s_i =  - s_j$). Coupled with the ternary distinguisher, this can help classify all the $k-1$ values into $\frac{k-1}{2}$ pairs, and improve recovery. 

We will add a discussion of full Gaussian secret recovery in the revised version of the paper.


Meta-review: This paper proposes new machine learning algorithms for solving LWE type problems.
The paper focuses on LWE instances with sparse or small secrets and gives improved techniques for solving those.
As noted by some of the reviewers, it is not quite clear how generalizable the techniques are, or whether the considered LWE problems are really the most relevant in practice.
But ML-based cryptanalysis of number-theoretic problems is a fairly under-explored problem, so I think it is good to see more work towards this direction (even if it currently does not impact the parameter choices for practical schemes).
Decision: Accept (poster)