Cryptanalysis of a Symmetric Fully Homomorphic Encryption Scheme

Fully homomorphic encryption supports meaningful computations on encrypted data, and hence, is widely used in cloud computing and big data environments. Recently, Li et al. constructed an efficient symmetric fully homomorphic encryption scheme and utilized it to design a privacy-preserving-outsourced association rule mining scheme. Their proposal allows multiple data owners to jointly mine some association rules without sacrificing the data privacy. The security of the homomorphic encryption scheme against the known-plaintext attacks was established by examining the hardness of solving nonlinear systems. However, in this paper, we illustrate that the security of Li et al.'s homomorphic encryption is overvalued. First, we show that we can recover the first part of the secret key from several known plaintext/ciphertext pairs with the continued fraction algorithm. Second, we find that we can retrieve the second part of the secret key through the Euclidean algorithm for the greatest common divisor problem. Experiments on the suggested parameters demonstrate that in case of more than two homomorphic multiplications, all the secret keys of the randomly instantiated Li et al.'s encryption schemes can be very efficiently recovered, and the success probability is at least 98% for one homomorphic multiplication.