On non-abelian homomorphic public-key cryptosystems

Dima Grigoriev

IRM, Université de Rennes Beaulieu, 35042, Rennes, France

dima@maths.univ-rennes1.fr

Ilia Ponomarenko

Steklov Institute of Mathematics, Fontanka 27, St. Petersburg 191011, Russia

                                           inp@pdmi.ras.ru

Abstract

An important problem of modern cryptography concerns secret public-key computations in algebraic structures. We construct homomorphic cryptosystems being (secret) epimorphisms f : G → H, where G, H are groups and H is finite. A letter of a message to be encrypted is an element h ∈ H, while its encryption g ∈ 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 for abelian groups H). In addition, a cryptosystem is designed for performing operations over a finite ring.

1 Definitions

In what follows all the groups are presented in a some natural way depending on the problem. For example, the special constructions of Section 3 are based on the groups ℤ_{n}^{+} and ℤ_{n}^{∗} just given via n, whereas the general construction of Section 2 requires only that the multiplication and taking the inverse in the group in question could be performed efficiently. In the latter case the groups can be presented by generators and relations or even by generic algorithms (see e.g. [8]).

There is a lot of public-key cryptosystems using groups (see e.g. [1, 6, 7, 9]) but only a few of them have a homomorphic property in the sense of the following definition.

Definition 1.1 Let H be a finite group. A triple S = (G, H, f(R, P, A)) where G is a finitely generated group, f = f(R, P, A) is an epimorphism from G onto H, R ⊂ G is a set of distinct representatives of the left cosets of G by ker(f) and P is a surjection from the set A to the group ker(f), is called a homomorphic cryptosystem over H if the following condition are satisfied:

(1) appropriate presentations of A and of the groups G and H are of size O(N) for some N ∈ ℕ;

(2) in these presentations one can get random elements and compute the inverse of the element (in a group G or H, respectively) and the product of two elements in probabilistic polynomial time on N;

(3) |R| = |H| and the images of the elements of R with respect to f are given explicitely;

(4) the mapping P is a trapdoor function.

Condition (4) means (see [5]) that the values of P can be computed in probabilistic polynomial time on N, whereas finding of the inverse mapping P^{−1} is a hard computational problem which can be solved by means of some additional secret information (for instance, knowing some invariant of the group G). In a homomorphic cryptosystem S the elements of H are encoded by the elements of G, all the computations are performed in G and the result is decoded to H. More exactly:

Public Key: G, H, P, R, A, f|_{R}.

Secret Key: finding P^{−1}.

Encryption: given h ∈ H take g ∈ R such that f(g) = h, and a random element g_{0} ∈ ker(f); the ciphertext of h is the element g_{0}g ∈ G.

Decryption: given g ∈ G find the elements g′ ∈ R and a ∈ A such that g′g^{−1} = P (a); set f(g) = f(g′).

One can see that the encryption procedure can be performed by means of public keys efficiently. However, the decryption procedure is a secret one in the following sense. To find the element g′ one in fact has to solve the membership problem for ker(f) in G. We assume that a solution for each instance g ∈ ker(f) of this problem must have a “proof”, which is actually an element a ∈ P^{−1}(g). Thus, the secrecy of the system is based on the assumption that finding P^{−1} is an intractable computation problem. On the other hand, our ability to compute P^{−1} enables to efficiently implement the decryption algorithm. One can treat P as a proof system for ker(f) in the sense of [2].

Definition 1.2 G_{crypt} is the class of all finite groups H for which there exists a homomorphic cryptosystem over H.

In the context of our definition of a homomorphic cryptosystem the main problem is to describe the class G_{crypt}. To our knowledge at present all known homomorphic cryptosystems (G, H, f(R, P, A)) are more or less modifications of the following one with

G = {g ∈ ℤ_{n}^{∗} : J_{n}(g) = 1}, H = ℤ_{2}^{+}, ker(f) = {g^{2} : g ∈ G}, A = G, P (g) : g ↦ g^{2}

where n = pq with p, q being distinct large primes of size N = O(log n), J_{n} is the Jacobi symbol and R is a random set of representatives of cosets of G by ker(G) (see [5]). We call it the quadratic residue system. It can be proved (see [5]) that in this case finding P^{−1} is not easier than factoring n, whereas given p and q the computation of P^{−1} can be done in polynomial time in N.

