Abstract
Lots of revocable group signature schemes have been proposed so far. In one type of revocable schemes, signing and/or verifying algorithms have O(N) or O(R) complexity, where N is the group size and R is the number of revoked members. On the other hand, in Camenisch-Lysyanskaya scheme and the followers, signing and verifying algorithms have O(1) complexity. However, before signing, updates of the secret key are required. The complexity is O(R) in the worst case. In this paper, we propose a revocable scheme with signing and verifying of O(1) complexity, where no updates of secret key are required. The compensation is the long public key of O(N). In addition, we extend it to the scheme with \(O(\sqrt{N})\)-size public key, where signing and verifying have constant extra costs.
The original version of this chapter was revised: The copyright line was incorrect. This has been corrected. The Erratum to this chapter is available at DOI: 10.1007/978-3-642-00468-1_29
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Au, M.H., Susilo, W., Mu, Y.: Constant-size dynamic k-TAA. In: De Prisco, R., Yung, M. (eds.) SCN 2006. LNCS, vol. 4116, pp. 111–125. Springer, Heidelberg (2006)
Au, M.H., Susilo, W., Mu, Y.: Constant-size dynamic k-TAA. Cryptology ePrint Archive: Report 2008/136 (2008); this is the extended version of [1]
Barreto, P.S.L.M., Galbraith, S.D., O’hEigeartaigh, C., Scott, M.: Efficient pairing computation on supersingular abelian varieties. Designs, Codes and Cryptography 42(3), 239–271 (2007)
Barreto, P.S.L.M., Naehrig, M.: Pairing-friendly elliptic curves of prime order. In: Preneel, B., Tavares, S. (eds.) SAC 2005. LNCS, vol. 3897, pp. 319–331. Springer, Heidelberg (2006)
Bellare, M., Shi, H., Zhang, C.: Foundations of group signatures: The case of dynamic groups. In: Menezes, A. (ed.) CT-RSA 2005. LNCS, vol. 3376, pp. 136–153. Springer, Heidelberg (2005)
Boneh, D., Boyen, X.: Short signatures without random oracles. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 56–73. Springer, Heidelberg (2004)
Boneh, D., Boyen, X., Shacham, H.: Short group signatures. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 41–55. Springer, Heidelberg (2004)
Boneh, D., Shacham, H.: Group signatures with verifier-local revocation. In: Proc. 11th ACM Conference on Computer and Communications Security (ACM-CCS 2004), pp. 168–177 (2004)
Boudot, F.: Efficient proofs that a committed number lies in an interval. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 431–444. Springer, Heidelberg (2000)
Bresson, E., Stern, J.: Group signature scheme with efficient revocation. In: Kim, K.-c. (ed.) PKC 2001. LNCS, vol. 1992, pp. 190–206. Springer, Heidelberg (2001)
Brickell, E.F., Camenisch, J., Chen, L.: Direct anonymous attestation. In: Proc. 11th ACM Conference on Computer and Communications Security (ACM-CCS 2004), pp. 132–145 (2004)
Camenisch, J., Groth, J.: Group signatures: Better efficiency and new theoretical aspects. In: Blundo, C., Cimato, S. (eds.) SCN 2004. LNCS, vol. 3352, pp. 120–133. Springer, Heidelberg (2005)
Camenisch, J., Herreweghen, E.V.: Design and implementation of the idemix anonymous credential system. In: Proc. 9th ACM Conference on Computer and Communications Security (ACM-CCS 2002), pp. 21–30 (2002)
Camenisch, J., Lysyanskaya, A.: Dynamic accumulators and application to efficient revocation of anonymous credentials. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 61–76. Springer, Heidelberg (2002)
Chaum, D., van Heijst, E.: Group signatures. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 241–246. Springer, Heidelberg (1991)
Furukawa, J., Imai, H.: An efficient group signature scheme from bilinear maps. In: Boyd, C., González Nieto, J.M. (eds.) ACISP 2005. LNCS, vol. 3574, pp. 455–467. Springer, Heidelberg (2005)
Furukawa, J., Imai, H.: An efficient group signature scheme from bilinear maps. IEICE Trans. Fundamentals E89-A(5), 1328–1338 (2006)
Groth, J.: Fully anonymous group signatures without random oracles. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 164–180. Springer, Heidelberg (2007)
Hess, F., Smart, N., Vercauteren, F.: The eta pairing revisited. IEEE Trans. Information Theory 52(10), 4595–4602 (2006)
Isshiki, T., Mori, K., Sako, K., Teranishi, I., Yonezawa, S.: Using group signatures for identity management and its implementation. In: Proc. 2nd ACM Workshop on Digital Identity Management, pp. 73–78 (2006)
Nakanishi, T., Funabiki, N.: A short verifier-local revocation group signature scheme with backward unlinkability. In: Yoshiura, H., Sakurai, K., Rannenberg, K., Murayama, Y., Kawamura, S.-i. (eds.) IWSEC 2006. LNCS, vol. 4266, pp. 17–32. Springer, Heidelberg (2006)
Nakanishi, T., Funabiki, N.: Short verifier-local revocation group signature scheme with backward unlinkability. IEICE Trans. Fundamentals E90-A(9), 1793–1802 (2007)
Nakanishi, T., Kubooka, F., Hamada, N., Funabiki, N.: Group signature schemes with membership revocation for large groups. In: Boyd, C., González Nieto, J.M. (eds.) ACISP 2005. LNCS, vol. 3574, pp. 443–454. Springer, Heidelberg (2005)
Nakanishi, T., Sugiyama, Y.: A group signature scheme with efficient membership revocation for reasonable groups. In: Wang, H., Pieprzyk, J., Varadharajan, V. (eds.) ACISP 2004. LNCS, vol. 3108, pp. 336–347. Springer, Heidelberg (2004)
Teranishi, I., Sako, K.: k-times anonymous authentication with a constant proving cost. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T.G. (eds.) PKC 2006. LNCS, vol. 3958, pp. 525–542. Springer, Heidelberg (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Nakanishi, T., Fujii, H., Hira, Y., Funabiki, N. (2009). Revocable Group Signature Schemes with Constant Costs for Signing and Verifying. In: Jarecki, S., Tsudik, G. (eds) Public Key Cryptography – PKC 2009. PKC 2009. Lecture Notes in Computer Science, vol 5443. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-00468-1_26
Download citation
DOI: https://doi.org/10.1007/978-3-642-00468-1_26
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-00467-4
Online ISBN: 978-3-642-00468-1
eBook Packages: Computer ScienceComputer Science (R0)