On compression functions over groups with applications to homomorphic encryption

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 [Formula: see text] implemented by group operations on a given finite group [Formula: see text], which satisfies that [Formula: see text] and [Formula: see text] where [Formula: see text] is some element of order [Formula: see text]. The previous work gave an example of such a function over the symmetric group [Formula: see text] 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 [Formula: see text] (such as an Abelian group and a smaller symmetric group [Formula: see text] with [Formula: see text]). We also construct such a function over the alternating group [Formula: see text] 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 [Formula: see text], which is more efficient than the previously known reductions.