Salsa Fresca: Angular Embeddings and Pre-Training for ML Attacks on Learning With Errors
Authors: Samuel Stevens
Emily Wenger
Cathy Yuanchen Li
Niklas Nolte
Eshika Saxena
Francois Charton
Kristin E. Lauter
Venue: Accepted by TMLR ()

Abstract: Learning with Errors (LWE) is a hard math problem underlying recently standardized post-quantum cryptography (PQC) systems for key exchange and digital signatures. Prior work proposed new machine learning (ML)-based attacks on LWE problems with small, sparse secrets, but these attacks require millions of LWE samples to train on and take days to recover secrets. We propose three key methods---better preprocessing, angular embeddings and model pre-training---to improve these attacks, speeding up preprocessing by $25\times$ and improving model sample efficiency by $10\times$. We demonstrate for the first time that pre-training improves and reduces the cost of ML attacks on LWE. Our architecture improvements enable scaling to larger-dimension LWE problems: this work is the first instance of ML attacks recovering sparse binary secrets in dimension $n=1024$, the smallest dimension used in practice for homomorphic encryption applications of LWE where sparse binary secrets are proposed, albeit for larger modulus $q$. Our ML-based approach is the only attack which has successfully recovered secrets for these parameters.

Published in Transactions on Machine Learning Research (04/2025)
Salsa Fresca: Angular Embeddings and Pre- Training for ML Attacks on Learning With Errors
Samuel Stevens The Ohio State University
stevens. @osu. edu
Emily Wenger Duke University
emily. wengyeewenrrrduuue.oommm edu
Cathy Yuanchen Li University of Chicago
wwanchen@uchicago.oo
Niklas Nolte Meta AI Research
notte@meta.com
Eshika Saxena Meta AT Research
eshika@metto. com
François Charton Meta AI Research
fcharton@meta.coom
Kristin E. Lauter Meta AT Research
kloute@@meta.com com
Reviewed OpenReview: https: openrevveee....eee.. net/ forum? id wddd55955gg
Abstract
Learning with Errors (LWE) is hard math problem underlying recently standardized post- quantum cryptography (PQC) systems for key exchange and digital signatures (Chen et al. 2022). Prior work (Wenger et al. 2022 Li et al. 2023a b proposed new machine learning (MT.)-based attacks on TWE problems with small, sparse secrets, but these attacks require millions of LWE samples train on and take days to recover secrets. We propose three key methods-better preprocessing, angular embeddings and model pre-training- these attacks, speeding up preprocessing by 25x and improving model sample efficiency by 10x. We demonstrate for the first time that pre-training improves and reduces the cost of ML attacks on LWE. Our architecture improvements enable scaling to larger-dimension LWE problems: this work is the first instance of ML attacks recovering sparse binary secrets in dimension n = 1024, the smallest dimension used in practice for homomorphic encryption applications of LWE where sparse binary secrets are proposed Lauter et al. (2011), albeit for larger modulus q. The ML--baed approach is the only attack which has successfully recovered secrets for these parameters.
improve
1 Introduction
Lattice-based cryptography was recently standardized by the US National Institute of Standards and Technology (NIST) in the 5-year post-quantum cryplography (PQC) competition (Chen et al. 2022). Lattice- based schemes are believed to resistant to attacks by both classical and quantum computers. Given their importance for the future of information security, verifying the security of these schemes critical, especially when special parameter choices are made such binary, ternary, and/ or sparse secrets. Both the NIST standardized schemes and homomorphic encryption (HE) rely the hardness of the "Learning

---

Published in Transactions on Machine Learning Research (04/2025)
Table I: Best attack results for LWE problems in dimensions n (higher harder), modulus q (lower is harder). and Hamming weights h (higher is harder). We recover secrets for 1024 for the first time in ML-based LWE attacks and reduce total attack time for n = 512, 512, 4 41 to 50 hours (with full CPU parallelization).
LWE (A, b)
preprocessing time (hrs/CPU/matrix)
training time (hrs)
total time (hrs)
n
log29
highest h
matrices needed
512
41
44
1955
13.1
36.9
50.0
768
35
1302
12.4
14.8
27.2
1024
50
13
977
26.0
47.4
73.4
with Errors" (Regev 2005 LWE) problem. NIST schemes standardize small secrets (binomial), and the HE standard includes binary and ternary secrets Albrecht et al. (2021); Bossuat et al. (2024), with sparse versions used in practice Cheon al. (2017).
The LWE problem is defined as follows: in dimension n, the secret E 2 is a vector of length with integer entries modulo q. Let A Σ be a uniformly random matrix with m rows, and E 2 an error vector sampled from narrow Gaussian Xe (see 2 for notation summary). The goal is to find s given A and b, where b = A S te mod q. The hardness of this problem depends on the parameter choices: n, q, and the secret and error distributions. Many HE implementations use sparse, small secrets to improve efficiency and functionality, where all but entries of s are zero (so h is the Hamming weight s). The non-zero elements have a limited range of values: for binary secrets, and -1 for ternary secrets. Sparse binary or ternary secrets allow for fast computations, since they replace the n-dimensional scalar product A by sums. However, binary and ternary secrets might be less secure Bai & Galbraith (2014).
Most attacks on LWE rely on lattice reduction techniques, such as LLL or BKZ Lenstra et al. 1982 Schnorr (1987): : Chen & Nguyen (2011). which recover by finding short vectors a lattice constructed from A, b and g Ajtai (1996); Chen el al. (2020). BKZ attacks scale poorly to large dimension and small moduli q Albrecht et al. (2015).
ML-based attacks LWE were first proposed in Wenger et al. (2022 Li et al. (023a b), inspired by viewing LWE as linear regression problem on discrete torus. These attacks train small transformer models (Vawwani et al. 2017) to extract secret from cavesdropped LWE samples (A, b), using lattice- reduction for preprocessing. Although Li et al.] solves medium-to-hene small sparse LWE instances, for example, dimension n = 512, the approach is bottlenecked by preprocessing and larger dimensions used in HE schemes, such as 1024. In this work, we introduce several improvements to Li et al.Js MI. attack, enabling secret recovery for harder LWE problems in less time. Our main contributions are:
25x faster pre-processing using Flatter (Ryan & Heninger
2023 and interleaving with polish-
ing (Charton et al. 2024 and BKZ2.0 CChn & Nguyen 2011
(ec $3
An encoder-only transformer architecture, coupled with an angular embedding for model inputs. This reduces the model's logical and computational complexity and halves the input sequence length, significantly improving model performance (see
The first use of pre-training for LWE to improve sample efficiency for ML attacks, further reducing preprocessing cost by 10x (see
Overall, these improvements in both preprocessing and modeling allow us to recover secrets for harder instances of LWE, i.e. higher dimension and lower modulus in less time and with fewer computing resources. A summary our main results can found in Table [ Although no prior LWE attack has been shown to succoed experimentally at the parameter scttings we consider, g we contextualize our performance by presenting theoretical estimates for other LWE attacks. The ML-baaedd approach the only attack which has successfully recovered secrets for these parameters.
2

---

Published in Transactions on Machine Learning Research (04/2025)
Table 2: Notation used in this work.
Symnbll Description
(A, b)
LWE matrix/vector pair, with - +
(a, b)
An LWE vector/integer pair, Modulus the LWE problem.
of (A, b).
The (unknown) true secret.
h
Number of nonzero bits in secret.
Error vector, drawn from distribution X Standard deviation of the Problem dimension (the dimension and s)
de
7
The total number of LWE samples available
m
# LWE samples each subset during reduction
Candidate secret, not necessarily correct
R
Matrix computed to reduce the coordinates of A.
P
Preprocessing reduction factor; ratio dAA)
2 Context and Attack Overview
Wenger et al. (0022) and Li et al. 2023a demonstrated the feasibility of MT--based attacks LWF. Li et al. (2023a) has? 2 parts: data preprocessing using lattice reduction techniques; 2) model training interleaved with regular calls to a secret recovery routine, using a trained model as cryptographic distinguisher to guess the secret. In this section we provide an overview of ML-based attacks in prior work.
2.1 Attack Part 1: LWE data preprocessing
The attack assumes t 4n initial LWE samples (a, b) (rows of (A,b)) with the same secret are available. Sampling m of the 4n initial samples without replacement, matrices A E 2 Zm with vectors b E 2 are constructed.
The preprocessing step strives to reduce the norm of the rows of A by applying a carefully selected integer linear operator R. Because R linear with integer entries, the transformed pairs (R.,, Rb) mod are also LWE pairs with the same secret, albeit larger error. In practice, is found by performing lattice reduction
the (m + n) (m + 12) matrix A 0 q A
and finding linear operators [C R such that the
Im
norms of [C R A= [ R.A + q C. are small. This achieves reduction of the norms of the entries of RA mod q, but also increases the error in the calculation of Rb RA s Re, making secret recovery more difficult. Although ML models can learn from noisy dala, too much noise will make the distribution of Rb uniform on [0, q) and inhibit learning. The parameter w controls the trade-off between norm reduction and error increase. Reduction strength measured by p a(A) deviations of the rows of R.A and A.
c(RA) where denotes the mean of the standard
Li et al. 2023a use BKZ Schnorr (1987) for lattice reduction Li al. (2023b) improves the reduction time by 45x via modified definition of the A matrix and by interleaving BKZ2.0 Chen & Nguyen (011 and
polish Charton et al. (2024) (sce Appendix Fh.
This preprocessing step produces many (RA, Rb) pairs that can be used to train models. Individual rows of RA and associated elements of Rb, denoted as reduced LWE samples (Ra, Rb) with some abuse of notation, are used for model training. Both the subsampling of m samples from the original LWE samples and the reduction step are done repcatedly and in parallel to produce million reduced LWE samples, providing the data needed to train the model.
3

---

Published in Transactions on Machine Learning Research (04/2025)
2.2 Attack Part 2: Model training and secret recovery
With 4 million reduced LWE samples (Ra, Rb), transformer is trained to predict Rb from Ra. For simplicity, and without loss of generality, we will say the transformer learns to predict b from a. Li et al. train encoder-decoder transformers (Vaswani et al.) 2017) with shared layers (Dehghani et al. 2019). Inputs and outputs consist of integers that are split into two tokens per integer by representing them in a large base B = & with & ~ 10 and binning the lower digit to keep the vocabulary small as increases. Training is supervised and minimizes a cross-cntropy loss.
The key intuition behind MT-attacks on LWE is that to predict b from a, the model must have learned the secret We extract the secret from the model by comparing model predictions for two vectors and a' which only differ on one entry. We expect the difference between the model's predictions for and V to be small (of the same maguitude as the error) if the corresponding bit of s is zero, and large if it is non-zero. Repeating the process on all n positions yields a guess for the secret.
For ternary secrets, Li et al. (2023b) introduce two-bit distinguisher, which leverages the fact that if socret bits s and 8y have the same value, adding a constant K to inputs both these indices should induce similar predictions. Thus, if u, is the 8th basis vector and K is random integer, we expect model predictions for + Ku; and + Ku to be the same if 8; 8j. After using this pairwise method to determine whether the non-zero secret bits have the same value, Li et al.) classify them into two groups. With only two ways to assign 1 and -1 to the groups of non-zero secret. bits, this produces two secret guesses.
Wenger et al. (2022) test a secret guess s* by computing the residuals b- - a s* over the 4n initial LWE sample. s" is correct, the standard deviation of the residuals will be close to x de- Otherwise, it will be close to the standard deviation of a uniform distribution over Zyj: g/v12.
For given dimension, modulus and secret Hamminng weight, the performance of ML attacks vary from one secret. to the next. Li et al. (2023b) observe that the difficulty of recovering given secret s from set of reduced LWE samples (a, b) depends on the distribution of the scalar products a s. If a large proportion of these products remain in the interval (-q/2, q/2) (assuming centering) even without a modulo operation, the problem is similar enough to linear regression that the ML. attack will usually recover the secret. Li et al. introduce the statistic NoMod: the proportion of scalar products in the training set having this property. They demonstrate that large NoMod strongly correlates with likely secret recoveries for the ML-attack.
2.3 Improving upon prior work
Li et. al. (2023b) recover binary and ternary secrets, for n = 512 and log, 41 LWE problems with Hamming weight S 63, in 36 days, using 4,000 CPUs and 1 GPU ((i et al. 2023b Table 1)). Most of the computing resources are needed in the preprocessing stage: reducing one m n A matrix takes 35 days, and 4000 matrices must be reduced to build training set of million examples. This suggests two directions for improving the attack performance. First, introdueing fast alternatives to BKZ2. .0 may shorten the time required to reduce one matrix. Second, minimizing the number of samples needed to train the models would reduce the number of CPUs needed for the preprocessing stage.
Another crucial goal is scaling to larger dimensions n. The smallest standardized dimension in the HE Standard Albrecht et al. [2021) h is n = 1024. At present, ML attacks are limited by their preprocessing time and the length of the inpul sequences. The atlention mechanism used in transformers is quadratic in the sequence length, and Li et al. (2023b) encodes n dimensional inputs with 2n tokens. More efficient encoding would cut down transformer processing speed and memory consumption quadratically.
2.4 Parameters and settings in our work
Before presenting our innovations and results, we brielly discuss the LWE settings considered in our work. LWE problems are parameterized by the modulus q, the secret dimension n, the secret distribution Xs (sparse binary Shaary/ternary /ternary) and the hamming weight h of the secret (the number of non-zero entries). Table 3 spocifies the LWE problem settings we attack. Proposals for LWE parameter settings in homomorphic encryption suggest using 1024 with sparse secrets (as low h 64), albeit with smaller q than we consider Curtis
4

---

Published in Transactions on Machine Learning Research (04/2025)
Table 3: LWE parameters attacked in work. For all settings, we attack both binary and lernary secret distribu- lions Xo.
Table Reduction performance and median time to reduce one matrix for Li et al. (2023b) work. Li et al. method fails for n > 512 on our compute cluster.
CPU hours matrix
7
logg 9
h
71
log2 9
Li et al. (2023b)
Ours
512
41
50 < h < 70
512
41
0.41
= 350
13.1
768
35
5 <
< 15
768
35
0.71
N/A
12.4
1024
50
S 15
1024
50
0.70
N/A
26.0
Table 5: Tradeoff between reduction quality and error is controlled by w. n = 1024, log, = 50.
1
3
5
7
10
13
P
0.685
0.688
0.688
0.694
0.698
0.706
R l//
0.341
0.170
0.118
0.106
0.075
0.068
& Player 2019); Albrecht (2017). Thus, is important to show that ML attacks can work in practice for dimension n 1024 if hope attack sparse secrets in real-world settings. Similar to developing attacks reduced-round AES, we develop attacks LWE problems with larger q and lower h than in practice. Future work should further improve q and h towards concrete homomorphic encryption proposals.
The LWE error distribution remains the same throughout our work: rounded Gaussian with o = 3 (follow- ing Albrecht et al.] (2021)). Table 10 in Appendix E contains all experimental settings, including values for the moduli 4, preprocessing settings, and model training settings.
3 Data Preprocessing
Prior work primarily used BKZ2.0 0 in the preprocessing/lattie reduction step. While effective, BKZ2. 0 is slow for large values of n. We found that for n = 1024 matrices it could not finish single loop in 3 days on an Intel Xeon Gold 6230 CPU, eventually timing out.
Our preprocessing pipeline. Our improved preprocessing incorporates recently developed (at the time of writing) reduction algorithm Flatter Ryan & Heninger (2023 which promiscs similar reduction guarantees to LLL with much-reduced compute time, allowing to preprocess LWE matrices in dimension up to n 1024. We interleave Flatter and BKZ2. 0 and switch between them after 3 loops of one results in Ap< < -0.001. Following Li et al. (2023b), we run polish after each Flatter and BKZ2. 0 loop concludes. We initialize our Flatter and BKZ2. 0 runs with block size 18 and a = 0.04, which provided the best empirical trade-off between time and reduction quality (see Appendix F for additional details), and make reduction parameters stricter as reduction progresses up block size 22 for BKZ2. O and a 0.025 for Flatter.
Preprocessing performance. Table records the reduction achieved for each (n, q) pair and the time required, compared with Li et al. (2023b). Rocall that p mcasures the reduction the standard deviation of A₁ relative to its original uniform random distribution; lower is better. Standard deviation strongly correlates with vector norms, but for consistency with Li al. (2023b) we use standard deviation.
We record reduction time as CPU hours matrix, the amount of time it takes algorithm to reduce LWE matrix using one CPU. We parallelize our reduction across many CPUs. For = 512, our methods improve reduction time by factor of 25, and scale easily to n = 1024 problems. Overall, we find that Flatter improves the time (and consequently resources required) for preprocessing, but does not improve the overall reduction quality.
5

---

Published in Transactions on Machine Learning Research (04/2025)
impus/Ouigut
(c, y) E IR?
Not trainable
Trainable perameters
Hidden representations
MaxPool
y1
V/2
y3
Un
MLP
Sel- Attention
T2
W
a
a2
a3
any
Figure Encoder-only transformer ($4.1) proposed angular embedding.
with angular embedding, See 4.2 for an explanation of our
Error penalty w. We run reduction experiments with penalty w 10. Table 5 demonstrates the tradeoff between reduction quality and reduction error, as measured by ||R]]/q, for 1024, log2 9 50 problems. Empirically, find that |R|l/g 0.09 is sufficiently low to recover secrets from LWE problems with e (00,3)))
Experimental setup. In practice, we do not preprocess a different set of 4n (a, b) pairs for each secret recovery experiment because preprocessing so expensive. Instead, we use a single of preprocessod Ra rows combined with arbitrary secret. produce different. (Ra, Rb) pairs for training. We first generate secret and calculate b A + for the original 4n pairs. Then, produced by preprocessing to A and b to produce many (Ra, Rb) pairs with reduced norm. This technique enables analyzing attack performance across many dimensions (varying h, model parameters, etc.) in a reasonable amount of time. Preprocessing a new dataset for each experiment would make evaluation at scale near-impossible.
apply the many different R
4 Model Architecture
Previous MT. attacks on LWE use a encoder-decoder transformer (Vaswani et al. 2017). bidirectional encoder processes the input and an auto-regressive decoder generates the output. Integers both input and output sequences were tokenized as two digits in large base smaller than g. We propose simpler and faster encoder-only model and introduce angular embedding for integers modulo q.
4.1 Encoder-only model
Encoder-dccoder models were originally introduced for machine translation, because their outputs can be longer than their inputs. However, they are complex and slow at inference, because the decoder must run once for each output token. For IWE, outputs (one integer) are always shorter than inputs (a vector of n

---

Published in Transactions on Machine Learning Research (04/2025)
integers).
Li et al. (2023b) observe that an encoder-only model, 4-layer bidirectional transformer based DeBERTa He et al., 2020). achieves comparable performance with their encoder-decoder model.
Here, we experiment with simpler encoder-only models without DeBERTa's disentangled attention mechanism with 2 to 8 layers. Outputs are max-pooled across the sequence dimension, decoded by a linear layer for each output digit (Figure 1
We minimize a cross-entropy loss. This simpler architecture improves training speed
by 25%.
4.2 Angular embedding
Most transformers process sequences of tokens from a fixed vocabulary, encoded in IR by a learned embodding. Typical vocabulary sizes vary from 32K in Llama2 (Tourron et al. 2023). to 256K in Jurassic-1 (Lieber et al. 2021). The larger the vocabulary, the more data needed to learn the embeddings. LWE inputs and outputs are integers from z. For > 512 and q 2 2a5; encoding integers with one token creates a too-large vocabulary. To avoid this, Li et al. (2023a b) encode integers with two tokens by representing them in base B = with small l and binning the low digit so the overall vocabulary has < 10K tokens.
This approach has two limitations. First, input sequences are 2n tokens long, which slows training as n grows, because transformers' attention mechanism scales quadratically in sequence length. Second, beyond sequence length concerns, vocabulary-based embeddings do not introduce any inductive bias: models must learn how to embed tokens solely from the data. However, LWE is structured problem (modular arithmetic over 2n); and prior work has demonstrated that translormers can learn this st structure. Liu el. al. (2022) showed that transformers trained on modular arithmetic problems learn vocabulary embeddings that miroor the circle-like structure present in 2g (e.g. the embedding for 0 is close to that of and g - 1) late in training, a phenomenon known as "grokking" Power et al. (2022 Gromov (2023).
To address these shortcomings, we introduce an angular embedding which strives better represent the problem's 's modular structure in embedding space, while encoding integers with only one token. An integer a Zg is first converted to angle by the transformation + 2 q' and then to the point (0n
E R² All input integers (in 2,)) are therefore represented as points on the 2-dimensional unit circle, which is then embedded
cllipse in Rd, via a learned lincar projection W.. This improves the sequence length: individual elements of a each only need one token, so E 2 uses tokens instead of 2n tokens as in prior work. Our approach also adds inductive bias: because we linearly project from the unit circle in R to the transformer's embedding space Rdd, the embeddings for the different elements in Z, are arranged in a ellipsis, preserving the circle-like structure of integers mod q.
Model outputs, obtained by max-pooling the encoder output sequence, are decoded as points in IR. by another linear projection Wo. The training loss is the L2 distance between the model prediction and the point representing b the unit circle.
4.3 Experiments
Here, we compare our new architecture with previous work, and assess its performance on larger instances of LWE (n 768 and 1024). All comparisons with prior work are performed on 512 and log2 q 41 for binary and ternary secrets, using the same pre-processing techniques as Li ct al. (2023b).
we compare our encoder-only model (with and without the angular embedding) with the encoder-decoder and the DeBERTa models from Li et al. (023bb) The encoder-only and encoder-decoder models are trained for 72 hours one 32GB V100 GPU.
Encoder-only models vs prior designs. In Table G
The DeBERTa model, which requires more computing resources, is trained for 72 hours on four 32GB V100 GPUs Our encoder-only model, using the same vocabulary embedding as prior work, processes samples 25% faster than the encoder-decoder architecture and 3x faster than the DeBERTa architecture. With the angular embedding, training is 2.4x faster, because input soquences are half as long, so attention calculations are accelerated. Our models also outperform prior designs on secret recovery: previous models recover binary secrets with Hamming weight 63 and ternary secrets with Hamming weight 60. Encoder-only models with
7

