# Deliverable 4

**Description:** Implement a homomorphic encryption by reading relevant papers and coding a working encryption mechanism. The methodology chosen is Pailler encryption, which is a partial homomorphic encryption scheme

**Implementation steps:**

- Generate a public-private key pair
- Encrypt a number
- Decrypt a number

** Working of key generation function: **

- Pick two large prime numbers p and q randomly and independently
- Confirm that gcd of pq and product of 1-p and 1-q is 1. This property is assured if both primes are of equal length
- Compute n is product of p and q and the lambda is the lcm of p-1 and q-1
- Pick a random integer g in the set of integers from 1 to n2
- Define function L which is division of x-1 by n
- Calculate multiplicative modulo inverse mu. If it doesn't exist, choose new p and q and repeat
- The public key is n and g
- The private key is lambda and mu
- Prove the homomorphic properties of paillier encryption scheme

** Working of encryption function: **

- Encryption can work for any m in the range 0 to n
- Select random number r such that r value is between 0 and n
- Compute ciphertext as pow(g, m) * pow(r, n) * mod n^2

** Working of decryption function: **

Decrypt ciphertext using L(pow(c, lambda) * mod n^2) * mu * mod n

** Results **