eprint.iacr.org will be offline for approximately an hour for routine maintenance again at 10pm UTC on Wednesday, April 17.

Paper 2013/361

Linearly Homomorphic Structure-Preserving Signatures and Their Applications

Benoit Libert, Thomas Peters, Marc Joye, and Moti Yung


Structure-preserving signatures (SPS) are signature schemes where messages, signatures and public keys all consist of elements of a group over which a bilinear map is efficiently computable. This property makes them useful in cryptographic protocols as they nicely compose with other algebraic tools (like the celebrated Groth-Sahai proof systems). In this paper, we consider SPS systems with homomorphic properties and suggest applications that have not been provided before (in particular, not by employing ordinary SPS). We build linearly homomorphic structure-preserving signatures under simple assumptions and show that the primitive makes it possible to verify the calculations performed by a server on outsourced encrypted data (i.e., combining secure computation and authenticated computation to allow reliable and secure cloud storage and computation, while freeing the client from retaining cleartext storage). Then, we give a generic construction of non-malleable (and actually simulation-sound) commitment from any linearly homomorphic SPS. This notably provides the first constant-size non-malleable commitment to group elements.

Note: Fixed one issue in Appendix B

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Crypto 2013 -- This is the full version
Structure-preserving cryptographysignatureshomomorphismcommitment schemesnon-malleability
Contact author(s)
benoit libert @ technicolor com
2013-07-17: last of 2 revisions
2013-06-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Benoit Libert and Thomas Peters and Marc Joye and Moti Yung},
      title = {Linearly Homomorphic Structure-Preserving Signatures and Their Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2013/361},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/361}},
      url = {https://eprint.iacr.org/2013/361}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.