On non-Abelian homomorphic public-key cryptosystems

An important problem of modern cryptography concerns secret public-key computations in algebraic structures. We construct homomorphic cryptosystems, which are (secret) epimorphisms f : G H, where G and H are (publically known) groups and H is finite. A letter of a message to be encrypted is an element h H, while its encryption is an element g G such that f(g) = h. A homomorphic cryptosystem allows one to perform computations (in the group G) with encrypted information (without knowing the original message over H).In this paper, 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 (fixed) solvable group H. Bibliography: 24 titles.Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 293, 2002, pp. 39–58.This revised version was published online in April 2005 with a corrected cover date and article title.