Message Authentication Code with Fast Verification over Encrypted Data and Applications

In common data analytic scenarios, data is produced by a multitude of _data producers_ (e.g., medical clinics), stored and maintained by some _data keeper_ (e.g., a centralized repository), and substantial benefit can be gained from making data accessible to a variety of _data consumers_ (e.g., researchers); however, making cleartext data accessible poses a privacy threat and may infringe on privacy regulation. Computing over data encrypted by fully homomorphic encryption (FHE) enables providing privacy guarantee together with data mining utility. To ensure that correct insights are extracted, it is essential to guarantee _data authenticity_. In this work we present an authenticity proof for encrypted data: As a central tool we show how to modify a classical MAC based on universal hashing to introduce _the first MAC with fast homomorphic verification over the reals_ (7.37 microseconds amortized runtime). We then utilize our MAC for guaranteeing data authenticity, for data provided by an untrusted data keeper in FHE encrypted form. We implemented our solution, demonstrating _substantial efficiency improvements_ over the prior art (Chatel et al. USENIX'21): improving the proof size and generation time by over 10^4X. To demonstrate the usefulness of our homomorphic verification in realistic systems we implemented it in AWS EC2 with S3 storage, demonstrating it achieves practical performance for fetching and authenticating FHE ciphertexts, as well as smooth integration with subsequent homomorphic evaluation of decision tree models.