All Dates/Times are Australian Eastern Standard Time (AEST)

Technical Program

Paper Detail

Paper IDD5-S6-T4.2
Paper Title Practically Solving LPN
Authors Thom Wiggers, Simona Samardjiska, Radboud University, Netherlands
Session D5-S6-T4: Post Quantum Cryptography
Chaired Session: Friday, 16 July, 23:40 - 00:00
Engagement Session: Saturday, 17 July, 00:00 - 00:20
Abstract The best algorithms for the Learning Parity with Noise (LPN) problem require sub-exponential time and memory. This often makes memory, and not time, the limiting factor for practical attacks, which seem to be out of reach even for relatively small parameters. In this paper, we try to bring the state-of-the-art in solving LPN closer to the practical realm. We improve upon the existing algorithms by modifying the Coded-BKW algorithm to work under various memory constrains. We correct and expand previous analysis and experimentally verify our findings. As a result we were able to mount practical attacks on the largest parameters reported to date using only 2³⁹ bits of memory.