Paper 2015/194

Practical Homomorphic MACs for Arithmetic Circuits

Dario Catalano and Dario Fiore

Abstract

Homomorphic message authenticators allow the holder of a (public) evaluation key to perform computations over previously authenticated data, in such a way that the produced tag $\sigma$ can be used to certify the authenticity of the computation. More precisely, a user knowing the secret key $\sk$ used to authenticate the original data, can verify that $\sigma$ authenticates the correct output of the computation. This primitive has been recently formalized by Gennaro and Wichs, who also showed how to realize it from fully homomorphic encryption. In this paper, we show new constructions of this primitive that, while supporting a smaller set of functionalities (i.e., polynomially-bounded arithmetic circuits as opposite to boolean ones), are much more efficient and easy to implement. Moreover, our schemes can tolerate any number of (malicious) verification queries. Our first construction relies on the sole assumption that one way functions exist, allows for arbitrary composition (i.e., outputs of previously authenticated computations can be used as inputs for new ones) but has the drawback that the size of the produced tags grows with the degree of the circuit. Our second solution, relying on the $D$-Diffie-Hellman Inversion assumption, offers somewhat orthogonal features as it allows for very short tags (one single group element!) but poses some restrictions on the composition side.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in EUROCRYPT 2013
Keywords
message authentication codeshomomorphic authenticatorssecure outsourcing
Contact author(s)
dario fiore @ imdea org
History
2015-03-04: received
Short URL
https://ia.cr/2015/194
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/194,
      author = {Dario Catalano and Dario Fiore},
      title = {Practical Homomorphic MACs for Arithmetic Circuits},
      howpublished = {Cryptology ePrint Archive, Paper 2015/194},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/194}},
      url = {https://eprint.iacr.org/2015/194}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.