International Association
for Cryptologic Research

We propose constructions of fully homomorphic encryption completely different from the previous work, using special kinds of non-commutative finite groups. Unlike the existing schemes, our ciphertexts involve no \"noise\" terms, hence the inefficient \"bootstrapping\" procedures are not necessary. Our first scheme is based on improved results on embeddings of logic gates into (almost) simple groups [Ostrovsky and Skeith III, CRYPTO 2008]. Our second scheme is based on properties of the commutator operator (analogous to those used in Barrington\'s theorem) and a new idea of input rerandomization for commutators, effective for some (almost) simple matrix groups. Our main idea is to conceal the concrete structures of the underlying groups by randomly applying some special transformations famous in combinatorial group theory, called Tietze transformations, to a kind of symbolic representations of the groups. Ideally, the resulting group is expected to behave like a black-box group where only an abstract group structure is available; a detailed analysis of the true effect of random Tietze transformations on the security is a future research topic. We emphasize that such a use of Tietze transformations in cryptology has no similar attempts in the literature and would have rich potential for further applications to other areas in cryptology.