Paper 2016/804

Multi-Key Homomorphic Authenticators

Dario Fiore, Aikaterini Mitrokotsa, Luca Nizzardo, and Elena Pagnin


Homomorphic authenticators (HAs) enable a client to authenticate a large collection of data elements $m_1, . . . , m_t$ and outsource them, along with the corresponding authenticators, to an untrusted server. At any later point, the server can generate a $short$ authenticator $\sigma_{f, y}$ vouching for the correctness of the output $y$ of a function $f$ computed on the outsourced data, i.e., $y = f(m_1,...,m_t)$. Recently researchers have focused on HAs as a solution, with minimal communication and interaction, to the problem of delegating computation on outsourced data. The notion of HAs studied so far, however, only supports executions (and proofs of correctness) of computations over data authenticated by a single user. Motivated by realistic scenarios (ubiquitous computing, sensor networks, etc.) in which large datasets include data provided by multiple users, we study the concept of $multi-key$ $homomorphic$ $authenticators$. In a nutshell, multi-key HAs are like HAs with the extra feature of allowing the holder of public evaluation keys to compute on data authenticated under different secret keys. In this paper, we introduce and formally define multi-key HAs. Secondly, we propose a construction of a multi-key homomorphic signature based on standard lattices and supporting the evaluation of circuits of bounded polynomial depth. Thirdly, we provide a construction of multi-key homomorphic MACs based only on pseudorandom functions and supporting the evaluation of low-degree arithmetic circuits. Albeit being less expressive and only secretly verifiable, the latter construction presents interesting efficiency properties.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in ASIACRYPT 2016
Homomorphic SignaturesDigital SignaturesMessage Authentication CodesSecure Outsourcing
Contact author(s)
luca nizzardo @ imdea org
2016-08-24: received
Short URL
Creative Commons Attribution


      author = {Dario Fiore and Aikaterini Mitrokotsa and Luca Nizzardo and Elena Pagnin},
      title = {Multi-Key Homomorphic Authenticators},
      howpublished = {Cryptology ePrint Archive, Paper 2016/804},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.