Limitations of the decoding-to-LPN reduction via code smoothing
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909540153294848 |
|---|---|
| author | Pathegama, Madhura Barg, Alexander |
| author_facet | Pathegama, Madhura Barg, Alexander |
| contents | The Learning Parity with Noise (LPN) problem underlines several classic cryptographic primitives. Researchers have attempted to demonstrate the algorithmic hardness of this problem by finding reductions from the decoding problem of linear codes, for which several hardness results exist. Earlier studies used code smoothing as a tool to achieve reductions for codes with vanishing rate. This has left open the question of attaining a reduction with positive-rate codes. Addressing this case, we characterize the efficiency of the reduction in terms of the parameters of the decoding and LPN problems. As a conclusion, we isolate the parameter regimes for which a meaningful reduction is possible and the regimes for which its existence is unlikely. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_03742 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Limitations of the decoding-to-LPN reduction via code smoothing Pathegama, Madhura Barg, Alexander Information Theory Cryptography and Security 94A60, 94B05 The Learning Parity with Noise (LPN) problem underlines several classic cryptographic primitives. Researchers have attempted to demonstrate the algorithmic hardness of this problem by finding reductions from the decoding problem of linear codes, for which several hardness results exist. Earlier studies used code smoothing as a tool to achieve reductions for codes with vanishing rate. This has left open the question of attaining a reduction with positive-rate codes. Addressing this case, we characterize the efficiency of the reduction in terms of the parameters of the decoding and LPN problems. As a conclusion, we isolate the parameter regimes for which a meaningful reduction is possible and the regimes for which its existence is unlikely. |
| title | Limitations of the decoding-to-LPN reduction via code smoothing |
| topic | Information Theory Cryptography and Security 94A60, 94B05 |
| url | https://arxiv.org/abs/2408.03742 |