Abstract
Recently, a new paradigm to construct very efficient multi-show attribute-based anonymous credential (ABC) systems has been introduced in Asiacrypt’14. Here, structure-preserving signatures on equivalence classes (SPS-EQ-\(\mathcal {R}\)), a novel flavor of structure-preserving signatures (SPS), and randomizable polynomial commitments are elegantly combined to yield the first ABC systems with O(1) credential size and O(1) communication bandwidth during issuing and showing. It has, however, been left open to present a full-fledged revocable multi-show attribute-based anonymous credential (RABC) system based on the aforementioned paradigm. As revocation is a highly desired and important feature when deploying ABC systems in a practical setting, this is an interesting challenge.
To this end, we propose an RABC system which builds upon the aforementioned ABC system, preserves its nice asymptotic properties and is in particular entirely practical. Our approach is based on universal accumulators, which nicely fit to the underlying paradigm. Thereby, in contrast to existing accumulator-based revocation approaches, we do not require complex zero-knowledge proofs of knowledge (ZKPKs) to demonstrate the possession of a non-membership witness for the accumulator. This is in part due to the nice rerandomization properties of SPS-EQ-\(\mathcal {R}\). Thus, this makes the entire RABC system conceptually simple, efficient and represents a novel direction in credential revocation. We also propose a game-based security model for RABC systems and prove the security of our construction in this model. Finally, to demonstrate the value of our novel approach, we carefully adapt an efficient existing universal accumulator approach (as applied within Microsoft’s U-Prove) to our setting and compare the two revocation approaches when used with the same underlying ABC system.
The authors have been supported by EU Horizon 2020 through project Prismacloud (GA No. 644962) and by EU FP7 through project MATTHEW (GA No. 610436). An extended version of this paper is available in the IACR Cryptology ePrint Archive.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
We, however, note that the efficiency of our scheme comes at the cost of more complex proofs.
- 2.
We stress that in our context pseudonyms are solely used for revocation and not for showing purposes (as e.g., in the model of [14]) and thus one might call ours revocation pseudonyms (but we simply call them pseudonyms henceforth).
- 3.
Such a witness is basically a consistently randomized commitment (by using \(\rho \)) to \(\overline{\mathbb {A}'}\).
- 4.
To ensure the authenticity of the rerandomized revocation information, we require users to prove knowledge of the randomizer used for randomizing the original accumulator and for proof-technical reasons we require the user to prove knowledge of \(\log _Q C_3\).
References
Acar, T., Chow, S.S.M., Nguyen, L.: Accumulators and U-Prove revocation. In: Sadeghi, A.-R. (ed.) FC 2013. LNCS, vol. 7859, pp. 189–196. Springer, Heidelberg (2013)
Akagi, N., Manabe, Y., Okamoto, T.: An efficient anonymous credential system. In: Tsudik, G. (ed.) FC 2008. LNCS, vol. 5143, pp. 272–286. Springer, Heidelberg (2008)
Au, M.H., Tsang, P.P., Susilo, W., Mu, Y.: Dynamic universal accumulators for DDH groups and their application to attribute-based anonymous credential systems. In: Fischlin, M. (ed.) CT-RSA 2009. LNCS, vol. 5473, pp. 295–308. Springer, Heidelberg (2009)
Baldimtsi, F., Lysyanskaya, A.: Anonymous credentials light. In: ACM CCS. ACM (2013)
Begum, N., Nakanishi, T., Funabiki, N.: Efficient proofs for CNF formulas on attributes in pairing-based anonymous credential system. In: Kwon, T., Lee, M.-K., Kwon, D. (eds.) ICISC 2012. LNCS, vol. 7839, pp. 495–509. Springer, Heidelberg (2013)
Belenkiy, M., Camenisch, J., Chase, M., Kohlweiss, M., Lysyanskaya, A., Shacham, H.: Randomizable proofs and delegatable anonymous credentials. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 108–125. Springer, Heidelberg (2009)
Benaloh, J.C., de Mare, M.: One-way accumulators: a decentralized alternative to digital signatures. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 274–285. Springer, Heidelberg (1994)
Boneh, D., Shacham, H.: Group signatures with verifier-local revocation. In: ACM CCS (2004)
Boyen, X.: The uber-assumption family – a unified complexity framework for bilinear groups. In: Galbraith, S.D., Paterson, K.G. (eds.) Pairing 2008. LNCS, vol. 5209, pp. 39–56. Springer, Heidelberg (2008)
Brands, S.: Rethinking public-key Infrastructures and Digital Certificates: Building in Privacy. MIT Press, Cambridge (2000)
Camenisch, J., Dubovitskaya, M., Haralambiev, K., Kohlweiss, M.: Composable and modular anonymous credentials: definitions and practical constructions. IACR Cryptology ePrint Archive
Camenisch, J., Herreweghen, E.V.: Design and implementation of the idemix anonymous credential system. In: ACM CCS. ACM (2002)
Camenisch, J., Kohlweiss, M., Soriente, C.: An accumulator based on bilinear maps and efficient revocation for anonymous credentials. In: Jarecki, S., Tsudik, G. (eds.) PKC 2009. LNCS, vol. 5443, pp. 481–500. Springer, Heidelberg (2009)
Camenisch, J., Krenn, S., Lehmann, A., Mikkelsen, G.L., Neven, G., Pedersen, M.O.: Formal treatment of privacy-enhancing credential systems (2015)
Camenisch, J., Lehmann, A., Neven, G., Rial, A.: Privacy-preserving auditing for attribute-based credentials. In: Kutyłowski, M., Vaidya, J. (eds.) ICAIS 2014, Part II. LNCS, vol. 8713, pp. 109–127. Springer, Heidelberg (2014)
Camenisch, J.L., Lysyanskaya, A.: An efficient system for non-transferable anonymous credentials with optional anonymity revocation. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 93–118. Springer, Heidelberg (2001)
Camenisch, J.L., Lysyanskaya, A.: A signature scheme with efficient protocols. In: Cimato, S., Galdi, C., Persiano, G. (eds.) SCN 2002. LNCS, vol. 2576, pp. 268–289. Springer, Heidelberg (2003)
Camenisch, J.L., Lysyanskaya, A.: Dynamic accumulators and application to efficient revocation of anonymous credentials. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, p. 61. Springer, Heidelberg (2002)
Camenisch, J.L., Lysyanskaya, A.: Signature schemes and anonymous credentials from bilinear maps. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 56–72. Springer, Heidelberg (2004)
Canard, S., Lescuyer, R.: Anonymous credentials from (indexed) aggregate signatures. In: DIM. ACM (2011)
Canard, S., Lescuyer, R.: Protecting privacy by sanitizing personal data: a new approach to anonymous credentials. In: ASIA CCS. ACM (2013)
Chase, M., Meiklejohn, S., Zaverucha, G.M.: Algebraic MACs and keyed-verification anonymous credentials. In: ACM CCS. ACM (2014)
Chaum, D.: Security without identification: transaction systems to make big brother obsolete. Commun. ACM 28(10), 1030–1044 (1985)
Cheon, J.H.: Security analysis of the strong diffie-hellman problem. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 1–11. Springer, Heidelberg (2006)
Derler, D., Hanser, C., Slamanig, D.: Revisiting cryptographic accumulators, additional properties and relations to other primitives. In: Nyberg, K. (ed.) CT-RSA 2015. LNCS, vol. 9048, pp. 127–144. Springer, Heidelberg (2015)
Fuchsbauer, G.: Breaking existential unforgeability of a signature scheme from Asiacrypt 2014. IACR Cryptology ePrint Archive (2014)
Fuchsbauer, G., Hanser, C., Slamanig, D.: EUF-CMA-Secure structure-preserving signatures on equivalence classes. IACR Cryptology ePrint Archive (2014)
Garman, C., Green, M., Miers, I.: Decentralized anonymous credentials. In: NDSS (2014)
Hajny, J., Malina, L.: Unlinkable attribute-based credentials with practical revocation on smart-cards. In: Mangard, S. (ed.) CARDIS 2012. LNCS, vol. 7771, pp. 62–76. Springer, Heidelberg (2013)
Hanser, C., Slamanig, D.: Structure-preserving signatures on equivalence classes and their application to anonymous credentials. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8873, pp. 491–511. Springer, Heidelberg (2014)
Lapon, J., Kohlweiss, M., De Decker, B., Naessens, V.: Analysis of revocation strategies for anonymous idemix credentials. In: De Decker, B., Lapon, J., Naessens, V., Uhl, A. (eds.) CMS 2011. LNCS, vol. 7025, pp. 3–17. Springer, Heidelberg (2011)
Li, J., Li, N., Xue, R.: Universal accumulators with efficient nonmembership proofs. In: Katz, J., Yung, M. (eds.) ACNS 2007. LNCS, vol. 4521, pp. 253–269. Springer, Heidelberg (2007)
Lueks, W., Alpár, G., Hoepman, J.H., Vullers, P.: Fast revocation of attribute-based credentials for both users and verifiers. In: Federrath, H., Gollmann, D. (eds.) SEC 2015. IFIP AICT, vol. 455, pp. 463–478. Springer, Heidelberg (2015)
Lysyanskaya, A., Rivest, R.L., Sahai, A., Wolf, S.: Pseudonym systems (extended abstract). In: Heys, H.M., Adams, C.M. (eds.) SAC 1999. LNCS, vol. 1758, pp. 184–199. Springer, Heidelberg (2000)
Nakanishi, T., Fujii, H., Hira, Y., Funabiki, N.: Revocable group signature schemes with constant costs for signing and verifying. In: Jarecki, S., Tsudik, G. (eds.) PKC 2009. LNCS, vol. 5443, pp. 463–480. Springer, Heidelberg (2009)
Nakanishi, T., Funabiki, N.: Verifier-local revocation group signature schemes with backward unlinkability from bilinear maps. In: Roy, B. (ed.) ASIACRYPT 2005. LNCS, vol. 3788, pp. 533–548. Springer, Heidelberg (2005)
Nguyen, L.: Accumulators from bilinear pairings and applications. In: Menezes, A. (ed.) CT-RSA 2005. LNCS, vol. 3376, pp. 275–292. Springer, Heidelberg (2005)
Nguyen, L., Paquin, C.: U-prove designated-verifier accumulator revocation extension. Technical report, Microsoft Research (2014)
Paquin, C., Zaverucha, G.: U-prove cryptographic specification v1.1, revision 3. Technical report, Microsoft Corporation (2013)
Song, D.X.: Practical forward secure group signature schemes. In: ACM CCS. ACM (2001)
Sudarsono, A., Nakanishi, T., Funabiki, N.: Efficient proofs of attributes in pairing-based anonymous credential system. In: Fischer-Hübner, S., Hopper, N. (eds.) PETS 2011. LNCS, vol. 6794, pp. 246–263. Springer, Heidelberg (2011)
Unterluggauer, T., Wenger, E.: Efficient pairings and ECC for embedded systems. In: Batina, L., Robshaw, M. (eds.) CHES 2014. LNCS, vol. 8731, pp. 298–315. Springer, Heidelberg (2014)
Verheul, E.R.: Self-blindable credential certificates from the weil pairing. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 533–551. Springer, Heidelberg (2001)
Acknowledgements
We would like to thank the anonymous reviewers for their valuable comments.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Derler, D., Hanser, C., Slamanig, D. (2015). A New Approach to Efficient Revocable Attribute-Based Anonymous Credentials. In: Groth, J. (eds) Cryptography and Coding. IMACC 2015. Lecture Notes in Computer Science(), vol 9496. Springer, Cham. https://doi.org/10.1007/978-3-319-27239-9_4
Download citation
DOI: https://doi.org/10.1007/978-3-319-27239-9_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-27238-2
Online ISBN: 978-3-319-27239-9
eBook Packages: Computer ScienceComputer Science (R0)