Towards Constructing Fully Homomorphic Encryption without Ciphertext Noise from Group Theory
Towards Constructing Fully Homomorphic Encryption without Ciphertext Noise from Group Theory
复制标题
从群论构建无密文噪声的全同态加密
DOI：
10.1007/978-981-15-5191-8_8
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Koji Nuida
中科院分区：
文献类型：
--
作者：
Bernhard Muhlherr;Koji Nuida;Koji Nuida
在2008年，比Gentry的开创性的“自举”技术的第一个全同态加密（FHE）方案早一年，Ostrovsky和Skeith III提出了一种完全不同的方法来实现FHE。他们证明了NAND算子可以在一些非交换群中实现;因此，同态加密群的元素将产生一个FHE方案，而不会产生密文噪声。然而，在他们的论文中没有提出关于如何同态加密群元素的观察，文献中也没有后续研究。本文的目的是更清楚地展示什么是足够的，什么似乎是有效的构造FHE计划的基础上，他们的方法。首先，证明了在有限群之间存在满射同态π：G→ G是充分的，其中π的位算子在G中实现，且π的核的元素与G的一般元素不可区分.其次，我们提出了一些新的方法来实现一些群G中的位算子。第三，我们给出了一个观察，一个天真的方法，使用矩阵组将永远不会产生安全的FHE由于攻击利用的“线性”的建设。然后，我们提出了一个想法，以避免这种“线性”使用组合群论。具体实现FHE计划的基础上，我们提出的框架是一个未来的研究课题。
In CRYPTO 2008, 1 year earlier than Gentry’s pioneering “bootstrapping” technique for the first fully homomorphic encryption (FHE) scheme, Ostrovsky and Skeith III had suggested a completely different approach towards achieving FHE. They showed that the NAND operator can be realized in some non-commutative groups; consequently, homomorphically encrypting the elements of the group will yield an FHE scheme, without ciphertext noise to be bootstrapped. However, no observations on how to homomorphically encrypt the group elements were presented in their paper, and there have been no follow-up studies in the literature. The aim of this paper is to exhibit more clearly what is sufficient and what seems to be effective for constructing FHE schemes based on their approach. First, we prove that it is sufficient to find a surjective homomorphism π: G→ G between finite groups for which bit operators are realized in G and the elements of the kernel of π are indistinguishable from the general elements of G. Secondly, we propose new methodologies to realize bit operators in some groups G. Thirdly, we give an observation that a naive approach using matrix groups would never yield secure FHE due to an attack utilizing the “linearity” of the construction. Then we propose an idea to avoid such “linearity” by using combinatorial group theory. Concretely realizing FHE schemes based on our proposed framework is left as a future research topic.