Developing Efficient Blinded Attribute Certificates on Smart Cards via Pairings

Lejla Batina1, Jaap-Henk Hoepman1,2, Bart Jacobs1, Wojciech Mostowski1*, and Pim Vullers1**
1 Institute for Computing and Information Sciences,
Radboud University Nijmegen, The Netherlands.
2 TNO Information and Communication Technology, The Netherlands.
This paper describes an elementary protocol to prove possession of anonymous credentials together with its implementation on smart cards. The protocol uses self-blindable attribute certificates represented as points on an elliptic curve (which are stored on the card). These certificates are verified on the reader-side via a bilinear pairing. Java Card smart cards offer only very limited access to the cryptographic coprocessor. It thus requires some ingenuity to get the protocol running with reasonable speed. We realise protocol runs with on-card computation times in the order of 1.5 seconds. It should be possible to further reduce this time with extended access to the cryptographic coprocessor.
anonymous credentials, elliptic curve cryptography, smart card, bilinear pairing, attributes, blinding, protocols, Java Card
* Sponsored by the NLnet foundation through the OV-chipkaart project.
** Sponsored by Trans Link Systems/Open Ticketing.

1   Introduction

With the growing use of smart cards in e-ticketing in public transport, huge centralised databases are compiled with detailed travel information of individual citizens. This raises considerable privacy and security concerns [14]. It leads to a renewed interest in anonymous credential systems, offering attribute-based authorisation. With such system a smart card may be personalised, but does not show its identity on entry into a public transport system. Instead it shows an attribute — such as “first class train pass valid in December 2009” — together with a signature on the public key of the card that is linked to this attribute. The corresponding private key is assumed to be stored in protected hardware in the card, inaccessible from the outside. We assume the attribute to be fairly general, and not identifying individual cards/people. The signature, however, is specific, and may be used for tracing. Therefore we are interested in self-blindable signatures as proposed by Verheul [25].

Other credential systems exist, see for instance [5, 6, 8]. They typically require non-trivial computational resources, such that implementing them on smart cards is a serious challenge, see for example [12, 21, 23]. Of these Danes [12] implements idemix [8] zero knowledge proofs on smart cards, with running times in the order of tens of seconds; Sterckx et al. [21] implement direct anonymous attestation [6] with running times under 3 seconds; Tews and Jacobs [23] describe an implementation of Brands' selective disclosure protocols [5], with running times around 5 seconds. All quoted times refer to the execution time on a smart card.

This paper distinguishes itself through its use of elliptic curve cryptography (ECC). It does so for two (main) reasons.

Actual use of ECC on smart cards is relatively new. The major deployment is probably in the latest generation of European e-passports, using Extended Access Control to protect finger prints [7]. Java Card generation 2.2 smart cards offer support for ECC, through the cryptographic coprocessor, basically via only two primitives, namely Diffie-Hellman key agreement (ECDH) and Digital Signature Algorithm (ECDSA). This is barely enough to implement our protocol on a card efficiently. Crucial in our implementation are the following two points.

The main contributions of this work are as follows.

Our results show that anonymous credentials on smart cards are becoming feasible. Also, they show that increasing access to the cryptographic coprocessor may increase the number of applications of advanced smart cards. Hopefully this perspective stimulates card manufacturers.

This paper is organised as follows. In Section 2 an overview of elliptic curve cryptography and pairings is given. These techniques are used for the protocol given in Section 3. Finally, Section 4 describes the implementation details and gives an indication of times needed for protocol runs, with a number of different parameters.

5   Conclusions

In line with results of others [12, 21, 23] this paper demonstrates that implementations of anonymous credential systems with smart cards are becoming possible. One important bottleneck (and source of frustration) remains the limited access offered to the coprocessor on current Java Card smart cards. This paper uses elliptic curves (with pairings) and abuses Diffie-Hellman key agreement for (scalar) point multiplication, together with several other tricks, to bring on-card computation times down to around 1.5 seconds. We expect to be able to further reduce this time via additional optimisations.