---

Published in Transactions on Machine Learning Research (04/2025)
Table 6: Best recovery results for binary and ternary secrets on various model architectures (n= = 512,
logg 4 = 11). Encoder-Decoder and DeBERTa models and recovery results from Li et al. (2023b); ; we benchmark DeBERTA samples/sec on our hardware. Encoder (Vocab.) uses prior work's vocabulary embedding. Encoder
(Angular) is presented in Section 4.2
Samples/ Sec
Largest Binary h Ternary h
Largest
Architecture
Encoder- Decoder
200
63
58
Encoder (DeBERTa)
83
Encoder (Vocab.)
256
63
66
Encoder (Angular)
610
66
Vocabulary embedding
Angular embedding
Figure 2: Encoder-only (angular embedding) perfor- mance for varying # of layers and embedding dimen- sions (n 512, log, q 41, binary X+). Samples per second quantifies training speed; " "Recovered" = % recovered out of 100 secrets with h from 49-67; "Hours"= mean hours to recovery.
Succeed?
15
Tiue
Count
10
10
0.4 0.5
0.6
0.4
0.5
0.6
Layers Emb. Dim. Params Samples/S Recovered Hours
Proportion of NoMod in training data
Proportion of NoMod training
1.3M
23%
18.9
4.1M
19.6
Count # successes (orange) and failures (blue) for various NoMod for vocabulary- vs. angular embedding schemes. 512, log. 41, h 57-67.
Figure 3:
14.6M
25%
26.2
6
512
20.9M
465
25%
28.1
8
512
27.2M
356
24%
30.3
angular embedding recover binary and ternary secrets with Hamming weights up to 66. G.. in the Appendix gives detailed results.
Impact of model size. Table compares encoder-only models of different sizes (using angular embeddings). All models are run for up to 72 hours one 32GB V100 GPU on = 512, log, q 41. We observe that larger models yield little benefit in terms of secret recovery rate, and small models are significantly faster (both in terms of training and recovery). Additional results are in Appendix G.2 We use 4 layers with embedding dimension 512 for later experiments because it recovers the most secrets (25%) the fastest.
Embedding ablation. Next, compare our new angular embedding scheme to the vocabulary embeddings. The better embedding should recover both more secrets and more difficult ones (as measured by Hamming weight and NoMod; see 2.2 for a description of NoMod). To mcasure this, we run attacks on identical datasets, 512, log, g = 41, h = 57-67 with 10 unique secrets per h. One set of models uses the angular embedding, while the other uses the vocabulary embedding from Li et al. (023b)).
To chock if angular embodding outperforms vocabulary embodding. we measure the attacked secrets' NoMod. We expect the better embedding to recover secrets with lower NoMod and higher Hammingg weights (e.g. harder secrets). As Figure 3 and Table 6 demonstrate, this is indeed the case. Angular embeddings recover secrets with N 56 vs. 63 for vocabulary embedding (see Table 29 in Appendix for raw numbers). Furthermore, angular embedding models recover more secrets than those with vocabulary embeddings (16 vs. 2) and succeed on higher (66 vs. 63). We conclude that an angular embedding is superior to a vocabulary embedding because it recovers harder secrets.
proposed architecture improvements to scale The long input sequence length in prior work made scaling attacks to n 2 512 difficult, due to both memory footprint and slow model processing speed. In contrast, our more efficient model and angular embedding scheme ($4.) 44. enable us to attack n = 768 and n = 1024 secrets. Table shows that we can recover up to h = 9 for both n = 768 and n 1024 settings, with < 24 hours of training on a single 32GB V100 GPU. In $5.1 we show recovery of h 13 for n 1024 using more samplo-efficient training strategy. We run identical experiments using prior work's encoder-decoder model, but fail to recover any secrets with 512 in the same computational budget.
Scaling Finally,
8

