← Back ◬ AI & Machine Learning Mar 31, 2026

Attacks on Sparse LWE and Sparse LPN with new Sample-Time tradeoffs

arXiv Security Archived Mar 31, 2026 ✓ Full text saved

arXiv:2603.27190v1 Announce Type: new Abstract: This paper extends the Kikuchi method to give algorithms for decisional $k$-sparse Learning With Errors (LWE) and $k$-sparse Learning Parity with Noise (LPN) problems for higher moduli $q$. We create a Kikuchi graph for a sparse LWE/LPN instance and use it to give two attacks for these problems. The first attack decides by computing the spectral norm of the adjacency matrix of the Kikuchi graph, which is a generalization of the attack for $q=2$ giv

Full text archived locally

✦ AI Summary · Claude Sonnet

Computer Science > Cryptography and Security [Submitted on 28 Mar 2026] Attacks on Sparse LWE and Sparse LPN with new Sample-Time tradeoffs Shashwat Agrawal, Amitabha Bagchi, Rajendra Kumar This paper extends the Kikuchi method to give algorithms for decisional k-sparse Learning With Errors (LWE) and k-sparse Learning Parity with Noise (LPN) problems for higher moduli q. We create a Kikuchi graph for a sparse LWE/LPN instance and use it to give two attacks for these problems. The first attack decides by computing the spectral norm of the adjacency matrix of the Kikuchi graph, which is a generalization of the attack for q=2 given by Wein et. al. (Journal of the ACM 2019). The second approach computes non-trivial closed walks of the graph, and then decides by computing a certain polynomial of edge labels in the walks. This is a generalization of the attack for q=2 given by Gupta et. al. (SODA 2026). Both the attacks yield new tradeoffs between sample complexity and time complexity of sparse LWE/LPN. Subjects: Cryptography and Security (cs.CR) Cite as: arXiv:2603.27190 [cs.CR] (or arXiv:2603.27190v1 [cs.CR] for this version) https://doi.org/10.48550/arXiv.2603.27190 Focus to learn more Submission history From: Shashwat Agrawal [view email] [v1] Sat, 28 Mar 2026 08:32:00 UTC (50 KB) Access Paper: HTML (experimental) view license Current browse context: cs.CR < prev | next > new | recent | 2026-03 Change to browse by: cs References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)

💬 Team Notes