论文标题
在具有同态加密应用的组上的压缩功能上
On Compression Functions over Groups with Applications to Homomorphic Encryption
论文作者
论文摘要
完全同态加密（FHE）使实体能够在加密数据上执行任意计算，而无需解密密文。构建FHE方案的正在进行的组理论方法使用了由小组操作在给定有限的组$ G $上实现的某个“压缩”函数$ f（x）$，它满足$ f（1）= 1 $ and $ f（σ）= f（σ^2）=σ$ in g $ 3 $ 3 $ 3 $ 3 $ 3 $。先前的工作给出了一个示例，即通过一种启发式方法在对称组$ g = s_5 $上提供了这样的功能。在本文中，我们系统地研究了各组功能的可能性。我们表明，在任何可解决的组$ g $（例如Abelian组和较小的对称组$ s_n $的$ n \ leq 4 $）上不存在这样的功能。我们还可以在交替的组$ g = a_5 $上构造这种功能，该功能的表达式最短。此外，通过使用此新功能，我们将FHE方案的构造减少到了组$ A_5 $的同型加密方案的构造，这比以前已知的还原更有效。
Fully homomorphic encryption (FHE) enables an entity to perform arbitrary computation on encrypted data without decrypting the ciphertexts. An ongoing group-theoretical approach to construct an FHE scheme uses a certain "compression" function $F(x)$ implemented by group operations on a given finite group $G$, which satisfies that $F(1) = 1$ and $F(σ) = F(σ^2) = σ$ where $σ\in G$ is some element of order $3$. The previous work gave an example of such a function over the symmetric group $G = S_5$ by just a heuristic approach. In this paper, we systematically study the possibilities of such a function over various groups. We show that such a function does not exist over any solvable group $G$ (such as an Abelian group and a smaller symmetric group $S_n$ with $n \leq 4$). We also construct such a function over the alternating group $G = A_5$ that has a shortest possible expression. Moreover, by using this new function, we give a reduction of a construction of an FHE scheme to a construction of a homomorphic encryption scheme over the group $A_5$, which is more efficient than the previously known reductions.
