Homomorphic encryption and multilinear maps based on the approximate-GCD problem

Cryptographic schemes are constructed on top of problems that are believed to be hard. In particular, recent advanced schemes, as homomorphic primitives and obfuscators, use the approximate greatest common divisor (AGCD) problem, which is simple to describe and easy to implement, since it does not require complex algebraic structures nor hard-to-sample probability distributions. However, in spite of its simplicity, the AGCD problem generally yields inefficient schemes, usually with large ciphertext expansion.

In this thesis, we analyze the AGCD problem and several existing variants thereof and propose a new attack on the multi-prime AGCD problem. Then, we propose two new variants:
1. The vector AGCD problem (VAGCD), in which AGCD instances are represented as vectors and randomized with a secret random matrix;
2. The polynomial randomized AGCD problem (RAGCD), that consists of representing AGCD samples as polynomials and randomizing them with a secret random polynomial.

We show that these new variants cannot be easier than the original AGCD problem and that all the known attacks, when adapted to the VAGCD and the RAGCD problem, are more expensive both in terms of time and of memory, allowing us then to chose smaller parameters and to improve the efficiency of the schemes using the AGCD as the underlying problem.

Thus, by combining techniques from multilinear maps and indistinguishability obfuscation with the VAGCD problem, we provide the first implementation of a N-party non-interactive key exchange resistant against all known attacks.

Still aiming to show that the VAGCD problem can lead to performance improvements in cryptographic primitives, we use it to construct a homomorphic encryption scheme that can natively and efficiently operate with vectors and matrices. For instance, for 100 bits of security, we can perform a sequence of 128 homomorphic products between 128-dimensional vectors and 128x128 matrices in less than one second. We also use our scheme in two applications: homomorphic evaluation of nondeterministic finite automata and a Naïve Bayes classifier.

Finally, using the RAGCD problem, we construct a new homomorphic scheme for polynomials and we propose new fast bootstrapping procedures for fully homomorphic scheme (FHE) over the integers. Therewith, we can for the first time bootstrap AGCD-based FHE schemes in less than one second in a common personal computer. For the best of our knowledge, only FHE schemes based on the LWE problem had subsecond bootstrapping procedures, while AGCD-based schemes required several seconds or even minutes to be bootstrapped.