基于列表译码方法在查询访问模型下含错学习问题的分析

Analysis of Learning With Errors in Query Access Model:A List Decoding Approach

Regev在2005年提出了含错学习问题(LWE),这个问题与随机线性码的译码问题密切相关,并且在密码学特别是后量子密码学中应用广泛。原始的含错学习问题是在随机访问模型下提出的,有证据证明该问题的困难性。许多研究者注意到的一个事实是当攻击者可以选择样本时,该问题是容易的。但是目前据作者所知并没有一个完整的求解算法。该文分析了查询访问模型下的带有错误学习问题,给出了完整的求解算法。分析采用的工具是将该问题联系到隐藏数问题,然后应用傅里叶学习算法进行列表译码。

Regev introduced the Learning With Errors(LWE) problem in 2005, which has close connections to random linear code decoding and has found wide applications to cryptography, especially to post-quantum cryptography. The LWE problem is originally introduced in random access model, and there are evidences that indicate the hardness of this problem. It is well known that the LWE problem is vulnerable if the attacker is allowed to choose samples. However, to the best of the author’s knowledge, a complete algorithm has not been published. In this paper, the LWE problem in query samples access model is analyzed. The technique is to relate the problem to the hidden number problem, and then Fourier learning method is applied to the list decoding.