zbMATH — the first resource for mathematics

Real traceable signatures. (English) Zbl 1267.94115
Jacobson, Michael J. jun. (ed.) et al., Selected areas in cryptography. 16th annual international workshop, SAC 2009, Calgary, Alberta, Canada, August 13–14, 2009. Revised selected papers. Berlin: Springer (ISBN 978-3-642-05443-3/pbk). Lecture Notes in Computer Science 5867, 92-107 (2009).
Summary: Traceable signature scheme extends a group signature scheme with an enhanced anonymity management mechanism. The group manager can compute a tracing trapdoor which enables anyone to test if a signature is signed by a given misbehaving user, while the only way to do so for group signatures requires revealing the signer of all signatures. Nevertheless, it is not tracing in a strict sense. For all existing schemes, \(T\) tracing agents need to recollect all \(N^{\prime}\) signatures ever produced and perform \(RN^{\prime}\) “checks” for \(R\) revoked users. This involves a high volume of transfer and computations. Increasing \(T\) increases the degree of parallelism for tracing but also the probability of “missing” some signatures in case some of the agents are dishonest.
We propose a new and efficient way of tracing – the tracing trapdoor allows the reconstruction of tags such that each of them can uniquely identify a signature of a misbehaving user. Identifying \(N\) signatures out of the total of \(N^{\prime}\) signatures (\(N \ll N^{\prime})\) just requires the agent to construct \(N\) small tags and send them to the signatures holder. \(N\) here gives a trade-off between the number of unlinkable signatures a member can produce and the efforts for the agents to trace the signatures. We present schemes with simple design borrowed from anonymous credential systems. Our schemes are proven secure respectively in the random oracle model and in the common reference string model (or in the standard model if there exists a trusted party for system parameters initialization).
For the entire collection see [Zbl 1177.94012].

94A62 Authentication, digital signatures and secret sharing
94A60 Cryptography
Full Text: DOI