International Association
for Cryptologic Research

At Crypto 2013 Libert, Peters, Joye and Yung introduced the notion of Linearly Homomorphic Structure Preserving Signatures (LHSPS) as a tool to perform verifiable computation on encrypted data and to create constant-size non malleable commitments to group elements. In this paper we improve our understanding of LHSPS by putting forward new methodologies and applications. First, we present a generic transform that converts LHSPS which are secure against weak random message attack (RMA) into ones that achieve full security guarantees. Next we give evidence that RMA secure linearly homomorphic structure preserving signatures are interesting in 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.