In Gentry's fully homomorphic encryption scheme, a sparse subset sum problem (SSSP) is used and a big set is included in the public key. In the implementation of a variant, to reduce the size of the public key, Gentry and Halevi used a specific form of a SSSP constructed from geometric progressions. In this study, the authors solve Gentry and Halevi's sparse subset sum challenges for the first time. Owing to the aggressive choice of parameters, the process is fairly easy and can be done by simply modifying their lattice‐based attack. Their experiment shows that even a large challenge can be solved within two days. As a second contribution, considering other attacks such as a hybrid attack combining a meet in the middle attack with a lattice‐based attack, they provide a new condition for hard instances of the SSSP from geometric progressions.

Recently, the usage of GPU is not limited to the jobs associated with graphics and a wide variety of applications take advantage of the flexibility of GPUs to accelerate the computing performance. Among them, one of the most emerging applications is the fully homomorphic encryption (FHE) scheme, which enables arbitrary computations on encrypted data. Despite much research effort, it cannot be considered as practical due to the enormous amount of computations, especially in the bootstrapping procedure. In this paper, we accelerate the performance of the recently suggested fast bootstrapping method in FHEW scheme using GPUs, as a case study of a FHE scheme. In order to optimize, we explored the reference code and carried out profiling to find out candidates for performance acceleration. Based on the profiling results, combined with more flexible tradeoff method, we optimized the bootstrapping algorithm in FHEW using GPU and CUDA's programming model. The empirical result shows that the bootstrapping of FHEW ciphertext can be done in less than 0.11 second after optimization.