Squashing

Gentry’s bootstrapping technique is allowed only for the decryption algorithms withsmall depth. Therefore, he used some “tweaks” to reduce the decryption algorithm’s complexity. This method is called squashing and works as follows: First, choose a set of vectors, whose sum equals to the multiplicative inverse of the secret key ((Bj^sk)^-1). If the ciphertext is multiplied by the elements of this set, the polynomial degree of the circuit is reduced to the level that the scheme can handle. The ciphertext is now “bootstrappable”. Nonetheless, the hardness of the recovering the secret key is now based on the assumption of Sparse Subset Sum Problem (SSSP) [Hoffstein et al. 2008]. This basically adds another assumption to the provable security of the scheme.