论文标题
具有错误问题和涂抹条件的多项式学习
The Polynomial Learning With Errors Problem and the Smearing Condition
论文作者
论文摘要
随着量子计算的迅速发展，保证抗量子攻击的加密协议的安全性至关重要。一些领先的候选密码系统使用错误（LWE）问题的学习，以简单性和硬度的吸引力，可通过减少硬计算晶格问题来保证。它的代数变体，带有错误（RLWE）和多项式学习的环形学习（PLWE），比标准LWE的效率提高，但它们的安全性尚待彻底研究。在这项工作中，我们考虑了“涂抹”条件，这是[6]中引入的对PLWE和RLWE攻击的条件。我们扩展了有关Elias等人提出的有关涂抹的一些问题。在[6]中，并展示了涂片与优惠券收藏家的问题有多相关，我们开发了一些实用算法来计算与涂抹有关的概率。最后，我们提出了对PLWE的基于涂抹的攻击，并证明了其有效性。
As quantum computing advances rapidly, guaranteeing the security of cryptographic protocols resistant to quantum attacks is paramount. Some leading candidate cryptosystems use the Learning with Errors (LWE) problem, attractive for its simplicity and hardness guaranteed by reductions from hard computational lattice problems. Its algebraic variants, Ring-Learning with Errors (RLWE) and Polynomial Learning with Errors (PLWE), gain in efficiency over standard LWE, but their security remains to be thoroughly investigated. In this work, we consider the "smearing" condition, a condition for attacks on PLWE and RLWE introduced in [6]. We expand upon some questions about smearing posed by Elias et al. in [6] and show how smearing is related to the Coupon Collector's Problem Furthermore, we develop some practical algorithms for calculating probabilities related to smearing. Finally, we present a smearing-based attack on PLWE, and demonstrate its effectiveness.
