On Compression Functions over Small Groups with Applications to Cryptography
share
In the area of cryptography, fully homomorphic encryption (FHE) enables any entity to perform arbitrary computation on encrypted data without decrypting the ciphertexts. An ongoing group-theoretic approach to construct FHE schemes uses a certain "compression" function F(x) implemented by group operators on a given finite group G (i.e., it is given by a sequence of elements of G and variable x), which satisfies that F(1) = 1 and F(σ) = F(σ^2) = σ where σ∈ G is some element of order three. The previous work gave an example of such F over G = S_5 by just a heuristic approach. In this paper, we systematically study the possibilities of such F. We construct a shortest possible F over smaller group G = A_5, and prove that no such F exists over other groups G of order up to 60 = |A_5|.
READ FULL TEXT