Class: ElGamal

The El Gamal cryptosystem implemented on top of verificatum.arithm.PGroup. This is a generalized implementation in several ways and eliminates the complexity that plagues other implementations by proper abstractions.

The first generalization allows us to use multiple El Gamal public keys in parallel. The second allows us to define and implement the Naor-Yung cryptosystem directly from the El Gamal cryptosystem and a proof equal exponents (see verificatum.crypto.ElGamalZKPoK). The third generalizes the cryptosystem to any width of plaintexts, i.e., lists of plaintexts or equivalently elements of product groups.

• The first generalization is captured by letting the underlying group G be of the form G = H^k, where H is a group of prime order q and k > 0 is the key width, and the private key is contained in the ring of exponents R = (Z/qZ)^k of G, where Z/qZ is the field of prime order q.
• In the standard cryptosystem the private key is an element x of R, and the public key has the form (g, y), where g is an element of G and y = g^x. In the second generalization we instead allow the public key to be an element ((g, h), y) of (G x G) x G, but still define y = g^x with x in R. Here h can be defined as h = y^z for a random z in R.

  The standard cryptosystem defines encryption of a message m in G as Enc((g, y), m, r) = (g^r, y^r * m), where r is randomly chosen in R. We generalize encryption by simply setting Enc(((g, h), y), m, r) = ((g^r, h^r), y^r * m). Note that the same exponent r is used for all three exponentiations and that it resides in R.

  The standard cryptosystem defines decryption of a ciphertext (u, v) by Dec(x, (u, v)) = v / u^x. In the generalized version a decryption is defined by Dec(x, ((u, a), v)) = v / u^x.

• We generalize the cryptosystem to allow encryption of plaintexts m of width w contained in G' = G^w, or equivalently lists of plaintexts in G. A simple way to accomplish this with a proper implementation of groups (see verificatum.arithm.PGroup) is to simply widen public and secret keys.
  1. The original secret key is replaced by x' = (x, x,..., x) in R' = R^w.
  2. A public key (g, y) in G x G is replaced by (g', y'), where y' = (g, g,..., g) and y' = (y, y,..., y) are elements in G'. Thus, the new public key is contained in G' x G'.
  3. A public key ((g, h), y) in (G x G) x G is replaced by a wider public key ((g', h'), y'), where g', and y' are defined as above and h' is defined accordingly. Thus, the new public key is contained in (G' x G') x G'.