Attacks on Sparse LWE and Sparse LPN with new Sample-Time tradeoffs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911550165483520 |
|---|---|
| author | Agrawal, Shashwat Bagchi, Amitabha Kumar, Rajendra |
| author_facet | Agrawal, Shashwat Bagchi, Amitabha Kumar, Rajendra |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_27190 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Attacks on Sparse LWE and Sparse LPN with new Sample-Time tradeoffs Agrawal, Shashwat Bagchi, Amitabha Kumar, Rajendra Cryptography and Security 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. |
| title | Attacks on Sparse LWE and Sparse LPN with new Sample-Time tradeoffs |
| topic | Cryptography and Security |
| url | https://arxiv.org/abs/2603.27190 |