New tag-based signatures and their applications on linearly homomorphic signatures

Tag-based signature schemes can be efficiently converted into digital signature schemes using a generic transformation. However, there is no signature scheme that admits k > 1 fold tag-collisions in the lattice environment as pointed by Ducas and Micciancio (2014). This work answers this problem in the stateful case. We use homomorphic hash functions and hash functions of tags to construct a SIS-based stateful tag -based signature (STS) scheme that admits k > 1 fold tag-collisions. Messages are encoded prior to the signing procedure such that any k sequentially signed messages with the same tag form a basis for a vector subspace. The security analysis adopts a new abstraction called vector-space oriented partition. With the same technique, two STS schemes based on the CDH and the RSA assumptions, respectively, are proposed.As an application of our STS schemes, we show that those having field (or quasi-field) as message space can be converted into linearly homomorphic signature (LHS) schemes. Therefore, we immediately obtain CDH/RSA-based LHS scheme in the standard model under the same weaker assumption. Our LHS schemes can be viewed as removing the restriction on the homomorphic propertyfrom the related STS schemes. They have similar public key and signature sizes as the existing counterparts.

Automated summary

This paper discusses the conversion of tag-based signature schemes into digital signature schemes and addresses the issue of allowing k > 1 fold tag-collisions in the lattice environment. It proposes a stateful tag-based signature (STS) scheme based on homomorphic hash functions and hash functions of tags, which allows for k > 1 fold tag-collisions. Two STS schemes based on the CDH and RSA assumptions, respectively, are also introduced using the same technique. The paper further explores the application of the STS schemes and demonstrates the conversion of schemes with field or quasi-field as message space into linearly homomorphic signature (LHS) schemes.