Privacy-Preserving Homomorphic MACs with Efficient Verification

Homomorphic Message Authentication Code (MAC) allows a user to outsource data to an untrusted server and verify that results of computation on the data returned by the server are correct. Recently, much effort has been independently focused on whether a homomorphic MAC scheme supports data confidentiality or the authenticators can be efficiently verified. In this paper, we address the question of whether it is possible for homomorphic MAC to simultaneously achieve both the privacy and the efficiency. The answer is affirmative and we propose a new cryptographic primitive, privacy-preserving homomorphic MACs with efficient verification that can guarantee the authenticator can not reveal the underlying message. More precisely, our contributions are three-fold: (i) we introduce the primitive of privacy-preserving homomorphic MAC (PHMAC) that provides both data confidentiality and efficient verification, (ii) We provide a PHMAC construction which supports homogeneous polynomials, and demonstrate it shows high efficiency, (iii) We investigate how our PHMAC primitive with efficient verification can be employed to homomorphic authenticator-encryption and verifiable computation.