Attacking a Levelled Fully Homomorphic Encryption System with Topological Data Analysis

In this paper, we study the Fully Homomorphic Encryption system proposed by Craig Gentry, Amit Sahai, and Brent Waters in [3]. We present a restated version of the proposed cryptosystem, and consider the ciphertexts resulting from the use of this system, to find patterns in them. For this task, we train a machine learning pipeline, utilizing Topological Data Analysis. We show that for secure parameters chosen according to the available literature, this machine learning approach can simply guess what the plain text should have been in a majority of cases (accuracy > 70%), in very good time complexity (< O( \(n^3\) )). This attack was ineffective against the base Learning With Errors (LWE) problem, which hints at a possible flaw somewhere in the reduction from LWE to the cryptosystem.