Compressible Multi-Key And Multi-Identity Fully Homomorphic Encryption Schemes

With the development of new computing models such as cloud computing,users' data is at risk of being leaked.How to protect users' data privacy and how to realize trusted data storage and operation on an untrusted third party? Fully homomorphic encryption(FHE)provides a possible way to fundamentally solve the problem.FHE enables the third party to directly operate the ciphertexts,with the results being the same as the results of operating on the corresponding plaintexts.In 2009,Gentry proposed the first FHE scheme.After that,its inefficiency has always been a bottleneck of the development of practical schemes and applications.At TCC 2019,Gentry and Halevi proposed the first compressible FHE scheme that enables the ratio of plaintext size to the ciphertext size(i.e.,the compression rate)to reach to 1-? for any small ? > 0 under the standard learning with errors(LWE)assumption.However,it is only a single-key one,where the homomorphic evaluation can only be performed within ciphertexts under the same key.Compared with singlekey FHE,multi-key FHE is more practical.Multi-key FHE enables ciphertexts encrypted under different public keys to perform homomorphic operations without having to decrypt these ciphertexts using their own private keys.In addition,in a multi-identity FHE scheme,only identity information and public parameters are required when encrypting,which simplifies certificate-based key management in public key infrastructure.Based on the work of Gentry and Halevi,a new compressible ciphertext expansion technique is proposed.Then,we use this technology to construct a compressible multi-key FHE scheme and a compressible multi-identity FHE scheme to overcome the bottleneck of bandwidth inefficiency in the multi-key and multiidentity settings.The two schemes proposed in this paper make the objects of homomorphic operation can be the ciphertexts encrypted under different keys or different identities before compression,thus solving the single key defect of the work of Gentry and Halevi.Based on the standard assumption of learning with errors,the two schemes are respectively semantically secure and selectively secure in the random oracle model(ROM).