Double-trapdoor anonymous tags for traceable signatures

This paper introduces a novel tool, public-key anonymous tag system, which is useful in building controlled privacy-protecting protocols. The double-trapdoor structure of the system not only allows the authority to create a token which can trace someone’s tags without violating anonymity of the tag issuer, but also allows the issuer to claim or deny the authorship of a tag in the stateless manner. An efficient instantiation based on simple assumptions in the standard model is presented. We then use it for a modular construction of traceable signatures. Our scheme supports a signature authorship claiming (and denial) that binds a claim to the public-key of the signer unlike that in known schemes. It is also the first scheme in the literature which features concurrent joining of users, stronger anonymity, and so on without random oracles.     

Structure-Preserving Signatures and Commitments to Group Elements

A modular approach to constructing cryptographic protocols leads to simple designs but often inefficient instantiations. On the other hand, ad hoc constructions may yield efficient protocols at the cost of losing conceptual simplicity. We suggest a new design paradigm, structure-preserving cryptography, that provides a way to construct modular protocols with reasonable efficiency while retaining conceptual simplicity. A cryptographic scheme over a bilinear group is called structure-preserving if its public inputs and outputs consist of elements from the bilinear groups and their consistency can be verified by evaluating pairing-product equations. As structure-preserving schemes smoothly interoperate with each other, they are useful as building blocks in modular design of cryptographic applications. This paper introduces structure-preserving commitment and signature schemes over bilinear groups with several desirable properties. The commitment schemes include homomorphic, trapdoor and length-reducing commitments to group elements, and the structure-preserving signature schemes are the first ones that yield constant-size signatures on multiple group elements. A structure-preserving signature scheme is called automorphic if the public keys lie in the message space, which cannot be achieved by compressing inputs via a cryptographic hash function, as this would destroy the mathematical structure we are trying to preserve. Automorphic signatures can be used for building certification chains underlying privacy-preserving protocols. Among a vast number of applications of structure-preserving protocols, we present an efficient round-optimal blind-signature scheme and a group signature scheme with an efficient and concurrently secure protocol for enrolling new members.