by Teik Guan Tan, De Wen Soh, and Jianying Zhou
Learning Parity with Noise (LPN) is an attractive post-quantum cryptosystem for low-resource devices due to its simplicity. Communicating parties only require the use of AND and XOR gates to generate or verify LPN cryptogram samples exchanged between the parties. However, the LPN setup is complicated by different parameter choices including key length, noise rate, sample size, and verification window which can determine the usability and security of the implementation. To address advances in LPN cryptanalysis, recommendations for ever increasing key lengths have made LPN no longer feasible for low resource devices. In this paper, we use a series of experiments to simulate and cryptanalyze LPN authentication under different parameter values to arrive at recommended values suitable for low-resource devices. We also examine the impact of limiting the key lifespan of the LPN secret vector as a means to balance security while keeping key lengths relatively short.
Published at ICICS 2022 https://link.springer.com/chapter/10.1007/978-3-031-15777-6_2
You can check out the video presentation below: