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.Category / Keywords: cryptographic protocols / Homomorphic Message Authentication Codes, Secure Outsourcing, Verifiable Computation Original Publication (with minor differences): IACR-PKC-2014 Date: received 27 Apr 2015 Contact author: luca nizzardo at imdea org Available format(s): PDF | BibTeX Citation Version: 20150501:120451 (All versions of this report) Short URL: ia.cr/2015/396 Discussion forum: Show discussion | Start new discussion