Cryptology ePrint Archive: Report 2011/117

Bounded Vector Signatures and their Applications

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

Abstract: 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.

Category / Keywords: applications / Algebraic Signatures, Malleable Signatures, Vectors

Publication Info: Full version of paper to be appear at 6th ACM Symposium on Information, Computer and Communications Security (ASIACCS 2011).

Date: received 8 Mar 2011

Contact author: scott coull at redjack com

Available format(s): PDF | BibTeX Citation

Version: 20110310:021202 (All versions of this report)

Short URL: ia.cr/2011/117

Discussion forum: Show discussion | Start new discussion