Paper 2015/396

Generalizing Homomorphic MACs for Arithmetic Circuits

Dario Catalano, Dario Fiore, Rosario Gennaro, and Luca Nizzardo

Abstract

Homomorphic MACs, introduced by Gennaro and Wichs in 2013, allow anyone to validate computations on authenticated data without knowledge of the secret key. Moreover, the secret-key owner can verify the validity of the computation without needing to know the original (authenticated) inputs. Beyond security, homomorphic MACs are required to produce short tags (succinctness) and to support composability (i.e., outputs of authenticated computations should be re-usable as inputs for new computations). At Eurocrypt 2013, Catalano and Fiore proposed two realizations of homomorphic MACs that support a restricted class of computations (arithmetic circuits of polynomial degree), are practically efficient, but fail to achieve both succinctness and composability at the same time. In this paper, we generalize the work of Catalano and Fiore in several ways. First, we abstract away their results using the notion of encodings with limited malleability, thus yielding new schemes based on different algebraic settings. Next, we generalize their constructions to work with graded encodings, and more abstractly with $k$-linear groups. The main advantage of this latter approach is that it allows for homomorphic MACs which are (somewhat) composable while retaining succinctness. Interestingly, our construction uses graded encodings in a generic way. Thus, all its limitations (limited composability and non-constant size of the tags) solely depend on the fact that currently known multilinear maps share similar constraints. This means, for instance, that our scheme would support arbitrary circuits (polynomial depth) if we had compact multilinear maps with an exponential number of levels.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in PKC 2014
Keywords
Homomorphic Message Authentication CodesSecure OutsourcingVerifiable Computation
Contact author(s)
luca nizzardo @ imdea org
History
2015-05-01: received
Short URL
https://ia.cr/2015/396
License
Creative Commons Attribution
CC BY

BibTeX

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