Dynamic Fully Forward-Secure Group Signatures

摘要

Enhancing user privacy while allowing the use of digital cre dentials in network-wide applications is a very active area. Group signatures are primary privacy-preserving credentials that enable both, non-repudiation and abuser-tracing. When embedding cryptographic tools in actual computing systems, it is important to ensure physical layer protection to cryptographic keys. A simple risk analysis shows that taking advantage of system (i.e., hardware, software, net work) vulnerabilities is usually much easier than cryptan alyzing the cryptographic primitives themselves. Forward secure cryptosystems, in turn, are one of the suggested pro tective measures, where private keys periodically evolve in such a way that, if a break-in occurs, past uses of those keys in earlier periods are protected. At CCS 2001, Song argued why key exposures may cause even more important concerns in the context of group sig natures (namely, under the mask of anonymity within a group of other key holders). She then gave two examples of forward-secure group signatures, and argued their ad hoc properties based on the state of understanding of group signature security properties at that time (proper security models had not been formalized yet). These implementa tions are fruitful initial efforts, but still suffer from certain imperfections. In the first scheme for instance, forward se curity is only guaranteed to signers as long as the group manager's private key is safe. Another scheme recently de scribed by Nakanishi et al. for static groups also fails to maintain security when the group manager is compromised. In this paper, we reconsider the subject and first formal ize the notion of "fully forward-secure group signature" (FS GS) in dynamic groups. We carefully define the correctness and security properties that such a scheme ought to have. We then give a realization of the primitive with quite at tractive features: constant-size signatures, constant cost of signing/verifying, and at most polylog complexity of other metrics. The scheme is further proven secure in the standard model (no random oracle idealization is used).