Secure Fully Homomorphic Authenticated Encryption

Homomorphic authenticated encryption allows implicit computation on plaintexts using corresponding ciphertexts without losing privacy, and provides authenticity of the computation and the resultant plaintext of the computation when performing a decryption. However, due to its special functionality, the security notions of the homomorphic authenticated encryption is somewhat complicated and the construction of fully homomorphic authenticated encryption has never been given. In this work, we propose a new security notion and the first construction of fully homomorphic authenticated encryption. Our new security notion is a unified definition for data privacy and authenticity of homomorphic authenticated encryption. Moreover, our security notion is simpler and stronger than the previous ones. To realize our new security notion, we also suggest a construction of fully homomorphic authenticated encryption via generic construction. We combine a fully homomorphic encryption and two homomorphic authenticators, one fully homomorphic and one OR-homomorphic, to construct a fully homomorphic authenticated encryption that satisfies our security notion. Our construction requires its fully homomorphic encryption to be indistinguishable under chosen plaintext attacks and its homomorphic authenticators to be unforgeable under selectively chosen plaintext queries. Our construction also supports multiple datasets and amortized efficiency. For efficiency, we also construct a multi-dataset fully homomorphic authenticator scheme, which is a variant of the first fully homomorphic signature scheme. Our multi-dataset fully homomorphic authenticator scheme satisfies the security requirement of our generic construction above and supports amortized efficiency.