References

  1. Barreto, P., Naehrig, M.: Pairing-friendly elliptic curves of prime order. In: Selected Areas in Cryptography - SAC 2005. LNCS, vol. 3897, pp. 319-331. Springer (2006)
  2. Blake, I., Seroussi, G., Smart, N.P.: Advances in Elliptic Curve Cryptography. No. 317 in LMS, Cambridge Univ. Press (2005)
  3. Boneh, D., Franklin, M.: Identity-based encryption from the Weil pairing. In: Advances in Cryptology - CRYPTO 2001. LNCS, vol. 2139, pp. 213-229. Springer (2001)
  4. Boneh, D., Lynn, B., Shacham, H.: Short signatures from the Weil pairing. Journal of Cryptology 17(4), 297-319 (2004)
  5. Brands, S.: Rethinking Public Key Infrastructures and Digital Certificates: Building in Privacy. MIT (2000)
  6. Brickell, E.F., Camenisch, J., Chen, L.: Direct anonymous attestation. In: Pfitzmann, B., Liu, P. (eds.) Computer and Communications Security - CCS 2004. pp. 132-145. ACM (2004)
  7. BSI: Advanced security mechanisms for machine readable travel documents - Extended Access Control (EAC). Tech. Rep. TR-03110, German Federal Office for Information Security (BSI) (2008)
  8. Camenisch, J., van Herreweghen, E.: Design and implementation of the idemix anonymous credential system. In: Computer and Communications Security - CCS 2002. pp. 21-30. ACM (2002)
  9. Camenisch, J., Lysyanskaya, A.: Signature schemes and anonymous credentials from bilinear maps. In: Advances in Cryptology - CRYPTO 2004. LNCS, vol. 3152, pp. 56-72 (2004)
  10. Chaum, D.: Blind signatures for untraceable payments. In: Chaum, D., Rivest, R.L., Sherman, A.T. (eds.) Advances in Cryptology - CRYPTO 1982. pp. 199-203. Plenum Press (1983)
  11. Chen, Z.: Java Card Technology for Smart Cards: Architecture and Programmer's Guide. Java Series, Addison-Wesley (2000)
  12. Danes, L.: Smart card integration in the pseudonym system idemix. Master's thesis, University of Groningen, the Netherlands (2007)
  13. ECRYPTII: Yearly report on algorithms and keysizes (2008-2009). Tech. Rep. D.SPA.7, European Network of Excellence in Cryptology II (ECRYPTII) (2009)
  14. Jacobs, B.: Architecture is politics: Security and privacy issues in transport and beyond. In: Gutwirth, S., Poullet, Y., Hert, P. (eds.) Data Protection in a Profiled World - CPDP 2008. Springer (2010)
  15. Johnson, D., Menezes, A.: The elliptic curve digital signature algorithm (ECDSA). Tech. Rep. CORR 99-34, Department of Combinatorics & Optimization, University of Waterloo, Canada (2000)
  16. Joux, A.: A one round protocol for tripartite Diffie-Hellman. Journal of Cryptology 17(4), 263-276 (2004)
  17. Kiyomoto, S., Tanaka, T.: Anonymous attribute authentication scheme using self-blindable certificates. In: Intelligence and Security Informatics - ISI 2008. pp. 215-217. IEEE (2008)
  18. NXP: Smart solutions for smart services (z-card 2009). NXP Literature, Document 75016728 (2009)
  19. Paradinas, P., Cordry, J., Bouzefrane, S.: Performance evaluation of Java Card bytecodes. In: Sauveron, D., Markantonakis, K., Bilas, A., Quisquater, J.J. (eds.) Information Security Theory and Practices - WISTP 2007. LNCS, vol. 4462, pp. 127-137. Springer (2007)
  20. Smart, N.: Elliptic curve based protocols. In: Blake, I., Seroussi, G., Smart, N. (eds.) Advances in Elliptic Curve Cryptography. pp. 3-19. No. 317 in LMS, Cambridge Univ. Press (2005)
  21. Sterckx, M., Gierlichs, B., Preneel, B., Verbauwhede, I.: Efficient implementation of anonymous credentials on Java Card smart cards. In: Information Forensics and Security - WIFS 2009. pp. 106-110. IEEE (2009)
  22. Sun Microsystems, Inc.: Java Card 2.2.2 Application Programming Interface Specification (2006)
  23. Tews, H., Jacobs, B.: Performance issues of selective disclosure and blinded issuing protocols on Java Card. In: Markowitch, O., Bilas, A., Hoepman, J.H., Mitchell, C., Quisquater, J.J. (eds.) Information Security Theory and Practice - WISTP 2009. LNCS, vol. 5746, pp. 95-111. Springer (2009)
  24. Vercauteren, F.: Pairings on elliptic curves. In: Joye, M., Neven, G. (eds.) Identity-Based Cryptography. CIS, vol. 2, pp. 13-30. IOS Press (2009)
  25. Verheul, E.: Self-blindable credential certificates from the Weil pairing. In: Boyd, C. (ed.) Advances in Cryptology - ASIACRYPT 2001. LNCS, vol. 2248, pp. 533-550. Springer (2001)