On non-abelian homomorphic public-key cryptosystems

D. Yu. Grigor'ev ; I. N. Ponomarenko

Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part VII, Tome 293 (2002), pp. 39-58

Résumé

We construct homomorphic cryptosystems being (secret) epimorphisms $f\colon G\to H$, where $G$, $H$ are (publically known) groups and $H$ is finite. A letter of a message to be encrypted is an element $h\in H$, while its encryption $g\in G$ is such that $f(g)=h$. A homomorphic cryptosystem allows one to perform computations (operating in a group $G$) with encrypted information (without knowing the original message over $H$). In this paper certain homomorphic cryptosystems are constructed for the first time for non-abelian groups $H$ (earlier, homomorphic cryptosystems were known only in the Abelian case). In fact, we present such a system for any solvable (fixed) group $H$.