Key-Recovery Attacks Against Somewhat Homomorphic Encryption Schemes

Doctoral thesis (2017)

In 1978, Rivest, Adleman and Dertouzos introduced the concept of privacy homomorphism and asked whether it is possible to perform arbitrary operations on encrypted ciphertexts. Thirty years later, Gentry ... [more ▼]

In 1978, Rivest, Adleman and Dertouzos introduced the concept of privacy homomorphism and asked whether it is possible to perform arbitrary operations on encrypted ciphertexts. Thirty years later, Gentry gave a positive answer in his seminal paper at STOC 2009, by proposing an ingenious approach to construct fully homomorphic encryption (FHE) schemes. With this approach, one starts with a somewhat homomorphic encryption (SHE) scheme that can perform only limited number of operations on ciphertexts (i.e. it can evaluate only low-degree polynomials). Then, through the so-called bootstrapping step, it is possible to turn this SHE scheme into an FHE scheme. After Gentry's work, many SHE and FHE schemes have been proposed; in total, they can be divided into four categories, according to the hardness assumptions underlying each SHE (and hence, FHE) scheme: hard problems on lattices, the approximate common divisor problem, the (ring) learning with errors problem, and the NTRU encryption scheme. Even though SHE schemes are less powerful than FHE schemes, they can already be used in many useful real-world applications, such as medical and financial applications. It is therefore of primary concern to understand what level of security these SHE schemes provide. By default, all the SHE schemes developed so far offer IND-CPA security - i.e. resistant against a chosen-plaintext attack - but nothing is said about their IND-CCA1 security - i.e. secure against an adversary who is able to perform a non-adaptive chosen-ciphertext attack. Considering such an adversary is in fact a more realistic scenario. Gentry emphasized it as a future work to investigate SHE schemes with IND-CCA1 security, and the task to make some clarity about it was initiated by Loftus, May, Smart and Vercauteren: at SAC 2011 they showed how one family of SHE schemes is not IND-CCA1 secure, opening the doors to an interesting investigation on the IND-CCA1 security of the existing schemes in the other three families of schemes. In this work we therefore continue this line of research and show that most existing somewhat homomorphic encryption schemes are not IND-CCA1 secure. In fact, we show that these schemes suffer from key recovery attacks (stronger than a typical IND-CCA1 attack), which allow an adversary to completely recover the private keys through a number of decryption oracle queries. As a result, this dissertation shows that all known SHE schemes fail to provide IND-CCA1 security. While it is true that IND-CPA security may be enough to construct cryptographic protocols in presence of semi-honest attackers, key recovery attacks will pose serious threats for practical usage of SHE and FHE schemes: if a malicious attacker (or a compromised honest party) submits manipulated ciphertexts and observes the behavior (side channel leakage) of the decryptor, then it may be able to recover all plaintexts in the system. Therefore, it is very desirable to design SHE and FHE with IND-CCA1 security, or at least design them to prevent key recovery attacks. This raises the interesting question whether it is possible or not to develop such IND-CCA1 secure SHE scheme. Up to date, the only positive result in this direction is a SHE scheme proposed by Loftus et al. at SAC 2011 (in fact, a modification of an existing SHE scheme and IND-CCA1 insecure). However, this IND-CCA1 secure SHE scheme makes use of a non standard knowledge assumption, while it would be more interesting to only rely on standard assumptions. We propose then a variant of the SHE scheme proposed by Lopez-Alt, Tromer, and Vaikuntanathan at STOC 2012, which offers good indicators about its possible IND-CCA1 security. [less ▲]

On Key Recovery Attacks against Existing Somewhat Homomorphic Encryption Schemes

in Progress in Cryptology - LATINCRYPT 2014, Florianópolis 17-19 September 2014 (2014)

In his seminal paper at STOC 2009, Gentry left it as a future work to investigate (somewhat) homomorphic encryption schemes with IND-CCA1 security. At SAC 2011, Loftus et al. showed an IND-CCA1 attack ... [more ▼]

In his seminal paper at STOC 2009, Gentry left it as a future work to investigate (somewhat) homomorphic encryption schemes with IND-CCA1 security. At SAC 2011, Loftus et al. showed an IND-CCA1 attack against the somewhat homomorphic encryption scheme presented by Gentry and Halevi at Eurocrypt 2011. At ISPEC 2012, Zhang, Plantard and Susilo showed an IND-CCA1 attack against the somewhat homomorphic encryption scheme developed by van Dijk et al. at Eurocrypt 2010. In this paper, we continue this line of research and show that most existing somewhat homomorphic encryption schemes are not IND-CCA1 secure. In fact, we show that these schemes suffer from key recovery attacks (stronger than a typical IND-CCA1 attack), which allow an adversary to recover the private keys through a number of decryption oracle queries. The schemes, that we study in detail, include those by Brakerski and Vaikuntanathan at Crypto 2011 and FOCS 2011, and that by Gentry, Sahai and Waters at Crypto 2013. We also develop a key recovery attack that applies to the somewhat homomorphic encryption scheme by van Dijk et al., and our attack is more efficient and conceptually simpler than the one developed by Zhang et al.. Our key recovery attacks also apply to the scheme by Brakerski, Gentry and Vaikuntanathan at ITCS 2012, and we also describe a key recovery attack for the scheme developed by Brakerski at Crypto 2012. [less ▲]