Remark 1.3 It should be mentioned that a cryptosystem from [11] with G = ℤ_{n^{2}}^{∗}, H = ℤ_{n}^{+}, ker(f) = {g^{n} : g ∈ G}, A = G, P : g ↦ g^{n} and the same assumptions on n and N as in the quadratic residue system, is not homomorphic in the sense of Definition 1.1 because condition (3) of it does not hold. By the same reason the cryptosystem from [10] with G = ℤ_{p^{2}q}^{∗}, H = ℤ_{p}^{+}, and ker(f) = {g^{pq} : g ∈ G} is also not homomorphic (besides, in this system only a part of the group H is encoded).

2 Free products

Let us describe a construction producing new homomorphic cryptosystems from the old ones. To do this we recall some facts concerning the free products of groups. Let G_{i} = ⟨X_{i}; S_{i}⟩ be a group given by the set X_{i} of generators and the set S_{i} of relations, i = 1, 2. Without loss of generality we assume that X_{1} ∩ X_{2} = ∅. Then the free product G_{1} ∗ G_{2} of groups G_{1} and G_{2} is a group given by the presentation ⟨X_{1} ∪ X_{2}; S_{1} ∪ S_{2}⟩. In particular, G_{1} and G_{2} are the subgroups of G_{1} ∗ G_{2}. If X_{1} = G_{1} and X_{2} = G_{2} then, obviously, any element of the group G_{1} ∗ G_{2} can be reduced to the word in which no two adjacent letters belong to the same set among the sets X_{1}, X_{2}.

From the definition it follows that given epimorphisms f_{i} : G_{i} → H_{i}, i = 1, 2, there exists the uniquely determined epimorphism

f_{1} ∗ f_{2} : G_{1} ∗ G_{2} → H_{1} ∗ H_{2}  (1)

such that f_{1} ∗ f_{2}|_{G_{i}} = f_{i} for i = 1, 2 (we assume that H_{1} ∩ H_{2} = ∅). Set G_{0} = ker(f_{1}) ∗ ker(f_{2}). Then

ker(f_{1} ∗ f_{2}) = ⟨{x^{−1}G_{0}x : x ∈ X_{1} ∪ X_{2}, i = 1, 2}⟩  (2)

(it is the minimal normal subgroup of G_{1} ∗ G_{2} containing ker(f_{1}) and ker(f_{2})). The following statement reflects the fact that given generators of the groups ker(f_{1}) and ker(f_{2}) the elements of ker(f_{1} ∗ f_{2}) can be efficiently recognized in the group G_{1} ∗ G_{2}.

Lemma 2.1 Let A_{i} be a set and P_{i} : A_{i} → ker(f_{i}), i = 1, 2, be a polynomial-time computable surjection. Set A to be the set of all words in the alphabet A_{1} ∪ A_{2} ∪ G_{1} ∪ G_{2}. Then there exists a polynomial-time computable surjection P = P (G_{1}, G_{2}, f_{1}, f_{2}) from A onto ker(f) where f = f_{1} ∗ f_{2}, such that P |_{A_{i}} = P_{i}, i = 1, 2.

Proof. Let us define a mapping P : A → ker(f) recursively. Let w ∈ A. If w is the empty word, then set P (w) = 1_{G} where G = G_{1} ∗ G_{2}. If w = w′x for some w′ ∈ A and x ∈ A_{1} ∪ A_{2} ∪ G_{1} ∪ G_{2}, then set

