Attacks on Search RLWE
Attacks on Search RLWE
复制标题
对搜索 RLWE 的攻击
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Katherine E. Stange
中科院分区：
文献类型：
--
作者：
Hao Chen;K. Lauter;Katherine E. Stange
我们描述了一种新的攻击的搜索环学习错误（RLWE）问题的卡方统计检验的基础上，并给出例子的RLWE实例伽罗瓦数域容易受到我们的攻击。我们证明了一个搜索到决策减少伽罗瓦域适用于任何unramified素数模q，无论剩余的程度f的q，我们使用这在我们的攻击。我们的攻击的时间复杂度是O（q），其中f是q在K中的剩余度。我们还展示了攻击RLWE问题的一般分圆环（非2幂分圆环）的工作时，模是一个分歧素。我们通过发现许多易受攻击的实例并成功地攻击它们来演示实际攻击。我们包括所有攻击的代码。
We describe a new attack on the Search Ring Learning-With-Errors (RLWE) problem based on the chi-square statistical test, and give examples of RLWE instances in Galois number fields which are vulnerable to our attack. We prove a search-to-decision reduction for Galois fields which applies for any unramified prime modulus q, regardless of the residue degree f of q, and we use this in our attacks. The time complexity of our attack is O(q ), where f is the residue degree of q in K. We also show an attack on the RLWE problem in general cyclotomic rings (non 2-power cyclotomic rings) which works when the modulus is a ramified prime. We demonstrate the attacks in practice by finding many vulnerable instances and successfully attacking them. We include the code for all attacks.