Radboud University Nijmegen, 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

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.

- ECC supports small key and certificate lengths — compared to RSA — and thus reduces the time and bandwidth needed for transfer (of public keys between card and terminal) and for blinding (via modular multiplication of big natural numbers).
- ECC supports a form of signature via bilinear pairings [20] which is stable under blinding [25].

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.

- We abuse ECDH to perform point multiplication (repeated addition, or integer scalar multiplication) on the card. Diffie-Hellman does such a multiplication implicitly, however, it only returns the
*x*-coordinate of the resulting (multiplied) point. In principle, we have to reconstruct the corresponding*y*-coordinate (on the reader-side) by taking a square root, and checking which version (positive or negative) is the right one. However, we show how this reconstruction can be partially avoided via some tricks (see Section 4.2). - Modular multiplication of two (big) natural numbers is not supported, that is, the Java Card API does not provide access to this operation on the card's cryptographic coprocessor. Therefore we use our own implementation in Java Card, which leads to a significant slow down. It can be mitigated by reducing the number of bits in the blinding factor, for instance from 192 to 96 (or even to 48).

The main contributions of this work are as follows.

- A new protocol for anonymous credentials is described that can be used for various applications which require smart cards, in particular e-ticketing.
- An implementation of this protocol, via several optimisations, on an ordinary Java Card, using bilinear pairings on elliptic curves on the terminal-side.
- A running time on the card in the order of 1.5 seconds.

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.

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.

- 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)
- Blake, I., Seroussi, G., Smart, N.P.: Advances in Elliptic Curve Cryptography. No. 317 in LMS, Cambridge Univ. Press (2005)
- 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)
- Boneh, D., Lynn, B., Shacham, H.: Short signatures from the Weil pairing. Journal of Cryptology 17(4), 297-319 (2004)
- Brands, S.: Rethinking Public Key Infrastructures and Digital Certificates: Building in Privacy. MIT (2000)
- 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)
- 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)
- 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)
- 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)
- 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)
- Chen, Z.: Java Card Technology for Smart Cards: Architecture and Programmer's Guide. Java Series, Addison-Wesley (2000)
- Danes, L.: Smart card integration in the pseudonym system idemix. Master's thesis, University of Groningen, the Netherlands (2007)
- ECRYPTII: Yearly report on algorithms and keysizes (2008-2009). Tech. Rep. D.SPA.7, European Network of Excellence in Cryptology II (ECRYPTII) (2009)
- 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)
- 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)
- Joux, A.: A one round protocol for tripartite Diffie-Hellman. Journal of Cryptology 17(4), 263-276 (2004)
- Kiyomoto, S., Tanaka, T.: Anonymous attribute authentication scheme using self-blindable certificates. In: Intelligence and Security Informatics - ISI 2008. pp. 215-217. IEEE (2008)
- NXP: Smart solutions for smart services (z-card 2009). NXP Literature, Document 75016728 (2009)
- 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)
- 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)
- 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)
- Sun Microsystems, Inc.: Java Card 2.2.2 Application Programming Interface Specification (2006)
- 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)
- Vercauteren, F.: Pairings on elliptic curves. In: Joye, M., Neven, G. (eds.) Identity-Based Cryptography. CIS, vol. 2, pp. 13-30. IOS Press (2009)
- 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)