The ElGamal encryption scheme is not only the most extensively used alternative to RSA, but is also almost exclusively used in voting systems as an effective homomorphic encryption scheme. Being easily adaptable to a wide range of cryptographic groups, the ElGamal encryption scheme enjoys homomorphic properties while remaining semantically secure;

ElGamal is an asymmetric encryption scheme that consists of three algorithms: key generation(η), η being a security parameter, encryption E(m, pk) with m being a plaintext and pk a public key, and decryption D(c,sk) where c is a ciphertext and sk is a private key.

The ElGamal encryption scheme is known to be IND-CPA secure under the decisional Diffie-Hellman assumption:

Given two distributions DDH0 = (g^x, g^y, g^xy) and DDH1 = (g^x, g^y, g^z) where x, y,z are randomly distributed in Zq, a cyclic group with generator g. It is hard to distinguish between DDH0 and DDH1.

An encryption scheme is said to be IND-CPA secure if a polynomial time adversary choosing two plaintexts cannot distinguish between the resulting ciphertexts. If the adversary can distinguish between the ciphertexts better than guessing blindly, we say that the adversary achieves an advantage. The advantage of any efficient adversary is expressed as a negligible function of the security parameter in the formal definition of IND-CPA . For ElGamal, the security parameter is the key length.

A key point for the security of the ElGamal encryption scheme resides in the group G and its order. One should start by generating a pair of keys (public and private), then map the message into a group where the Decisional Diffie-Hellman assumption holds.

We use |g| to denote the order of an element g in Zp* (cyclic prime order group) and < g > to denote the cyclic subgroup of Zp* generated by g.

As if all subgroups of a cyclic group are cyclic and if G = is cyclic, then for every divisor d of |G| there exists exactly one subgroup of order d which may be generated. One may rely on this property to form a unique subgroup of quadratic residues elements.

For ElGamal, using a safe prime p = 2q+1, where the order is p−1 = 2q permits to form a subgroup of prime order q that forms the message space we need in order to encrypt messages. One may take advantage of the Lagrange theorem that states that in a finite group G, the order of any subgroup H divides the order of the group, to conclude that the prime order subgroup has no subgroups being prime. Finally, the message space must be restrained to this prime order subgroup.

In the file elgamal.ml, I have already implemented the most important functions as: prime, safe price, generator, safe prime order group and key generation.

In the file elgamal.mli, we can find the types of the functions we will be using.

In file test.ml, we will test if the implementation works or not.