C code implementing a key recovery attack on the scheme by Li, Galbraith and Ma for fully homomorphic encryption. The LGM scheme uses a list of vectors drawn from a Gaussian distribution as the secret key. The attack tries to recover coefficients from these vectors by asking for many decryptions of the same ciphertexts and using statistical methods to remove the uncertainty introduced by the random elements used in the decryption function.
The program generateEvectors.c is used to sample a number of vectors used as the secret key. This program requires the Discrete Gaussian Sampler library to work. Running the code takes three parameters:
- m: length of each secret key vector.
- t: number of secret key vectors produced.
- sigma: standard deviation for the discrete Gaussian sampler.
The output is a file containing the secret key vectors that can be read by coefficientSearch.c
The main program that simulates LGM decryption and runs the attack trying to recover coefficients from the secret vectors. The program needs a file with the secret key vectors to run, but otherwise only depends on standard C libraries. The program takes seven parameters to run:
-
lambda_max: the maximum value a random lambda_i can take in the decryption function (typically 2 or 3).
-
sample size: the number of decryption queries used for each ciphertext to generate a count of the number of 1-decryptions. Larger values give more accurate results, depending on the length of the secret vectors and the standard deviation used for sampling them.
-
negative: flag that indicates the interval for sampling random lambda-values. 0 means the lambda_i are sampled from [0...lambda_max-1] and 1 means the lambda_i are sampled from [-lambda_max...lambda_max].
-
attacked_vector: which of the secret key vectors e_i to recover, i in [0...t-1].
-
start: which vector in the file to start searching coefficients for.
-
stop: when to stop processing vectors from the file. Start and stop allow for easy parallelization.
-
file: filename of file with secret key vectors.
The program outputs a file with the estimated coefficients and notes the difference with the correct value if the estimate was not correct.