# Generalized ElGamal encryption

The EIGamal encryption scheme is typically described in the setting of the multiplicative group Z*, but can be easily generalized to work in any finite cyclic group G.

As with EIGamal encryption, the security of the generalized EIGamal encryption scheme is based on the intractability of the discrete logarithm problem in the group G. The group G should be carefully chosen to satisfy the following two conditions:

• 1. for efficiency, the group operation in G should be relatively easy to apply; and
• 2. for security’, the discrete logarithm problem in G should be computationally infeasible.

The following is a list of groups that appear to meet these two criteria, of which the first three have received the most attention.

• 1. The multiplicative group Z* of the integers modulo a prime p.
• 2. The multiplicative group of the finite field Wyn of characteristic two.
• 3. The group of points on an elliptic curve over a finite field.
• 4. The multiplicative group F* of the finite field F9, where q = pm, p a prime.
• 5. The group of units Z*, where n is a composite integer.
• 6. The jacobian of a hyperelliptic curve defined over a finite field.
• 7. The class group of an imaginary quadratic number field.
• 8.25 Algorithm Key generation for generalized EIGamal public-key encryption

SUMMARY: each entity creates a public key and a corresponding private key.

Each entity A should do the following:

• 1. Select an appropriate cyclic group G of order n, with generator a. (It is assumed here that G is written multiplicatively.)
• 2. Select a random integer a, 1 < a < n - 1, and compute the group element aa.
• 3. A’s public key is (a, a" ), together with a description of how to multiply elements in G; A’s private key is a.
• 8.26 Algorithm Generalized EIGamal public-key encryption

SUMMARY: В encrypts a message m for A, which A decrypts.

• 1. Encryption. В should do the following:
• (a) Obtain A’s authentic public key (a, a:'1).
• (b) Represent the message as an element m of the group G.
• (c) Select a random integer к, 1 < к < n - 1.
• (d) Compute 7 = a1 and S = m- (aa)k.
• (e) Send the ciphertext c = (7, S) to A.
• 2. Decryption. To recover plaintext m from c, A should do the following:
• (a) Use the private key a to compute 7“ and then compute y~a.
• (b) Recover m by computing (7-0) • S.
• 8.27 Note (common system-wide parameters) All entities may elect to use the same cyclic group G and generator a, in which case a and the description of multiplication in G need not be published as part of the public key (cf. Note 8.20).

8.28 Example (EIGonml encryption using the multiplicative group of F2m, with artificially small parameters)

Key generation. Entity A selects the group G to be the multiplicative group of the finite field F2 j , whose elements are represented by the polynomials over F2 of degree less than 4, and where multiplication is performed modulo the irreducible polynomial f(x) = x4 + x + 1 (cf. Example 2.231). For convenience, a field element азх3 + a2x[1] [2] [3] [4] [5] [6] [7] [8] + ax + a0 is represented by the binary string (a;S«2rti«o). The group G has order n = 15 and a generator is a = (0010).

A chooses the private key a = 7 and computes = a7 = (1011). A's public key is aa = (1011) (together with a = (0010) and the polynomial f(x) which defines the multiplication in G, if these parameters are not common to all entities).

Encryption. To encrypt a message m = (1100), В selects a random integer к = 11 and computes 7 = a11 = (1110), (aa)n = (0100), and S = m ■ (cc®)11 = (0101). В sends 7 = (1110) and S = (0101) to A.

Decryption. To decrypt, A computes 7“ = (0100), (ya)~ l = (1101) and finally recovers m by computing in = (7-0) • <5 = (1100). □

• [1] SUMMARY: each entity creates a public key and a corresponding private key.
• [2] Integers k,n, and t are fixed as common system parameters.
• [3] Each entity A should perform steps 3-7.
• [4] Choose a kxn generator matrix G for a binary (n, /c)-linear code which can correctt errors, and for which an efficient decoding algorithm is known. (See Note 12.36.)
• [5] Select a random к x к binary non-singular matrix S.
• [6] Select a random n x n permutation matrix P.
• [7] Compute the к x n matrix G = SGP.
• [8] A’s public key is (G, t); A’s private key is (S, G, P).