Subset Signatures with Controlled Context-Hiding

摘要

Subset signatures are a variant of malleable signatures which allow anyone to derive signatures on any subset of previously signed sets in such a way that derived signatures are indistinguishable from new signatures on the subset (i.e. context-hiding). Such a primitive has many applications. In some scenarios, it might be desirable to restrict some elements in the set from preserving the context-hiding property. In other words, it might be desirable to allow the signer, at the time of the signing, to mark specific elements (which we refer to hereafter as the restricted subset) such that the inclusion of any elements from the restricted subset in any derived signatures would violate the context-hiding property and make the derived signature linkable to the original signature. In this paper, we put forward the notion of subset signatures with controlled context-hiding. We propose a security model and a generic construction as well as efficient instantiations which do not rely on random oracles. Our instantiations are structure-preserving and therefore could be useful for other applications. As a special case of our constructions when the restricted subset is empty, we obtain more efficient constructions of standard subset signatures. Our constructions, which satisfy the strongest existing security definitions, have constant-size keys and outperform existing constructions in every respect. As part of our contribution, we construct a structure-preserving signature scheme with combined unforgeability that signs a vector of group elements while maintaining constant-size signatures. The scheme has some desirable properties and combines nicely with Groth-Sahai proofs, and thus could be of independent interest.