Abstract
Recent work showed that ML-based attacks on Learning with Errors (LWE), ahard problem used in post-quantum cryptography, outperform classical algebraicattacks in certain settings. Although promising, ML attacks struggle to scaleto more complex LWE settings. Prior work connected this issue to the difficultyof training ML models to do modular arithmetic, a core feature of the LWEproblem. To address this, we develop techniques that significantly boost theperformance of ML models on modular arithmetic tasks, enabling the models tosum up to $N=128$ elements modulo $q \le 974269$. Our core innovation is theuse of custom training data distributions and a carefully designed lossfunction that better represents the problem structure. We apply an initialproof of concept of our techniques to LWE specifically and find that they allowrecovery of 2x harder secrets than prior work. Our techniques also help MLmodels learn other well-studied problems better, including copy, associativerecall, and parity, motivating further study.