Paper 2011/117

Bounded Vector Signatures and their Applications

Lei Wei, Scott E. Coull, and Michael K. Reiter


Although malleability is undesirable in traditional digital signatures, schemes with limited malleability properties enable interesting functionalities that may be impossible to obtain otherwise (e.g., homomorphic signatures). In this paper, we introduce a new malleable signature scheme called bounded vector signatures. The proposed scheme allows a user to sign a multi-dimensional vector of values, along with a description of the context within which the vector should be interpreted. The scheme includes a unique malleability property, which we refer to as the stretch property, that allows the components of the signed vector to be increased up to a pre-defined limit without access to the signing key. Decreasing these values, however, remains computationally infeasible. We prove the security of our construction under the strong RSA and decisional Diffie-Hellman assumptions in the random oracle model. Finally, we underscore the utility of bounded vector signatures by discussing their use in distributed systems security applications.

Available format(s)
Publication info
Published elsewhere. Full version of paper to be appear at 6th ACM Symposium on Information, Computer and Communications Security (ASIACCS 2011).
Algebraic SignaturesMalleable SignaturesVectors
Contact author(s)
scott coull @ redjack com
2011-03-10: received
Short URL
Creative Commons Attribution


      author = {Lei Wei and Scott E.  Coull and Michael K.  Reiter},
      title = {Bounded Vector Signatures and their Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2011/117},
      year = {2011},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.