Paper 2013/801

Authenticating Computation on Groups: New Homomorphic Primitives and Applications

Dario Catalano, Antonio Marcedone, and Orazio Puglisi


In this paper we introduce new primitives to authenticate computation on data expressed as elements in (cryptographic) groups. As for the case of homomorphic authenticators, our primitives allow to verify the correctness of the computation without having to know of the original data set. More precisely, our contributions are two-fold. First, we introduce the notion of linearly homomorphic authenticated encryption with public verifiability and show how to instantiate this primitive (in the random oracle model) to support Paillier's ciphertexts. This immediately yields a very simple and efficient (publicly) verifiable computation mechanism for encrypted (outsourced) data based on Paillier's cryptosystem. As a second result, we show how to construct linearly homomorphic signature schemes to sign elements in bilinear groups (LHSG for short). Such type of signatures are very similar to (linearly homomorphic) structure preserving ones, but they allow for more flexibility, as the signature is explicitly allowed to contain components which are not group elements. In this sense our contributions are as follows. First we show a very simple construction of LHSG that is secure against weak random message attack (RMA). Next we give evidence that RMA secure LHSG are interesting on their own right by showing applications in the context of on-line/off-line homomorphic and network coding signatures. This notably provides what seems to be the first instantiations of homomorphic signatures achieving on-line/off-line efficiency trade-offs. Finally, we present a generic transform that converts RMA-secure LHSG into ones that achieve full security guarantees.

Note: The original work was considerably extended. Previous title was "Linearly Homomorphic Structure Preserving Signatures: New Methodologies and Applications"

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
Contact author(s)
a marcedone @ gmail com
2014-02-13: revised
2013-12-01: received
See all versions
Short URL
Creative Commons Attribution


      author = {Dario Catalano and Antonio Marcedone and Orazio Puglisi},
      title = {Authenticating Computation on Groups: New Homomorphic Primitives and Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2013/801},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.