Limitations of the decoding-to-LPN reduction via code smoothing
<|reference_start|>Limitations of the decoding-to-LPN reduction via code smoothing: The Learning Parity with Noise (LPN) problem underlies several classic cryptographic primitives. Researchers have endeavored to demonstrate the algorithmic difficulty of this problem by attempting to find a reduction from the decoding problem of linear codes, for which several hardness results exist. Earlier studies used code smoothing as a technical tool to achieve such reductions, showing that they are possible 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.<|reference_end|>
@article{pathegama2024limitations,
    title={Limitations of the decoding-to-LPN reduction via code smoothing},
    author={Madhura Pathegama and Alexander Barg},
    journal={arXiv preprint arXiv:2408.03742},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.03742},
    primaryClass={cs.IT cs.CR math.IT}
}