Message Authentication Code with Fast Verification over Encrypted Data and Applications
Authors: Adi Akavia (University of Haifa), Meir Goldenberg (University of Haifa), Neta Oren (University of Haifa), Rita Vald (Intuit Inc)
Volume: 2025
Issue: 4
Pages: 1092–1111
DOI: https://doi.org/10.56553/popets-2025-0173
Abstract: 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.
Keywords: message authentication code, homomorphic encryption, authenticated storage
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution 4.0 license.
