Cryptanalysis of an Unbounded Fully Homomorphic Encryption Scheme †

Gentry’s original blueprint for the construction of fully homomorphic encryption (FHE) starts from a somewhat homomorphic encryption scheme, that supports the homomorphic evaluation of arithmetic circuits of moderate multiplicative depth up to L, and whose decryption circuit itself can furthermore be “squashed” to a multiplicative depth less than L. Then, the homomorphic evaluation of this squashed decryption circuit, called bootstrapping, transforms any ciphertext into a ciphertext supporting at least one extra level of multiplication, enabling the homomorphic evaluation of arbitrary arithmetic circuits. Bootstrapping is the cornerstone of Gentry’s breakthrough. Unfortunately, it introduces substantial overhead that limits the efficiency of most FHE schemes so far. Consequently, numerous attempts have been made to circumvent the bottleneck of bootstrapping by directly constructing encryption schemes that support the evaluation of circuits of unbounded depth, e.g., by avoiding ciphertext noise, the randomness present in Gentry-like somewhat homomorphic schemes that grows after each homomorphic multiplication. Noise effectively limits the depths of supported circuits, as ciphertexts fail to correctly decrypt when noise size exceeds a certain threshold. Most attempts to achieve noiseless FHE schemes have proved insecure, however. In this paper, we take a closer look at a recent construction along those lines due to Zhang et al.’s unbounded FHE scheme, and show that it is no exception. We show that it is susceptible to an efficient full key recovery attack, and moreover that ciphertexts can be decrypted faster with the public parameters alone than the time it takes to generate the public key.