计算机科学
算法
噪音(视频)
量子
降噪
带着错误学习
密码学
理论计算机科学
人工智能
量子力学
图像(数学)
物理
作者
Bénédikt Tran,Serge Vaudenay
标识
DOI:10.1007/978-3-031-17433-9_13
摘要
The Learning Parity with Noise (LPN) problem is a famous cryptographic problem consisting in recovering a secret from noised samples. This problem is usually solved via reduction techniques, that is, one reduces the original instance to a smaller one before substituting back the recovered unknowns and starting the process again. There has been an extensive amount of work where time-memory trade-offs, optimal chains of reductions or different solving techniques were considered but hardly any of them involved quantum algorithms. In this work, we are interested in studying the improvements brought by quantum computers when attacking the LPN search problem in the sparse noise regime. Our primary contribution is a novel efficient quantum algorithm based on Grover’s algorithm which searches for permutations achieving specific error patterns. This algorithm non-asymptotically outperforms the known techniques in a low-noise regime while using a low amount of memory.
科研通智能强力驱动
Strongly Powered by AbleSci AI