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.
Category / Keywords: public-key cryptography / Date: received 29 Nov 2013, last revised 13 Feb 2014 Contact author: a marcedone at gmail com Available format(s): PDF | BibTeX Citation Note: The original work was considerably extended. Previous title was "Linearly Homomorphic Structure Preserving Signatures: New Methodologies and Applications" Version: 20140213:134321 (All versions of this report) Short URL: ia.cr/2013/801 Discussion forum: Show discussion | Start new discussion