ElGamal

What's included

• ElGamal (Multiplicative)
• Modified ElGamal (Additive)
• Threshold Encryption (m-of-n)
• Elliptic Curve El Gamal
• Zero Knowledge Proof of Correct Encryption (Honest Verfier)

Introduction

The ElGamal Cryptosystem is an asymmetric public key encryption scheme based on the Diffie-Hellman key exchange. Its security is based on the intractability of computing discrete logarithms for a large prime modulus. While ElGamal is naturally multiplicatively homomorphic, a modification to the message structure can be made to result in an additively homomorphic scheme (modified ElGamal).

Implementation

Key Generation

• Generate a safe prime p, alternatively generate a Sophie Germain q such that p = 2q + 1 and both p & q primes.
• Find a generator, g such that it will generate the cyclic group G with order q and not any other subgroup of where is the list of invertible elements less than q, i.e (1,..,q-1). Helpful link
• Calculate
• The public key is < p,q,g,y >
• The private key is

Encryption

• Randomly select an
• Encrypt a plaintext to a corresponding ciphertext where and

Modified ElGamal

• In the modified ElGamal

Decryption

• Decrypt some ciphertext using the private key x and computing where indicates the modular multiplicative inverse

Modified ElGamal

• In the modified ElGamal, decryption involves solving for the discrete log . While normally intractable the discrete log is feasible for small values of m . Current implementation is a brute force search although will probably move to Pollard's kangaroo algorithm when I find the time.

Threshold Encryption

Shamir Secret Sharing (SSS)

• The basic idea of SSS is a polynomial of degree n can be uniquely identified by (n-1) distinct points. By using Lagrange polynomials we can guarantee that the for a set of points the lowest degree polynomial is in fact unique.

Threshold Decryption

• To use threshold encryption, each owner of a key split calculates the partial decryption where is the private key of their split
• The plaintext message can then be recovered from the partial decryption using where S is the set of sufficient partial decryptions and

Incorporating Zero Knowledge Proofs

Non Interactive Proof of Knowledge of Discrete logarithms

• Each owner of a key,, also calculates a verification key
• Based on the Protocol but extended for two logarithms, each partial decryption is accompanied by a proof of correct decryption using a zero-knowledge proof of equality of discrete logarithms ()
• The normally interactive proof is made non-interactive using the Fiat-Shamir heurtistic where the collision-resistant hashing function used in this case is SHA256