On Compression Functions over Groups with Applications to Homomorphic Encryption
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911035453079552 |
|---|---|
| author | Nuida, Koji |
| author_facet | Nuida, Koji |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2208_02468 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | On Compression Functions over Groups with Applications to Homomorphic Encryption Nuida, Koji Group Theory Cryptography and Security 20D60, 94A60 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. |
| title | On Compression Functions over Groups with Applications to Homomorphic Encryption |
| topic | Group Theory Cryptography and Security 20D60, 94A60 |
| url | https://arxiv.org/abs/2208.02468 |