An Experimental Analysis on Lattice Attacks against Ring-LWE over Decomposition Fields
An Experimental Analysis on Lattice Attacks against Ring-LWE over Decomposition Fields
复制标题
DOI：
10.23919/isita.2018.8664308
复制
发表时间：
2018-10
期刊：
影响因子：
--
通讯作者：
Shota Terada;Hideto Nakano;Shinya Okumura;A. Miyaji
中科院分区：
文献类型：
--
作者：
Shota Terada;Hideto Nakano;Shinya Okumura;A. Miyaji
带误差学习的环变体（ring - lwe）问题提供了有效的后量子加密方案，包括同态加密方案。从效率和安全性的角度考虑，通常使用分环域作为环- lwe的底层数域。然而，特别是在HE方案中，提高效率和保证安全性是当前的重要任务。Arita和Handa提出将分解域作为Ring-LWE的底层数字域，并成功构建了一种能够同时高效加密多个明文的HE方案。然而，没有足够的证据表明分解字段不提供弱Ring-LWE实例。本文给出了分解场上针对Ring-LWE的晶格攻击的实验分析。更精确地说，我们分别在分解域和具有一些素数的环切域上对Ring-LWE进行了格攻击，并比较了各自的运行时间、成功率和根厄米特因子。我们还比较了针对不同分解域的相同攻击的结果，以找到提供弱Ring-LWE实例的分解域。通过我们的分析，我们期望分解场能够提供更安全、高效的基于环- lwe的HE方案。
The ring variant of learning with errors (Ring-LWE) problem has provided efficient post-quantum cryptographic schemes including homomorphic encryption (HE) schemes. Usually, cyclotomic fields are used as underlying number fields of Ring-LWE from the viewpoints of efficiency and security. However, especially in the case of HE schemes, improving the efficiency and ensuring the security are important tasks even now. Arita and Handa proposed to use decomposition fields as underlying number fields of Ring-LWE and successfully constructed a HE scheme which can encrypt many plaintexts efficiently at a time. However, there is no enough evidence that decomposition fields do not provide weak Ring-LWE instances.In this paper, we give an experimental analysis on lattice attacks against Ring-LWE over decomposition fields. More precisely, we conducted lattice attacks against Ring-LWE over decomposition fields and over the ℓ-th cyclotomic fields with some prime numbers ℓ, respectively, and compared each of the running-time, the success rate and the root hermite factor. We also compared the results of the same attacks on various decomposition fields to find decomposition fields providing weak Ring-LWE instances. As a result of our analysis, we expect that decomposition fields would provide more secure and efficient HE schemes based on Ring-LWE compared to the ℓ-th cyclotomic fields.