P (w) = \{ \begin{matrix}P (w′)P_{i}(x), & if x ∈ A_{i}, i = 1, 2, \\ P (x^{−1})P (w′)P (x), & otherwise. \end{matrix}

Now, from (2) it follows that P (A) ⊂ ker(f_{1} ∗ f_{2}). Moreover, the mapping P is efficiently computable whenever so are P_{1} and P_{2}. On the other hand, from (2) it follows that any element g ∈ ker(f_{1} ∗ f_{2}) can be uniquely represented in the form

g = g_{1}^{−1}k_{1}g_{1} ⋯ g_{s}^{−1}k_{s}g_{s}, g_{i} ∈ X^{∗}, k_{i} ∈ G_{0}

where X^{∗} is the set of all words over the alphabet consisting of letters belonging to the sets G_{i} \ ker(f_{i}), i = 1, 2. Assume by induction that g_{1}^{−1}k_{1}g_{1} ⋯ g_{s−1}^{−1}k_{s−1}g_{s−1} = P (w′) for some w′ ∈ A. Then for w = w′g_{s}^{−1}a_{s}g_{s} with a_{s} being the word of (A_{1} ∪ A_{2})^{∗} such that P (a_{s}) = k_{s}, we have

P (w) = g_{s}^{−1}P (w′g_{s}^{−1}a_{s})g_{s} = g_{s}^{−1}P (w′g_{s}^{−1})k_{s}g_{s} = g_{s}^{−1}g_{s}P (w′)g_{s}^{−1}k_{s}g_{s} = g.

Thus the mapping P is a surjection and we are done.

We need one more special homomorphism of a free product. Suppose that a finite group H is a semidirect product of a group H_{1} by a group H_{2}. Below we identify the group H_{i} with the corresponding subgroup of H, i = 1, 2, and the elements of H with the words xy, x ∈ H_{1}, y ∈ H_{2}. Then there exists a natural epimorphism

f(H_{1}, H_{2}) : H_{1} ∗ H_{2} → H  (3)

such that f|_{H_{i}} = id_{H_{i}}, i = 1, 2, and

ker(f) = ⟨{xyz^{−1} : x, y, z ∈ H, xy = z}⟩  (4)

where f = f(H_{1}, H_{2}). Set P (H_{1}, H_{2}) to be the identity mapping of the set A(H_{1}, H_{2}) = ker(f).

Let us describe the construction showing that the class G_{crypt} is closed with respect to semidirect produts. Let S_{i} = (G_{i}, H_{i}, f(R_{i}, P_{i}, A_{i})) be a homomorphic cryptosystem over a group H_{i} with G_{i} being a finite group, i = 1, 2. Suppose that a group H is a semidirect product of H_{1} by H_{2}. Set

G = G_{1} ∗ G_{2}, f = (f_{1} ∗ f_{2})f(H_{1}, H_{2}), A = A(G_{1}, G_{2}, f_{1}, f_{2}) × A(H_{1}, H_{2})

where f_{i} = f(R_{i}, P_{i}, A_{i}), i = 1, 2. Then due to the above definitions the mapping f : G → H is an epimorphism. Moreover, the group ker(f) contains the subgroup ker(f_{1} ∗f_{2}) which is normal in G. So ker(f) = ker(f_{1} ∗ f_{2}) ker(f(H_{1}, H_{2})). Thus the mapping

P : A → ker(f), (a, b) ↦ P′(a)P′′(b)

where P′ = P (G_{1}, G_{2}, f_{1}, f_{2}) and P′′ = P (H_{1}, H_{2}), is a polynomial-time computable surjection by Lemma 2.1. We claim that S = (G, H, f(R, P, A)) where R = R_{1}R_{2}, is a homomorphic cryptosystem over the group H. Indeed, the first three conditions of the definition are trivially satisfied. Thus it suffices to verify that the mapping P is a trapdoor function. However, from the definition of the surjection P it follows that the restriction of P to A_{i} × {1} equals P_{i}, i = 1, 2. So the problem of finding P_{i}^{−1}(g) with g ∈ ker(f_{i}) is a special case of the problem of finding P^{−1}(g) with g ∈ ker(f). On the other hand, the mapping (P′′)^{−1} is obviously polynomial time computable. So, to find P^{−1}(g) for g ∈ ker(f), it suffices to find (P′)^{−1}(g) with g ∈ ker(f_{1} ∗ f_{2}). Since the latter problem is obviously polynomial time reducible to finding P_{i}^{−1}(g) with g ∈ ker(f_{i}), one can find P^{−1}(g) by using a trapdoor information for P_{i}, i = 1, 2.

The above construction can be easily generalized to a finite set of homomorphic cryptosystems. Thus we obtain the following statement.

Theorem 2.2 Let {H_{1}, …, H_{k}} be a set of finite groups from G_{crypt} for some fixed k ∈ ℕ. Then any group H = H_{1} ⋯ H_{k} such that the group (H_{1} ⋯ H_{i})H_{i+1} is a semidirect product of H_{1} ⋯ H_{i} by H_{i+1}, i = 1, …, k − 1, belongs to the class G_{crypt}.

The special cases of a semidirect product are the direct and wreath products. (In the latter case the resulting group is a semidirect product of the direct power of the first group by the second group which acts on the product by permutations of direct factors, see e.g. [12]). Thus from Theorem 2.2 we obtain the following statement.

Corollary 2.3 The class G_{crypt} is closed under taking direct and wreath products.

3 Explicit constructions

In this section we present an explicit homomorphic cryptosystem over a cyclic group which is in a sense a generalization of the quadratic residue cryptosystem over ℤ_{2}. Given m, N ∈ ℕ set

D_{N,m} = {n ∈ ℕ : n = pq, p, q are primes, |p| = |q| = N, m|p − 1, GCD(m, q − 1) = 1}.

From the Dirichlet’s theorem on primes in arithmetic progressions [3] it follows that given m ∈ ℕ, m > 2, the set D_{N,m} is not empty for sufficiently large numbers N.

Let n ∈ D_{N,m} for some natural numbers N and m > 2. Then the group G = ℤ_{n}^{∗} has a normal subgroup G_{0} = {g^{m} : g ∈ G} the factor by which is isomorphic to the group H = ℤ_{m}^{+}. Denote by f the corresponding epimorphism from G to H. The mapping P : A → G_{0} with A = G taking g ∈ G to g^{m} is obviously a polynomial time computable surjection (end even epimorphism). Next, any element of the set

R_{m,n} = {(g_{0}, …, g_{m−1}) : g_{i} ∈ G, G_{0}g_{i} ≠ G_{0}g_{j} for i ≠ j}

is a system of distinct representatives of the cosets of G by G_{0}. Now we claim that the triple S_{N,m,n} = (G, H, f(R, P, A)) with randomly chosen R ∈ R_{m,n} is a homomorphic cryptosystem over H whenever the following statement is true:

Assumption (*). The problem P(m), of finding the m-root in ℤ_{n}^{∗} for n ∈ D_{N,m} given a random element R ∈ R_{m,n} is not easier than the same problem without any such R.

Again conditions (1), (2), (3) of the definition of a homomorphic cryptosystem are trivially satisfied. In fact, all we need follows from the lemma below.

Lemma 3.1 Let m, N ∈ ℕ, m > 2, and n ∈ D_{N,m}. Then

(1) given primes p and q such that n = pq and a number g ∈ ℤ_{n}^{∗} being m-power, one can find an m-root of g in probabilistic polynomial time in N;

(2) the factoring problem for n is probabilistic polynomial time reducable to the problem of finding the m-root in ℤ_{n}^{∗}.

Proof. Throughout the proof we will identify ℤ_{n}^{∗} with ℤ_{p}^{∗} ×ℤ_{q}^{∗}. To prove statement (1) we make use Rabin’s probabilistic polynomial-time algorithm for finding roots of polynomials over finite prime fields (see [13]). Namely, given p, q and an m-power element g ∈ ℤ_{n}^{∗} we proceed as follows:

Step 1. Find the numbers g_{p} ∈ ℤ_{p}^{∗} and g_{q} ∈ ℤ_{q}^{∗} such that g = g_{p}g_{q}.

Step 2. By Rabin’s algorithm (for a prime field) find the roots h_{p} ∈ ℤ_{p}^{∗} and h_{q} ∈ ℤ_{q}^{∗}

of the polynomials x^{m} − g_{p} and x^{m} − g_{q}.
Step 3. Output h = h_{p}h_{q}.

Since, obviously, h^{m} = h_{p}^{m}h_{q}^{m} = g_{p}g_{q} = g, statement (1) is proved. To prove statement (2) suppose that we are given a probabilistic polynomial-time algorithm Q_{n} that given g ∈ ℤ_{n}^{∗} computes an m-root Q_{n}(g) of g. The following procedure using well-known observations [5] shows how Q_{n} helps to find the numbers p and q.

Step 1. Randomly choose x ∈ ℤ_{n}^{∗}.

Step 2. Set y = Q(x^{m}). If x = y, then go to Step 1.

Step 3. Output q = GCD(xy^{−1} − 1, n) and p = n/q.

Let x = x_{p}x_{q} and y = y_{p}y_{q} where x_{p}, y_{p} ∈ ℤ_{p}^{∗} and x_{q}, y_{q} ∈ ℤ_{q}^{∗}. Since GCD(q − 1, m) = 1 and x_{q}^{m} = y_{q}^{m}, we conclude that x_{q} = y_{q}, So

xy^{−1} = (x_{p}x_{q})/(y_{p}x_{q}) = x_{p}/y_{p} = 1 (mod q).

Thus xy^{−1} − 1 is a multiple of q. To complete the proof we note that since m = O(1), the loop of Steps 1,2 terminates with a large probability after a polynomial number of iterations.

Unfortunately, we don’t know how to apply this lemma without assumption (*) because in our case the system S_{N,m,n} includes the set R ∈ R_{m,n}. However, from it we obtain the following statement.

Theorem 3.2 Under assumption (*) the triple S_{N,m,n} for m > 2 is a homomorphic cryptosystem over ℤ_{m}^{+}; in particular, ℤ_{m}^{+} ∈ G_{crypt} for all m > 1.

We complete the section by mentioning that S_{N,m,n} can be slightly modified to avoid the applying of Rabin’s algorithm for finding roots of polynomials over finite fields. In principle, to implement the decryption algorithm it suffices to determine whether a given number g ∈ G belongs to the group G_{0} or not. However, this can be done by observing that g ∈ G_{0} iff g_{p}^{(p−1)/m} = 1 (mod p).

4 Cryptosystems over finite rings

The results of this paper can be applied to implement secure circuit evaluation introduced by Yao in [15]. To do this we construct a cryptosystem for secure computations over finite fields and the rings ℤ_{n}, n ∈ ℕ. An alternative approach can be found in [14] (see also [4] where the problem of constructing a homomorphic cryptosystem over rings was posed).

Let F be a finite field. Set H to be the semidirect product of the additive group F^{+} of F by its multiplicative group F^{∗}. Since the group F^{+} is a direct product of cyclic groups and the group F^{∗} is cyclic itself, we conclude by Theorems 2.2 and 3.2 that H ∈ G_{crypt}. Thus there exists a homomorphic cryptosystem S(F) over the group H. On the other hand, any computation in F can be performed in the group H. Indeed, given a, b ∈ F one can find the sum a + b (resp. the product ab if ab ≠ 0) in F by computing the product of translations x + a and x + b (resp. linear functions ax and bx) in the group H considered as the group of affine functions over F. This shows that the cryptosystem S(F) enables us to perform secret computations in a finite field. The similar trick with H = ℤ_{n}^{+}ℤ_{n}^{∗} can be used to construct a cryptosystem for secret computations in the rings ℤ_{n}.

5 Conclusions

From Theorems 2.2 and 3.2 it follows that the class G_{crypt} contains all finite groups which can be constructed from cyclic groups by taking semidirect products. In particular, there are homomorphic cryptosystems over the dihedral groups (which are semidirect products of a cyclic group with ℤ_{2}) and so over symmetric groups Sym(n) for n = 2, 3. Moreover, by Corollary 2.3 all elementary Abelian groups belong to G_{crypt}. So there exists a homomorphic cryptosystem over the group Sym(4) ≈ ((ℤ_{2} × ℤ_{2})ℤ_{3}^{+})ℤ_{2}. It would be interesting to construct a homomorphic cryptosystem over an arbitrary symmetric group.

Acknowledgements. The authors would like to thank the Max-Planck Institut fuer Mathematik (Bonn) during the stay in which this paper was done; also Eberhard Becker who has drawn the authors attention to homomorphic cryptosystems and Igor Shparlinski for useful discussions.

References

[1] J. Benaloh, Dense probabilistic encryption, First Ann. Workshop on Selected Areas in Cryptology, 1994, 120–128.

[2] S. Cook, R. A. Reckhow, The relative efficiency of propositional proof systems, J. Symbolic Logic, 44 (1979), 36–50.

[3] H. Davenport, Multiplicative number theory, Springer, 1980.

[4] J. Feigenbaum, M. Merritt, Open questions, talk abstracts, and summary of discussions, DIMACS series in discrete mathematics and theoretical computer science, 2 (1991), 1–45.

[5] S. Goldwasser, M. Bellare, Lecture Notes on Cryptography, http://wwwcse.ucsd.edu/users/mihir/papers/gb.html, 2001.

[6] K. H. Ko, S. J. Lee, J. H. Cheon, J. W. Han, J. Kang, C. Park, New public-key cryptosystem using braid groups, Lecture Notes in Computer Science, 1880 (2000), 166–183.

[7] K. Koyama, U. Maurer, T. Okamoto, S. Vanstone, New public-key schemes based on elliptic curves over the ring ℤ_{n}, Lecture Notes in Computer Science, 576 (1991), 252–266.

[8] U. Maurer, S. Wolf, Lower bounds on generic algorithms in groups, Lecture Notes in Computer Science, 1403 (1998), 72–84.

[9] D. Naccache, J. Stern, A new public key cryptosystem based on higher residues, Proc. 5th ACM Conference on Computer and Communication Security, 1998, 59–66.

[10] T. Okamoto, S. Uchiyama, A New Public-Key Cryptosystem as Secure as Factoring, Lecture Notes in Computer Science, 1403 (1998), 308–317.

[11] P. Paillier, Public-Key Cryptosystem Based on Composite Degree Residuosity Classes, Lecture Notes in Computer Science, 1592 (1999), 223-238.

[12] D. S. Passman, Permutation groups, W.A.Benjamin, Inc., New-York-Amsterdam, 1968.

[13] M. O. Rabin, Probabilistic algorithms in finite fields, SIAM J. Comput., 9 (1980), 273–280.

[14] T. Sander, A. Young, M. Young, Non-interactive cryptocomputing for NC^{1}, Proc. 40th IEEE Symp. Found. Comput. Sci, 1999, 554–566.

[15] A. Yao, How to generate and exchange secrets, Proc. 27th IEEE Symp. Found. Comput. Sci, 1986, 162–167.