Cryptology ePrint Archive: Report 2014/097

Candidate Constructions of Fully Homomorphic Encryption on Finite Simple Groups without Ciphertext Noise

Koji Nuida

Abstract: 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.

Category / Keywords: public-key cryptography / public-key cryptography, fully homomorphic encryption, group-based cryptography

Date: received 10 Feb 2014, last revised 2 Nov 2015

Contact author: k nuida at aist go jp

Available format(s): PDF | BibTeX Citation

Note: Including an attack found for the instantiation of the scheme in 19-Aug-2015 version; see Page 17.

Version: 20151102:214109 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]