Article Preview
Top1. Introduction
Several exciting advances for lattice-based public key cryptosystem have been made, including predicate encryptions (Gorbunov, 2015a), the schemes of candidate multilinear maps (Garg, 2013a; Gentry, 2015; Coron, 2013a; Coron, 2015) and their applications (Garg, 2013b; Sahai, 2014), and homomorphic constructions (Gorbunov, 2015b; Gentry, 2009a). Particularly, homomorphic encryption (HE) is such an encryption where the output of the ring operations on the ciphertext space can be decrypted as the output of the corresponding ring operations on the plaintext space. It can be used for secure function evaluation, but the major application is homomorphic service, which is in such a scene. A user needs to obtain the output of the ring-operations on the plaintext space, and he wants to do nothing but decryption. The server implements homomorphic operations on the ciphertext space. That is, the server is given corresponding ciphertexts of input plaintexts, and computes the corresponding ciphertext of the output plaintext. Then the server sends this ciphertext to the user. The user then decrypts this ciphertext to obtain the original output plaintext. If an HE scheme can compute any function of the ciphertexts, then it is known as a Fully Homomorphic Encryption (FHE) scheme. Otherwise, it is referred to as a Somewhat Homomorphic Encryption (SHE) scheme. Recent years have witnessed several exciting advances for FHE, since the breakthrough work of Gentry (Gentry, 2009a; Gentry, 2009b). Smart and Vercauteren presented a novel FHE at PKC 2010 (Smart, 2010) (SV10 scheme for short), in which ciphertexts are integers rather than vectors. Another earliest scheme for FHE over the integers was presented by Dijk et al. (Dijk, 2010) at Eurocrypt 2010. The schemes above that follow Gentry’s blueprint have fairly poor performance. Without using the squashing step, the schemes in (Gentry, 2011a; Brakerski, 2011) begin to make the differences from Gentry’s blueprint for FHE. As shown in (Brakerski, 2011), the authors introduced new way of dimension-modulus reduction to control noise and thus to construct an FHE scheme based on the learning with error (LWE) problem. Soon after, Brakerski et al. (Brakerski, 2012b) made good use of modulus switching technique to obtain an FHE scheme without bootstrapping. Subsequently, the authors of (Brakerski, 2012a; Coron, 2014) gave several FHE schemes without modulus switching. At Crypto 2013 Gentry et al. (Gentry, 2013) used the approximate eigenvector method for building FHE scheme, which has no evaluation keys. This makes their scheme asymptotically faster and helps them construct the first identity-based FHE scheme. As a key technology for achieving FHE, faster bootstrapping is also explored in (Alperin-Sheriff, 2014; Ducas, 2015).