---

Published in Transactions on Machine Learning Research (04/2025)
Table Secret recovery time for larger dimensions n with encoder-only model with 4 layers, embedding dimension of 512 and angular embedding. We only report the training hours (on V100 GPU) for successuul secret recoveries, out of 10 secrets per h value.
Samples/ Sec
Hours to recovery for different h values
π
log, !
h 5
h =
h = 9
h = 11
768
35
355
3.1, 18.6, 18.9 1.6, 6.2, 7.6, 8.8, 34.0, 41.4, 43.7
9.1, 21.6, 24.9 4.6, 7.4, 13.5, 16.7
15.9, 27.7
1024
50
256
21.3
Table 8: # Training samples needed to recover secrets without pre-training. (n = 512, log, = 41, binary secrets). We report # of secrets recovered among h 30-45 (10 secrets for each h), the highest recovered, and the average atlack time among secrets recovered with 1M, 3M and 4M training samples.
Training samples
Total #
Best
Mean Hours
300K
1
32
30.3
1M
18
28.0 + 11.6
3M
21
44
26.5 + 10.5
4M
22
25.3 8.9
Our proposed model improvements lead the first successful ML attack that scales to real-world values of proposed real-world cases for LWF--bsed cryptosystems recommend using dimensions 768 and = 1024 Avanzi et al. [021]; Albrecht et al. [2021]: 1; Curtis & Player 2019 although they also recommend smaller q and harder secret distributions.
5 Training Methods
The final limitation address is the 4 million preprocessed LWE samples for model training. Recall that each training sample is row of reduced LWE matrix RA E _ so producing 4 million training samples requires reducing 1,000,000 LWE matrices. Even with the preprocessing improvements highlighted in $3 m+n
for 1024, this means preprocessing between 2000 and 4500 matrices at the cost of 26 hours per CPT per matrix. To further reduce total attack time, propose training with fewer samples and pre- training models.
5.1 Training with Fewer Samples
We first consider simply reducing training dataset size and seeing if the attack succeeds. Li et al. always use 4M training examples. To test if this many is needed for secret recovery, we subsample datasets of size N [100K, 300K, 1M, 3M] from the original 4M examples preprocessed via the techniques in $ We train models to attack LWE problems n = 512, loga q = 41 with binary secrets and h 30-45. Each attack is given 3 days on a single V100 32GB GPU.
Table 8 shows that attack still succeeds, when only 300K samples are used. We recover approximately the same number of secrets with 1M samples with 4M, and both setlings achieve the same best h. Using 1M rather than 4M training samples reduces our preprocessing time by 75%. We run similar experiments for n = 768 and n = 1024, and find that we can recover up to 13 secrets for n = 1024 with only 1M training samples. Those results are Tables to 20 in Appendix H.1
5.2 Model Pre- Trainini
To further improve sample efficiency, we introduce the first use pro-training in LWE. Pro-training models
has improved sample efficiency in language (Devlin et al. 2019 Brown et al. 2020 and vision (Kolesnikov et al. 20200; we hypothesize similar improvements for LWE. We frame secret recovery as downstream
We bound the number of reduced matrices needed because rows reduction matrices R discarded after preprocessing. Between and + nonzero rows R. are kept, we reduce between 4,000,000 and 4,000,000 matrices. m++
m

---

Published in Transactions on Machine Learning Research (04/2025)
300K Samples
1M Samples
3M Samples
4M Samples
100
Mean Hours
50
0 80K 240K
440K
80K 240K 440K
0 80K 240K
440K
0 80K 240K
440K
Pretraining Steps
Pretraining Steps
Pretraining Steps
Pretraining Steps
Figure How pre-training affects mean hours secret recovery for different training dataset sizes. (n 512, log, q 41, binary secrets).
task and pre-train a transformer to improve sample efficiency when recovering new secrets, further reducing preprocessing costs.
Formally, attacker would like to pre-train model parameterized by 0 on samples {(a', such that the pre-trained parameters 0 are better-than-randon initialization for recovering a secret from new samples {(a,b) b)}. Although pre-training to get H* may require significant compute, l can initialize models for many different secret recoveries, amortizing the initial cost.
Pre-training setup. First, generate and reduce new dataset of 4 million Ra' samples with which we prettrinn& a model. The 0'-initialized model will then train on the (Ra, Ró) samples used in $5.1 leading to a fair comparison between a randomly-initializz model and a l -niiniiialized model. Pre-training on the truc atlack datasel is unfair and unrealistic, since we assume the altacker will train 0" before acquiring the real LWE samples they wish to attack.
The pro-trained weights 8" should be good initialization for recovering many different secrets. Thus, we use many different secrets with the 4M rows Ra'. In typical recovery, have 4M rows Ra and 4M targets Rb. In the pre-training setting, however, generate 150 different secrets so that each Ra' has 150 different possible targets. So the model can distinguish targets, we introduce 150 special vocabulary tokens ta one for each secret 8,. We concatenate the appropriate token t,, to row Ra' paired with Rò' = Ra' S; + e. Thus, from 4M rows Ra', we produce 600M triplets (Ra', te. RB'). The model learns to predict R!' from a row Ra' and an integer token t.,
We hypot that including many Ra', Rb' pairs produced from different secrets will induce strong generalization capabilities. When train the 0*-initialized model on new data with unseen secret s, we indicate that there is new secret by adding a new token to to the model vocabulary that serves the same function as la above. We randomly initialize the new token embedding, but initialize the remaining model parameters with those of 6*. Then we train and extract secrets as in 2.
Experiments. For pre-training data, 4n LWE (a, samples. We use binary and ternary secrets with Hamming weights from 30 to 45, with 5 different secrets for each weight, for a total of 150 secrets and 600M (Ra', L,, RD') triplets for pre-training. We pre-train an encoder-only transformer with angular embeddings for days on 8x 32GB V100 GPUs with a global batch size of 1200. The model sees 528M total examples, less than one epoch. We do not run the distinguisher step during pro-training because we are not interested in recovering these sccrets.
4M Ra' rows reduced to p 0.41, generated from
set of
We the weights 0* as the initialization and repeat 55.1 experiments. We three different checkpoints from pre-training as 0* to evaluate the effect of different pre-training amounts: 80K, 240K and 440K pre-training steps.
Results. Figure demonstrates that pre-training improves sample efficiency during secret recovery. We record the minimum number of samples required to recover each secret for each checkpoint. Then we average these minimums among secrets recovered by all checkpoints (including the randomly initialized model) fairly compare them. We find that 80K steps improves sample efficiency, dropping from 1.7M to 409K mean samples roquired. However, further pre-training docs not further improve sample efficiency.
315, is embedded using learned vocabulary.
10

---

Published in Transactions on Machine Learning Research (04/2025)
Recall that using fewer samples harms recovery speed (see Ta- ble 8 Figure T shows trends for recovery speed for pre-trained and randomly initialized models for different numbers of training samples. We find that any pre-training slows down recovery, but further pre-training might minimize this slowdown. Appendix has complete results.
Training Samples Required
4M-
Doseline Protrained
3M
2M
[ 440K
1M
BOK
240K
Pretraining Steps
6 Comparison to Other Attacks
Figure 5: Mean minimum number of samples needed to recover binary se- crets as function of # pre-training steps. (n = 512, log, 9 = 41, binary se- crets).
It is difficult, to compare against other attacks because few of the known LWE attacks have been implemented at scale and have code available, and no prior work has demonstrated successful LWE attack performance for the (large) dimensions we consider. One umpublished work Ducas et al. (2023) provides code and claims to outperform Salsa Verde Li et al. (2023b), but in fact does not, and does not even recover secrets dimension n 512. We compare against this publicly available codo and find that it does not recover any secrets for the parameters we attack.
In addition, we also follow common practice in the lattice community and compare against the LWE Estimator Albrecht et al. (2015 public Github repository commonly used to provide theoretical estimales of LWE attack performance. However, the authors note that it has not been peer reviewed NIST (2023).
Furthermore, it is inaccurate in several instances Chen et al. (0220:: Cheon et al. (019)) Ducas & Pulles
2023 and does not actually implement allacks.
We present concrete results using code from Ducas et al. (0233) in Table 9 and the Estimator's predicted (2023)'s ss code ran for weeks on our LWE parameter best attack for our paramcters in Table ! Ducas et al.
sets, but never succeeded. Thus, we report "_" for that allack. In the estimalor results, the ROP metric refers loosely to the number of operations needed to run the attack, which does not casily translate to time measurements, making it a crude estimate for runtime. For example, for (Z/qZ) ring operations, one should multiply by the cost of a multiplication modulo 9, naively (log q)², or for ciphertext operations one should multiply by the cost of polynomial multiplications modulo q; etc. We omit space requirements which may make implementation of some of the theoretical attacks impossible for these large dimensions.
Table 9: Comparison to other claimed attacks. Estimates from Albrecht et al. 2015)) given in terms of ROP- = estimated number of required operations for attack. Space requirements not included here.
LWE setting (n, q, hi)
Estimator Results Albrecht et al. (2015)
Ducas et al. 2023
Attack Name
ROP
Time (sec)
(512, 41, 44) (768, 35, 9)
Bounded Distance Decoding (BDD) Liu & Nguyen
2013
242.8
BDD Meet-in-the-middae Hybrid Howgrave-Giran
2007
246.
(1024, 50, 13)
BDD Meel-in-thh-middle Hybrid Nowgrave-Grahan
2007
248.1
7 Discussion & Future Work
Our contributions are spread across multiple fronts:
faster preprocessing (25x fewer CPU hours), simpler architecture (25% more samples/sec), better token embeddings (2.4x faster training) and the first use of pre- training for LWE (10x fewer samples). Our efforts lead to 250x fewer CPU hours spent preprocessing and 3x more samples/see for for 512, loga 4 = 41 LWE problems, and lead to the first ML attack on LWE for = 768 and n = 1024. Of note is that our contributions compose well; rarely in machine learning research are optimizations across multiple fronts truly independent. A hypothetical 2x speedup via data filtering and 3x speedup from an improved optimization algorithm is unlikely to combine to a 6x speedup. In contrast, our optimizations do compose well.
Muiee//rtttin coe Ct htt.://eeeeeiiieettaeaaaaaeeaa wwwps//////////////eeeeaeeeeeeee Wtwpaa/ww////aa--a/a00 LVB brge://gittib..cc con /hy aatteeaattt commit 0owe79ca
11

---

Published in Transactions on Machine Learning Research (04/2025)
Although have made substantial progress in pushing the boundaries of machine learning- based attacks TWE, much future work remains in both building on this pre-training work and improving models' capacity to learn modular arithmetic.
8 Limitations
Our work still does not attack concrete proposed LWE parameters (for example, the HE Standard Albrecht (et al. (2021) proposes 1024, log2 29 with non-sparse secrets for an equivalent 128-bit security level). We are primarily limited in two directions. First, wow effectively lattice reduction methods reduce samples. Our work integrates and leverages the latest developments in lattice reduction to improve the number of samples with scalar products s that lie in (-2. 2): this property is referred to as NoMod in $2.2 and prior work (Li et al. 2023b). Second, we are limited by the ability of our neural network (currently a bidirectional encoder) to learn from samples that do not satisfy this NoMod property. While prior work has demonstrated
that transformers can learn modular arithmetic for = (Liu et al. 2022). current architectures struggle with larger values of n.
Furthermore, while pre-training improves sample efficiency, it does not lead to improvements when recovering secrets with 3M or more reduced samples. While disappointing, this not surprising: the "pre-train/finee /fneetueeie" paradigm primarily improves over "train-from-see "rommsccracc" in small-data regimes. Future work, instead of improving recovery speed with millions of samples, should focus on further improving sample efficiency 100K lewer.
Acknowledgments
We thank Mark Tygert for his always insightful comments and Mohamed Malhou for running experiments.
References
Ezal Ahmadzadeh, Hyunil Kim, Ongee Jeong, and Inkyu Moon. A Novel Dynamic Attack Classical Ciphers Using Attention- Based LSTM Racoder-Decodee Model. IEEE Access, 2021.
Miklós Ajtai. Generating hard instances of lattice problems. In Proc. of the ACM symposium on Theory of Computing, 1996.
Mohammed M Alani. Neuro-cryptanalysis of DES and triple-DEES. In Proc. of NeurIPS, 2012.
Martin Albrecht, Melissa Chase, Hao Chen, et al. Homomorphic encryption standard. In Protecting Privacy through Homomorphic Encryption, pp. 31-62. 2021. httpp://epprnt.. iacr. 2tgg/209/939
Martin R. Albrecht. On dual lattice attacks against small-secret LWE and parameter choices in HElib and SEAL. In Proc. of EUROCRYPT, 2017. ISBN 978-3-319-566146;;
Martin R. Albrecht, Rachel Player, and Sam Scott. On the concrete hardness of learning with errors. Journal of Mathematical Cryptology, 9(3):169 203, 2015.
Martin R Albrecht, Florian Göpfert, Fernando Virdia, and Thomas Wunderer. Revisiting the expected cost solving usvp and applications to lwe. In Proc. of ASIACRYPT, 2017.
Nada Aldarrab and Jonathan May. Can sequence-to-ssqueene models crack substitution ciphers? arXiv preprint arXiv:2012.15229, 2020.
Roberto Avanzi, Joppe Bos, Téo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Peter Schwabe, Gregor Seiler, and Damien Stehlé. CRYSTALS-Kyber (version 3.02) Submission to round of the NIST post-quantum project. 2021. Available at
Seunggeun Back and Kwangjo Kim. Recent advances of neural attacks against block ciphers. In Proc. of SCTS, 2020.
12

---

Published in Transactions on Machine Learning Research (04/2025)
Shi Bai and Steven D. Galbraith. Lattice Decoding Attacks on Binary LWE. In Information Security and Privacy, 2014.
Adrien Benamira, David Gerault, Thomas Peyrin, and Quan Quan Tan. deeper look at machine learning- based cryptanalysis. In Proc. of Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2021.
Jean-Philippe Bossuat, Rosario Cammarota, Jung Hee Cheon, Πlaraa Chillotti, Benjamin R Curtis, Wei Dai, Huijing Gong, Erin Hales, Duhyeong Kim, Bryan Kumara, et al. Security guidelines for implementing homomorphic encryption. Cryptology ePrint. Archive, 2024.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Proc. of NeurIPS, 2020.
François Charton. Linear algebra with transformers. Transactions in Machine Learning Research, 2022.
François Charton, Kristin Lauter, Cathy Li, and Mark Tygert. An efficient algorithm for integer lattice reduction. SIAM Journal on Matrix Analysis and Applications, 45(1), 2024.
François Charton. Can transformers learn the greatest common divisor? Siii::2308.15944 2024.
Hao Chen, Lynn Chua, Kristin Lauter, and Yongsoo Song. On the Concrete Security of LWE with Small Secret. Cryptology ePrint Archive, Paper 2020/539, 2020. URL https://eprrntt. iacr org/2020/539
Lily Chen, Dustin Moody, Yi-Kai Liu, et al. PQC Standardization Process:
Announcing Four Candidates to be Standardized, Plus Fourth Round Candidates. US Department of Commerce, NIST, 2022. https 7/crcc www.e.iinttti.... Balsstt.goo/eeew//22//eeee candidates to- be--be-see standardized- and roduru---
Yi Chen and Hongbo Yu. Bridging Machine Learning and Cryptanalysis via EDLCT. Cryptology ePrint Archive, 2021. https://eprint. waw.epriiitiitrr....eee..eeeeeee www.:iiiirror........cco. 2rg/2021/75
Yuanmi Chen and Phong Q. Nguyen. BKZ 2.0: Better Lattice Security Estimates. In Proc. of ASIACRYPT, 2011.
Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song. Homomorphic encryption for arithmetic of approximate numbers. In Proc. of ASIACRYPT, 2017.
Jung Hee Cheon, Minki Hhan, Seungwan Hong, and Yongha Son. A Hybrid of Dual and Meet-in-the- tnddh--ddddellee Attack on Sparse and Ternary Secret LWE. TEEE Access, 2019.
Benjamin R. Curtis and Rachel Player.
On the feasibility and impact of standardising sparse-secret LWE parameter sets for homomorphic encryption. In Proc. of the ACM Workshop on Encrypted Computing & Applied Homomorphic Cryptography, 2019.
Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. Universal transformers. In Proc. of ICLR, 2019.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova, BERT: Pre-training of deep bidirectional
transformers for language understanding. In Proceedings of the Conference of the North American Chapter
of the Association for Computational Linguistics, 2019. URL httpps//aaclanthology org/N19-1423
Elena Dubrova, Kalle Ngo, and Joel Gärtner. Breaking a fifth-order masked implementation of crystals-kyber by copy-paste. Cryptology cPrint Archive, 2022. https://eprint: www.:iiar.rr.ooo.... orgg/222/1713
Léo Ducas and Ludo N Pulles. Does the dual-sieve attack on learning with errors even work? In Annual International Cryptology Conference, pp. 37-69. Springer, 2023.
Leo Ducas, Eamonn Postlethwaite, and Jana Sotakova. SALSA Verde vs. The Actual State of the Art, 2023. https://crypto. iacr. ottp://////mmmrrrppp222///raaapp
13

---

Published in Transactions on Machine Learning Research (04/2025)
Nouha Dziri, Ximing Lu, Mclanie Sclar, Xiang Lorraine Li, et al. Faith and fate: Limits of transformers compositionality. arXiv preprint 2XXi:23355188544 2023.
Aron Gohr. Improving attacks on round-reduced speck32/66 64 using deep learning. In Proc. of Annual International Cryptology Conference, 2019.
Sergij V Goncharov. Using fuzzy bits and neural networks to partially invert few rounds of some cryptographic hash functions. arXiv preprint arXiv:1901.0243s 2019.
Sam Greydanus. Learning the enigma with recurrent neural networks. arXiv preprint Xivi S05iv:1708.07500 170.007576
2017.
Kaden Griffith and Jugal Kalita. Solving Arithmetic Word Problems with Transformers and Preprocessing of Problem Text. arXiv preprint arXiv:2106.0000 00893, 2021.
Andrey Gromov. Grokking modular arithmetic. arXiv preprint mrXi::3301026679 2023.
Pengcheng He, Xiaodong Liu, Jianfeng Gao, and Weizhu Chen. Deberta: Decoding-enhanced bert with disentangled attention. arXiv preprint arXiv:2006.06644, 2020.
Nick Grahra. A hybrid lattico-roduction and tidddle attack against ntru. In Proc. of CRYPTO. Springer, 2007.
Lukasz Kaiser and Ilya Sutskever. Neural GPUs learn algorithms. aiviv preprint arXiv:1511.0822. 2013.
Nal Kalchbrenner, Ivo Danihelka, and Alex Graves. Grid long short-term memory. arXiv preprint arxiv:1507.0133 2015.
Hayato Kimura, Keita Emura, Takanori Isobe, Ryoma Ito, Kazuto Ogawa, and Toshihiro Ohigashi. Output Prediction Attacks on SPN Block Ciphers using Deep Learning. Cryptology ePrint Archive, 2021. URL
Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai, Joan Puigcerver, Jessica Yung, Sylvain Gelly, and Neil Houlsby. Big transfer (bit): General visual representation learning. In Proc. of ECCV, 2020.
Guillaume Lample and François Charton. Deep learning for symbolic mathematics. In Proc. of ICLR, 2020.
Kristin Lauter, Michael Naehrig, and Vinod Vaikuntanathan. Can homomorphic encryption be practical? Proccedings of the 3rd ACM workshop Cloud computing security workshop, pp. 113-124, 2011.
Nayoung Lec, Kartik Srcenivasan, Jason D. Lee, Kangwook Lee, and Dimitris Papailiopoulos. Teaching arithmetic to small transformers. arXiv preprint arXiv:2307.03381 2023.
H.W. Lenstra, A.K. Lenstra, and L. Lovász. Factoring polynomials with rational coofficients. Mathematische Annalen, 101:515-534, 1982.
Cathy Yuanchen Li, Jana Sotáková, Emily Wenger, Mohamed Malhou, Evrard Garcelon, François Charton, and Kristin Lauter. Salsa Picante: A Machine Learning Attack on LWE with Binary Secrets. In Proc. of ACM CCS, 2023a.
Cathy Yuanchen Li, Emily Wenger, Zeyuan Allen-Zhu, Francois Charton, and Kristin E Lanter. SALSA VERDE: machine learning attack on LWE with sparse small secrets. In Proc. of NeurlPS, 2023b.
Opher Lieber, Or Sharir, Barak Lenz, and Yoav Shoham. Jurassic-1: Technical details and evaluation. White Paper. AI21 Labs, 1:9, 2021.
Mingjie Liu and Phong Q Nguyen. Solving BDD by Enumeration: An Update. In Ed Dawson (ed.), Topics in Cryptology CT-RSSA 2013, 2013.
Ziming Liu, Ouail Kitouni, Niklas S Nolte, Eric Michaud, Max Tegmark, and Mike Williams. Towards understanding grokking: An effective theory of representation learning. Proc. of NeurIPS, 2022.
14

---

Published in Transactions on Machine Learning Research (04/2025)
Yuanliang Meng and Anna Rumshisky. Solving math word problems with double-decoder transformer. arXiv preprint arXiv:1908. 10924, 2019.
Daniele Micciancio and Panagiotis Voulgaris. Faster exponential time algorithms for the shortest vector problem. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms,, 2010.
NIST. FAQ on Kyber512.
2023.
https://csrc.nist nist...........oomm..o....t.et.e htt.://wt....o/sc/c///////////ta
post ceett-qunntummcaee acrythographh/bbouumtttt///eeeee watpaaatttaaaaaaaaaeeeeea 512-FAQ. pdf
Rodrigo Nogueira, Zhiying Jiang, and Jimmy Lin. Investigating the limitations of transformers with simple arithmetic tasks. arXiv preprint arXiv:2102.13013 2021.
Theodoros Palamas. Investigating the ability of neural networks learn simple modular arithmetic. 2017. https://project-archiie archijeeeetrrciiieeeeeee.eeeeeee inf ed. ac http///c/220172290mmsspcppsp prooj-pfff
Stanislas Polu and 1lya Sutskever. Generative language modeling for automated theorem proving. arXiv preprint arXiv:2009.0330: 2020.
Alethea Power, Yuri Burda, Harri Edwards, Igor Babuschkin, and Vedant Misra. Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets. arXiv preprint arXiv:2201.021 2022.
Oded Regev. On Lattices, Learning with Errors, Random Linear Codes, and Cryptography. In Proc. of the ACM Symposium Theory of Computing, 2005.
Keegan Ryan and Nadia Heninger. Fast practical lattice reduction through iterated compression. Cryptology ePrint Archive, 2023. URL https://eprintt iacr. org/2023/237 pdf
Claus-Peter Schnorr. A hierarchy of polynomial time lattice basis reduction algorithhs Theoretical Computer Science, 1987. URL http:://ww..scdeeecddrr.......
Kai- Yeung Siu and Vwani Roychowdhury. Optimal depth neural networks for multiplication and related problems. In Proc. of NeurIPS, 1992.
Jacwoo So. Deep learning- baaning-basod cryptanalysis of lightweight block ciphers. Socurity and Communication Networks, 2020.
Shivin Srivastava and Ashutosh Bhatia. On the Learning Capabilities of Recurrent Ncural Networks: A Cryptographic Perspective. In Proc. of ICBK, 2018.
The FPLLL development leam. fplll, lattice reduction library, Version: 5.4.4. Available al https sgittub..com/fpl1/fpp11] 2023.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.09288 2023.
Ashish Vaswani, Noam Shazeer, Niki Parmar, et al. Attention all you need. In Proc, of NeurIPS, 2017.
Emily Wenger, Mingjie Chen, Francois Charton, and Kristin Lauter. Salsa: Autacking lattice cryplography with transformers. In Proc. of NeurIPS, 2022.
Wojciech Zaremba, Tomas Mikolov, Armand Joulin, and Rob Fergus. Learning simple algorithms from examples. arXiv preprint arXiv:1511.02271 2015.
15

---

Published in Transactions on Machine Learning Research (04/2025)
A
Appendix
We provide details, additional experimental results, and analysis ommitted in the main text:
1. Appendix
B
Broader impacts
2. Appendix
C
Related work
3. Appendix D
Future work
Appendix Attack parameters
Appendix Lattice reduction background
6. Appendix Additional model results (Section
7. Appendix Additional training results (Section
8. Appendix
Further NoMod analysis
B Broader Impacts
The main ethical concern related to this work is the possibility of our allack compromising currently-deployed PQC system. However, at present, our proposed attack does not threaten current standardized systems. If our attack scales higher h and lower q settings, then its impact is significant, as it would necessitate changing PQC encryption standards.
C Related Work
Using machine learning for cryptanalysis. An increasing number of cryplanalytic atlacks in recent years have incorporated ML models, Often, models are used to strengthen existing cryptanalysis approaches, such as side channel or differential analysis Chen & Yu (2021) Of particular interest is recent work that succossfully used ML algorithms to aid side-channel analysis of Kyber, a -NIST-ttandardized PQC method Dubrova et al. (2022). Other ML-based cryptanalysis schemes train models plaintext /cipeeeteetpphtttttcc pairs similar data, enabling direct recovery of cryptographic secrets. Such approaches have been studied against variety of cryptosystems, including hash functions Goncharov (2019). block ciphers Gohr (2019); Benamira et al. [2021) )
Chen & Yu (2021) 0; Alani [2012); So (2020); Kimura et al. 2021 Baek & Kim (2020). and substitution
ciphers Ahmadzadeh et al. (2021] Srivastava & Bhatia (2018) :: Aldarrab & May 2020); Greydanus 2017
The three ML-based LWE attacks upon which this work builds, SALSA Wenger al. (2022). PICANTE
et al. 2023a), and VERDE Li al. (2023b), also take this approach.
AI for Math. The use of neural networks for arithmetic was first considered by Siu & Roychowdhury 1992
and recurrent networks by Zaremba et al. (2015). Kalchbrenner et al. (2015) and Kaiser & Sutskever (2015)
Transformers have been used to solve problems in symbolic and numerical mathematics, integration ( Lample
& Charton 2020), lincar algebra (Charton 2022). 1 arithmetic (Charton 2024) and theorem proving (Polu
& Sutskever 2020 With the advent of large language models, recent research has focused on training
fine-tuning language models on math word problems: problems of mathematics expressed in natural language
Meng & Rumshisky 2019 Griffith & Kalita 2021 Lee et al. 2023). The limitations of these approaches were
discussed by Nogueira el al. (2021) and Dziri et al. (2023). Modular arithmetic was first considered by Power
et al. 2022 and Wenger et al. (0022) Its difficulty was discussed by Palamas (017 and Gromov 2023
D Future Work
Pre-training. Pre-training improves sample efficiency after 80K steps; however, further improvements to pre-training should be explored. First, our experiments used just one set of 4M RA combined with multiple secrets. To encourage generalization lo new RA, pre-training data should include different original As. Second, our transformer only has 14.1M parameters, and may be too small to benefit from pre-training. Third, pre-training data does not have to come from sniffed set of 4n (a, samples. Rather than use expensive preprocessed data, we could simulate reduction and generate random rows synthetically that look like R.A.
16

---

Published in Transactions on Machine Learning Research (04/2025)
ML for modular arithmetic. NoMod experiments consistently show that more training data which does not wrap around the modulus leads to more successful secret recovery (see Figure 3 and Li et al. (2023b)) ) This explains why a smaller modulus q is harder for ML approaches to attack, and indicates that models are not yet learning modular arithmetic (Wenger et al. 2022). Further progress on models learning modular arithmetic problems will likely help to achieve secrel recovery for smaller and larger h.
E Parameters for our attack
For training all models, we use a learning rate of 10-6, weight decay of 0.001, 3000 warmup steps, and an embedding dimension of 512. We use 4 encoder layers, and 8 attention heads for all encoder-only model experiments, except the architecture ablation in Figure 2 We the following primes: q 2199023255531 for 512, q 34088624597 for 768, and q = used for the experiments are in Table 10
for 1024. The rest of the parameters
Table 10: LWE, preprocessing, and training parameters. For the adaptive increase of preprocessing parameters, we start with block size 31, flatter 01, and LLI-delta 61 and upgrade to 82, 02 and 8g at a later stage. Parameters base B and bucket size are used to tokenize the numbers for transformer training.
LWE parameters
Preprocessing settings
Model training settings
n
log2 !
h
B
B2
01
Qg
61
82
Base B
Bucket size
Batch size
512
41
$ 70
18
22
0.04
0.025
0.96
0.9
137435953471
134217728
256
768
35
$ 11
18
22
0.04
0.025
0.96
0.9
1893812477
378762
128
1024
50
S 11
18
22
0.04
0.025
0.96
0.9
2532571560161
15601611
50651431
128
F
Additional background on lattice reduction algorithms
Lattice reduction algorithms reduce the length of lattice vectors, and are building block in most known attacks on lattice-based cryptosystems. If a short enough vector can be found, it can be used to recover LWE secrets via the dual, decoding, or uSVP attack Micciancio & Voulgaris (2010); Allrechh et al. (2017) 2021). The original lattice reduction algorithm, LLL Lenstra et al. (1982), runs time polynomial in the dimension of the lattice, but is only guaranteed to find an exponentially bad approximation to the shortest. vector. In other words the qualily of the reduction is poor. LLL iterates through the ordered basis vectors of lattice projecting vectors onto each other pairwise and swapping vectors until a shorter, re-ordered, nearly orthogonal basis is returned.
To improve the quality of the reduction, the BKZ Schnorr 1987) algorithm generalizes LLL by projecting basis vectors onto k - 1-dimensional subspaces, where < n is the "blocksize"". (LLL has blocksize 2.) As k approaches n, the quality of the reduced basis improves, but the running time is exponential in k, so is not practical for large block size. Experiments in Chen et al. (2020) with running BKZto allack LWE instances found that block size k 2 60 and
100 was infeasible in practice. Both BKZ and LLL implemented in the folll library The FPLLL development team (2023). along with improved version of BKZ: BKZ2. O Chen & Nguyen (2011). Charton et al.) proposed an alternative lattice reduction algorithm similar to LLL. In practice we use it as a polishing step after each BKZ loop concludes. Tt "polishes" " by iteratively orthogonalizing the vectors, provably decreasing norms with each run.
A newer alternative LLL is flatter Ryan Heninger (2023). which provides reduction guarantees analogous to LLL but runs faster due to better precision management. flatter runs on sublattices, and leverages clever techniques for reducing numerical precision as the reduction procoeds, enabling it to run much faster than other reduction implementattioss. Experiments in the original paper show flatter running orders of magnitude faster than other methods on high- nigh-dimensional (n 2 1024) lattice problems. The implementation of flatter has a few tunable parameters, notably a, which characterizes the strength of the desired reduction in terms of lattice "drop", a bespoke method developed by Ryan & Heninger (2023) that mimics the Lovász condition in traditional L.L.. Lenstra et al. 1982). Tn our runs of flatter, we set a = 0.04 initially and
17

---

Published in Transactions on Machine Learning Research (04/2025)
decrease it to 0.025 after the lattice is somewhat reduced, following the adaptive reduction approach of Li et al. 2023b)
G Additional Results for $4
G.1 Architecture Comparison
Tables 11 [for binary secrets) and Tables 13 and 14 (for ternary secrets) expand on the results in Table by showing how three different model architectures perform on binary and ternary secrets with different. Hamming weights. We see that the encoder-only model architecture with angular embedding improves secret model and the encoder-only model with two-token embedding.
recovery compared to the encoder-decole Notably, the encoder-only model with angular embedding is able recover secrets up to 66 for both binary and ternary secrets, which is big improvement comparod to previous work.
Table 11: Secret recovery (# successful recoveries/ # attack attempts) with varions model architectures for h h (n 512, log, 9 41, binary secrets).
h
Architecture
57
58
59
60
61
62
63
64
65
66
Encoder-Decoder
1/10
1/10
1/10
Encoder (Vocabulary)
0/10
0/7
2/10
0/10
0/8
0/10
1/10
0/9
0/8
0/8
Encoder (Angular)
2/10
0/7
3/10
2/10
1/8
1/10
2/10
1/9
1/8
2/8
Table 12: Average time to recovery (hours) for successful recoveries with various model architectures for h 57 h 66 (n 512, loga q 41, binary secrets).
h
Architecture
57
58
59
60
61
62
63
64
65
66
Macoder-Decodde
10.0
20.0
17.5
Encoder (Vocabulary)
19.8
22.0
Encoder (Angular)
33.0
37.0
33.2
29.1
26.7
29.8
57.1
31.6
28.8
Table 13: Secret recovery (## successful recoveries/ # attack attempts) with varions model architectures for h 57 h 66 (n 512, log, g 41, ternary secrets).
h
Archilecture
57
58
59
60
61
62
63
64
65
66
Encoder-Decoder
1 1/10
Encoder (Vocabulary)
0/9
1/8
0/9
0/9
1/10
0/8
0/7
0/7
0/10
1/9
Encoder (Angular)
0/9
1/8
0/9
0/9
1/10
0/8
0/7
0/7
0/10
1/9
G.2 Architecture Ablation
Here, we present additional results from the architecture ablation experiments summarized in Table 2 The results in Table 15 and Table [6 show the number of successful recoveries and average time to recovery with varying architectures across different Hamming weights. We see that increasing transformer depth (number of layers) tends improve recovery but also increases average recovery time. Inereasing the embodding dimension from 256 512 with 4 layers improves secret recovery. Thus, we choose 4 layers with hidden dimension of 512 as recovers the most secrets (25%) the fastest (26.2 mean hours).
18

---

Published in Transactions on Machine Learning Research (04/2025)
Table 14: Average time to recovery (hours) for successful recoveries with various model architectures for h 57 to h 66 (n 512, logg 9 41, ternary secrets).
h
Architecture
57
58
59
60
61
62
63
64
65
66
Encoder-Decoder
27.5
Encoder (Vocabulary)
24.8
28.2
34.4
Encoder (Angular)
57.6
47.4
70.3
Table 15: Effect of different transformer depths (# of layers) and widths (embedding dimension) on secret recovery (# successful recoveries/ # attack attempts) with encoder-only model (n 512, log, 4 = 41, binary secrets).
h
Layers
Emb Dim
49
51
53
55
57
59
61
63
65
67
128
2/9
4/10
5/10
3/9
2/10
2/8
1/9
3/10
1/9
0/10
256
2/9
4/10
5/10
3/9
2/10
2/8
1/9
2/10
1/9
0/10
4
512
3/9
4/10
5/10
4/9
2/10
2/8
1/9
3/10
1/9
0/10
6
512
3/9
4/10
5/10
3/9
2/10
2/8
2/9
3/10
1/9
0/10
512
3/9
4/10
5/10
4/9
2/10
2/8
1/9
2/10
1/9
0/10
H
Additional Results for $5
H.1 Training with Fewer Samples
Here, we present additional results from scaling to 768 and 1024 (without pre-training) as summarized in Table 7 Tables 17 and 18 show the results for the n = 768, log2 = 35 case with binary secrets. Similarly, Tables
and 20 show the results for the n = 1024, log2 = 50 case with binary secrets.
H.2 Model Pre- Tr--Trinning
In this section, we expand upon the pre-training results summarized in Figures 5 and 4 For each pre-training chockpoint, we mcasure number of successful recoverics out of trials per h and the average time hours successful secret recovery for 30 h 45. We also vary the number of samples from 100K to 4M see 512 and
which setup is most sample efficient. In all of these experiments, binary secrets. The results are presented as follows: no pre-training bascline (Tables 21 and 22] 80K steps
fixed, log, q 41, with
pre-training (Tables 23 and 24 240K steps pre-training (Tables 25 and 26 and 440K steps pre-training
(Tables 27 and 28
Based on these results, we conclude that some pro-training helps to recover secrets with less samples, but more pre-training not necessarily better. We also see that more pre-training increases the average time successful secret recovery.
19

---

Published in Transactions on Machine Learning Research (04/2025)
Table 16: Effect of different transformer depths (# of layers) and widths (embedding dimension) on average time to recovery (hours) with encoder-only model (n 512, log2 9 41, binary secrets).
h
Layers
Emb Dim
49
51
53
55
57
59
61
63
65
67
2
128
8.7
10.0
8.3
14.0
11.0
5.5
11.5
17.9
18.9
4
256
30.9
11.0
12.3
30.3
39.9
10.4
20.6
13.3
19.6
4
512
27.2
15.4
18.2
35.2
35.4
17.3
24.3
32.2
26.2
6
512
44.1
18.8
20.7
34.2
30.5
19.4
47.9
32.1
28.1
8
512
46.4
22.5
24.0
44.6
34.6
23.8
28.0
29.0
30.3
Table 17: Successful secret recoveries out 10 trials per h with varying amounts of training data (n 768, log, q = 35, binary secrets).
Average time (hours) to successful secret recoveries with varying amounts of training data (n = 768, log, 35, binary secrets).
Table 18:
# Samples
# Samples
7
11
5
100K
100K
1.4
300K
1
300K
0.7
12.3
1M
3
1M
27.9
24.5
39.2
3M
3
3M
17.8
13.0
44.2
4M
3
4M
13.5
18.5
21.8
Table Successful secret recoveries out of 10 trials per h with varying amounts of training data (n 1024, log, 50, binary secrets).
Table 20: Average time (hours) to successful secret recoveries with varying amounts training data (n 1024, log, 50, binary secrets).
h
# Samples
# Samples
5
7
9
11
13
15
100K
3
100K
11.6
300K
6
3
300K
14.8
17.7
1M
4
1
1M
15.7
29.2
36.1
47.4
3M
3M
14.8
14.0
29.6
39.8
4M
4M
19.9
10.6
21.3
Table 21: Successful secret recoveries out of 10 trials per with no model pre-training (n 512, log, 4 41, binary secrets).
h
# Samples
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
100K
300K
1
1M
3
2
1
3
1
1
1
2
3M
4
3
1
2
1
2
2
4M
1
4
3
1
3
1
1
2
Results of NoMod Analysis
As another performance metric for our approach, we measure the NoMod factor for the secrets secrets/datasen /atasets we attack. Li et al. computed NoMod follows: given training dataset. of LWE pairs (Ra, Rh) represented
20

---

Published in Transactions on Machine Learning Research (04/2025)
Table 22: Average time (hours) to successful secret recovery with no model pre-training (n = 512, logg ?
41, binary secrets).
h
# Samples
30
33
31
36
37
40
43
45
100K
300K
30.3
1M
21.1
36.9
36.3
27.5
21.9
23.9
16.5
50.7
52.9
3M
14.4
21.8
27.6
41.8
19.8
25.5
22.7
18.1
39.5
44.3
37.8
4M
26.5
29.1
69.7
22.7
22.7
20.9
29.0
25.7
40.5
Successful secret recoveries out of 10 trials per with 80K steps model pre-training (n 512, logg 41, binary secrets).
Table 23:
h
Samples
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
100K
1
300K
2
2
2
1M
1
3
2
1
1
3M
1
3
2
1
2
4M
1
3
2
1
Table 24: Average time (hours) to successful secret recovery with 80K steps model pre-training
(n 512, log, 41, binary secrets).
h
# Samples
30
31
32
33
34
35
36
37
39
40
43
100K
29.2
32.1
300K
57.7
47.6
26.9
31.7
62.6
55.6
50.9
1M
53.4
37.0
25.6
61.7
25.1
65.9
30.0
44.8
51.4
3M
34.4
41.8
25.1
57.5
26.2
45.1
23.6
38.4
39.7
4M
35.1
30.9
33.0
35.2
36.5
21.8
26.8
32.1
Table 25: Successful secret recoveries out of 10 trials per with 240K steps model pre-training (n 512, log, 41, binary secrets).
h
# Samples
30
31
32
33
34
35
36
37
38
39
40
42
43
44
45
100K
1
300K
2
2
2
2
1M
1
2
2
1
1
3M
1
2
2
2
1
4M
1
2
2
1
in the range (-g/2,g/2) and known secret compute Ra s Rb. If ||-||| < 9/2, know that the computation of Ra S did not cause R/ to "wrap around" modulus g. The NoMod factor of dataset is the percentage of (Ra, Rb) pairs for which ||ж||| < q/2.
Although NoMod is not usable a real world attack, since it requires a priori knowledge of s, it is a useful metric for understanding attack success in a lab environment. Li et all derived an empirical result stating that attacks should be successful when the NoMod factor of dataset is > 67. The NoMod analysis
21

---

Published in Transactions on Machine Learning Research (04/2025)
Table 26: Average time (hours) to successful secret recovery with 240K steps model pre-training (n 512, log, q 41, binary secrets).
h
# Samples
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
100K
21.0
300K
49.3
30.8
23.3
50.5
64.2
37.9
IM
49.4
29.5
23.4
50.8
20.1
24.8
24.2
51.9
61.9
3M
48.9
38.2
19.7
38.5
50.9
20.2
57.7
47.4
4M
42.4
34.9
19.5
55.8
29.0
24.1
18.3
54.0
52.4
Table 27: Successful secret recoveries out of 10 trials per with 440K steps model pre-training (n 512, log, g 41, binary secrets).
h
# Samples
30
31
32
33
34
35
36
37
40
42
43
44
45
100K
1
1
300K
1
2
1
1M
2
1
3M
1
1
2
2
4M
1
1
2
2
Table 28: Average time (hours) to successful secret recovery with 440K steps model pre-training (n 512, log, g 41, binary secrets).
h
# Samples
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
100K
33.3
20.0
300K
39.8
12.9
29.0
60.5
36.2
49.1
59.1
1M
56.9
16.6
18.6
43.6
24.9
36.4
53.4
3M
50.9
32.3
12.2
25.2
22.3
18.9
42.4
60.8
4M
58.3
30.0
13.5
34.6
19.7
22.3
45.7
59.7
indicates that models trained in those experiments only learning secrets from datasets in which the majority of Rb values do not "wrap around" g. If models could be trained to learn modular arithmetic better, this might ease the NoMod condition for success.
One of the main goals of introducing the angular embedding to introduce some inductive bias into the model training process. Specifically, teaching models that and g - are close the embedding space may enable them to better learn the modular arithmetic task at the heart of LWE. Here, we examine the NoMod factor of various datasets to if the angular embedding does provide such inductive bias. If it did, would expect that models with angular embeddings would recover secrets from datsets with NoMod 67. Table 29 lists NoMod percentages and successful secret recoveries for the angular and tokenization schemes described in 4.2
22

---

Published in Transactions on Machine Learning Research (04/2025)
Table 29: NoMod percentages for Verde data n 512, log, 9 41, binary secrets (varying and secrets indexed 0-9), comparing performance of angular vs. normal embedding. Key: recovered by angular only, recovered by both, not recovered.
h
3
7
57
45
49
52
41
51
46
51
57
60
49
58
48
48
48
48
38
43
52
52
45
48
59
43
46
56
50
66
63
35
46
41
40
60
48
59
58
49
54
61
49
41
42
41
50
62
45
42
45
54
55
43
61
56
54
42
63
56
60
55
54
63
47
54
51
45
43
64
44
46
41
41
41
47
45
43
41
55
65
45
51
48
60
45
48
41
48
45
50
66
45
51
39
64
45
47
43
60
48
55
67
47
48
49
40
47
48
51
50
46
Table 30: NoMod percentages for 768, log, 9 35 secrets (varying h and secrets indexed 0-9). Key: secret recovered, secret not recovered.
Table 31: NoMod percentages for n = 1024,
log, 9 = secrets (varying h and secrets indexed 0-10). Key: secret recovered, secret not recovered.
0
2
3
4
5
6
8
9
5
61
61
52
61
93
68
66
61
56
62
66
70
81
81
53
52
61
56
77
52
68
56
67
56
61
62
47
80
80
69
56
57
52
57
69
52
55
46
49
52
48
56
60
60
70
56
69
52
49
52
53
56
57
46
52
11
55
42
44
55
46
46
54
55
60
51
11
52
52
62
61
62
56
56
52
13
46
45
60
48
43
43
55
48
60
43
13
51
46
56
40
46
52
44
49
68
53
15
41
38
48
43
40
43
45
43
43
59
15
40
45
41
38
47
23


Reviews:
[{"review_id": "NgCgHP7onk", "reviewer": "Reviewer_YQZC", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n1. Introduces the LWE and PQC problems well to non-expert readers.\n2. The angular embedding is an interesting development that has empirical performance improvements over a standard vocabulary embedding.\n3. While the approach in and of itself is limited in its novelty, the combination of methods demonstrates tangible improvements and presents a significant contribution to the field of LWE.\n4. The number of experimentation and ablations demonstrate well the component based performance and trade-offs.\n5. The work is generally well written and presented. \n\n**Weaknesses**\n1. My biggest concern is the scope and positioning of the paper within Machine Learning research. I would arguably state that this method would be better placed in security focussed venue, given the limited contribution to the ML field of which TMLR is positioned. \n2. Much of the advancements do not lie in the ML research space. Rather, a number of existing methods have been combined to produce a more innovative systems approach to the application domain. Hence, for this venue the novelty is limited.\n3. The angular embedding section defines the development well, however, the choice is not well motivated. For example, how does the angular embeddings help represent the modular structure of the problem. A few more questions regarding the angular embedding are given below:\n    a. How does the learned linear projection W_e ensure an ellipse is learnt?\n    b. Did you try a vocabulary embedding with the additional learnable linear layers W_e and W_a? If so, does this improve the performance of vocabulary embeddings?\n    c. More analyses of the embeddings would be desirable to ensure the expected behaviour is being observed.\n4. Limitations of the work are not discussed.\n\n**Minor Comments**\n1. It is not clear how or why the problem setting was defined, why the values in table 3, why not alternative values or other settings. Does this follow prior works? \n2. It is not clear in the text if Flatter has been developed in this work or has been utilised by the authors. I assume the former as this has not been described in detail or anonymised.\n3. The addition of “Salsa Fresca” in the title does not help describe the work or its contributions, and perhaps an abbreviation of the methods used would be better placed.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a set of training methods to improve computational performance of the learning with errors problem in post-quantum cryptography. The authors present a significant improvement in computational time through the combining of established pre-processing techniques and pre-training methods. Angular embeddings are also introduced to improve recovery results, with the authors stating such embeddings more naturally align to the problem setting and domain. The authors provide a detailed empirical analysis and a number of ablations to demonstrate the improvements of their method and achieve recovery that has yet to be seen in existing literature.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Focus the writing more on the ML contributions and motivation. While the problem domain is well defined, more efforts should be made to adhere to the focus of the venue. For example, the introduction only briefly discusses the ML challenges and motivation. \n2. More focus on the motivation, and analysis of the angular embeddings, this is the primary contribution of the work, and is reduced to a single paragraph, that does not describe well its context.\n\n**Minor Changes**:\n1. Table 1, clarify what has the attack time been reduced from? You state it is now 50 from which value.\n2. Re-work section 3 to make it clear flutter is a previous development, utilised by the authors. In addition, provide quantitative values for the experimental setup of section 3. For example, replace “many” with specific values to aid reproduction.", "broader_impact_concerns": "The broader impact statement could be expanded further. There is a significant number of ethical risks that implicate this work, and the current statement could elaborate further.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "9GRBuuDqpc", "reviewer": "Reviewer_hCFg", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The paper is well organized and easy to follow.\n2. The method is well illustrated.\n3. The experimental results show promising results. \n\nWeaknesses:\n1. Some of the contributions claimed by the authors seem more like technical improvements rather than strict novel methods. For example, the methods adopted in the pre-processing phase are off-the-shelf.\n2. The paper proposed angular embedding in the transformer. but the motivation is not clearly justified. Besides, the advantages of the proposed angular embedding over the previous models are not fully discussed.\n3. From Figure 5, it seems that the pre-training could not effectively reduce the mean hours on large training dataset (e.g., 3M and 4M).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper focuses on improving machine learning (ML) attacks on the Learning with Errors (LWE) problem underlying post-quantum cryptography with three major techniques: better preprocessing, angular embeddings and model pre-training. The experiments show that the proposed method can improve the efficiency of the attacks on LWE problems.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Can authors further explain the motivation behind the proposed angular embedding? What are the advantages of the proposed angular embedding compared to the previous models? How does the angular embedding can overcome the shortcomings, namely quadratic computational cost and lose of inductive bias of number continuity.\n\n2. What is the computational expense of model pre-training? When model pre-training is included, is it still more efficient than the approach without model pre-training?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "JUSZy0zY8a", "reviewer": "Reviewer_FZQP", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths  \n\n$\\bullet$ The authors address a highly challenging computational problem, and their pre-processing improvements play a crucial role in making such attacks computationally feasible. If successful, these attacks could significantly impact the security of post-quantum cryptography (PQC), underscoring the importance of this work in evaluating the robustness and security guarantees of PQC schemes.\n\n$\\bullet$ The paper provides a solid empirical evaluation, with detailed comparisons to previous ML-based approaches for LWE attacks. The authors have done a commendable job of thoroughly discussing the attack parameters and hyperparameters, which adds to the transparency and reproducibility of the work. \n\n$\\bullet$ The paper is well-organized and written clearly and concisely. Even readers who are not experts in cryptography will find it easy to follow. \n\n\n## Weaknesses\n\n\n$\\bullet$ The paper lacks deeper insights and novel algorithmic contributions. While these engineering tweaks offer significant speedup, the authors could consider exploring and highlighting any insights that may have emerged during their work. \n\n\n$\\bullet$ The paper does not quantitatively or qualitatively demonstrate the advantages of using sub-quadratic or linear softmax-based attention mechanisms (see [1,2,3]) in terms of speeding up the attacks. \n\nIt would strengthen the work if the authors could include specific experiments or analyses that clearly show the impact of these mechanisms on computational efficiency and attack performance. \n\n$\\bullet$ The authors should include a detailed breakdown of the speedup improvements, demonstrating how specific components contribute to the overall improvement (e.g., achieving a 25$\\times$ speedup for $n$=512). This analysis would provide a clearer understanding of the most impactful factor in achieving the reported performance gains, and strengthen the empirical evaluation.\n\n[1] Zhang et al., The Hedgehog & the Porcupine: Expressive Linear Attentions with Softmax Mimicry, ICLR 2024\n\n[2] Zhang et al., Gated Slot Attention for Efficient Linear-Time Sequence Modeling, NeurIPS 2024. \n\n[3] Han at al., Bridging the Divide: Reconsidering Softmax and Linear Attention, NeurIPS 2024.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper builds upon existing machine learning-based attacks on the Learning with Errors (LWE) problem by leveraging off-the-shelf cryptographic tools (e.g., Flatter), and a novel algorithmic technique (e.g., angular embedding). These engineering tweaks substantially speed up the pre-processing phase, and enable the attack to scale effectively to real-world LWE parameters, such as $n$=1024, commonly employed in homomorphic encryption schemes.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See the weakness.", "broader_impact_concerns": "Addressed in the paper", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper, the authors introduce three key improvements to machine learning attacks on the learning with errors problem: **a)** faster preprocessing, **b)** angular embeddings, and **c)** model pre-training, which make ML attacks on LWE more efficient and scalable.
 
By integrating the Flatter algorithm and interleaving BKZ and polishing techniques, preprocessing is accelerated by 25×, while an encoder-only transformer architecture with angular embeddings reduces computational complexity, improving training efficiency. Additionally, the paper explores pre-training for ML-based LWE attacks, reducing the number of training samples required by 10×, making attacks significantly more sample-efficient.
 
The reviewers have generally been positive but have highlighted areas that could improve the paper and should be considered carefully when preparing the camera-ready version, given that the authors did not submit a revised version during the reviewer-author discussion. Therefore, the statements that authors have made during their responses need to be reflected in the camera-ready version submission. For example:
 
**a)** Provide a clearer motivation for angular embeddings and how they preserve cyclic structure of LWE problems

**b)** Add additional discussion on “the surprising nature of combining optimizations”

**c)** Incorporate the references and statements made in response to reviewer YQZC, e.g. around the Flatter Algorithm referencing

**d)** Expand section 2.4 to justify why specific LWE parameters were chosen

**e)** Please reorganise the information mentioned in response to FZQP reviewer related to “Speedup Breakdown”
Decision: Accept (poster)