On Compression Functions over Groups with Applications to Homomorphic Encryption

2022/08/04 by Koji Nuida, Nuida, Koji
Computer Science · Engineering · #20D60 #94A60 #Coding theory and cryptography #Cryptography and Data Security #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Mathematics #Group Theory (math.GR) #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2208.02468

openalex publication_date 2022/08/04 · openalex created_date 2022/08/06 · openalex updated_date 2026/07/28

Abstract

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(σ²) = σ where σ∈ G is some element of order 3. The previous work gave an example of such a function over the symmetric group G = S₅ 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 ≤ 4). We also construct such a function over the alternating group G = A₅ 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₅, which is more efficient than the previously known reductions.

Related

• On non-abelian homomorphic public-key cryptosystems
• Introducing GRAFHEN: Group-based Fully Homomorphic Encryption without Noise
• On homomorphic encryption using abelian groups: Classical security analysis
• An Unbounded Fully Homomorphic Encryption Scheme Based on Ideal Lattices and Chinese Remainder Theorem
• Homomorphic encryption schemes based on coding theory and polynomials