Efficient U-Prove Implementation for Anonymous Credentials on Smart Cards

Wojciech Mostowski*, and Pim Vullers**
Institute for Computing and Information Sciences,
Digital Security group, Radboud University Nijmegen, The Netherlands.
In this paper we discuss an efficient implementation of anonymous credentials on smart cards. In general, privacy-preserving protocols are computationally intensive and require the use of advanced cryptography. Implementing such protocols for smart cards involves a trade-off between the requirements of the protocol and the capabilities of the smart card. In this context we concentrate on the implementation of Microsoft's U-Prove technology on the MULTOS smart card platform. Our implementation aims at making the smart card independent of any other resources, either computational or storage. In contrast, Microsoft suggests an alternative approach based on device-protected tokens which only uses the smart card as a security add-on. Given our very good performance results we argue that our approach should be considered in favour of Microsoft's one. Furthermore we provide a brief comparison between Java Card and MULTOS which illustrates our choice to implement this technology on the latter more flexible and low-level platform rather than the former.
anonymous credentials, smart cards, U-Prove, MULTOS, Java Card
*Sponsored by the NL-Net Foundation through the OV-chipkaart project.
** Sponsored by Trans Link Systems/Open Ticketing.

1   Introduction

An effort to provide citizens with electronic signature (e-signature) capable identity cards is currently in progress in many European Union countries. The first countries to introduce such cards were Belgium and Estonia. More recently (November 2010) Germany introduced a new generation identity card [6] for their citizens, which also provides a limited form of anonymous attributes for improved privacy. Although Dutch identity cards already contain a chip with personal data, like in the e-passport, there is no e-signature functionality available yet. The Dutch government is currently working on adding e-signature capability, and possibly support for attributes, to such a card.

The e-signature application on the identity cards serves two major purposes. First, what is in the name, they can be used to digitally sign documents, for example tax return forms. Next, and probably most, they are used to provide strong authentication of the owner of the card, mainly for logging into governmental web services. But this use of signing or authentication certificates also involves a restriction of this use case. In the Netherlands the use of the social security number, which is integrated in the identity card, is by law only allowed within the government domain.

Therefore we study methods of authentication and authorisation which preserve the privacy of the card holder and restrict linkability of card uses. For example, the card holder may wish to prove his age category (an adult over 18 or a senior over 65) without revealing his actual date of birth. One way to achieve this is to use attributes instead of identities. A number of technologies [1, 4, 7] have been developed based on this idea, but the main focus has been on the cryptography and less on (efficient) implementations. The implementations which have been made are mainly for ordinary computers. Our research focuses on implementing and using such technologies on smart cards. This approach offers various new use cases, but also faces difficulties due to the limited capabilities of smart card platforms and hardware.

The work that we present here targets the U-Prove technology developed by Brands [4] and now owned and marketed by Microsoft [3]. Out of the existing privacy-aware protocols [3, 5, 8], this one has not yet been implemented on a smart card in its current specification. The current U-Prove specification [11] does support the use of a smart card as an additional protection device. In this scenario the card performs only a fraction of the protocol run. This is motivated by the constrained resources of smart cards and was already described by Brands in 2000 [4]. In Table 1 this approach is compared with our approach which offers the full protocol implementation on a smart card. We provide the full implementation of the U-Prove protocols to solve the main disadvantage of Microsoft's approach: the smart card cannot be used independently, since it is tied to computational (and storage) resources external to the card. This means that it requires a specific, card matching terminal, like the card owner's PC, to run the protocols.

Table 1. Comparison between Microsoft's device-protected U-Prove token approach and our U-Prove token on a smart card approach.

Microsoft's approach our approach
characteristics add-on security measure full protocol implementation
card stores single device-protection attribute all attributes, other token values
card computes short zero-knowledge proof for
the device-protection attribute
complete presentation proof
advantages fast, lightweight, protect any
number of dynamically issued tokens using pre-issued devices
independent use of the card, no need to trust the terminal
disadvantages trusted terminal required requires more card resources (?)

For performance our primary goal was to keep the running times of the protocol on the card sufficient for on-line use.1 Despite the obvious efficiency concern caused by our choice to implement the full U-Prove protocols on a smart card, we managed to provide a very efficient implementation. Our worst-case execution time of the protocol on the card (with five attributes) is 0.87 seconds. Configuring the implementation for a smaller number of attributes improves this running time considerably. This makes our implementation efficient enough to be possibly considered also for the use in e-ticketing, where transactions with a card should be at or below 0.3 seconds.2 This discards the disadvantage of our approach mentioned in Table 1, offering an overall better solution than Microsoft's approach. Thus, Microsoft is advised to change its approach to smart card support for U-Prove. Our good result is mostly due to the choice of the smart card implementation platform. Because of its more convenient API, we used a MULTOS smart card [10] in favour of the more popular Java Card platform [9]. The former has been overlooked as a prototyping platform whereas the latter exhibited questionable efficiency in some previous privacy-friendly protocol implementations [2, 12, 13].

The rest of this paper is organised as follows. Section 2 provides the necessary background on privacy-preserving protocols, related work, and open smart card platforms. We describe our MULTOS U-Prove implementation in Section 3, focusing on the implementation challenges without explaining the U-Prove protocols in detail.3 Section 4 discusses the results of our work and compares Java Card with MULTOS. Further steps in our research on privacy-preserving protocols are presented in Section 5, and finally Section 6 concludes the paper.

1 The proving scenario should be fast (less then a second) whereas the less frequently run issuance scenario can take a few seconds to complete a transaction.
2 http://www.smartcardalliance.org/resources/lib/Transit_Financial_Linkages_WP.pdf
3 A detailed description of the protocols can be found in the U-Prove cryptographic specification [3] and the mathematical background is addressed in Brands' book [4].

6   Conclusions

We have presented an efficient MULTOS implementation of the U-Prove technology that allows to run the complete prover side of the protocols on a smart card. This provides an anonymity friendly credentials mechanism for users of such a smart card, with full independence from authentication resources external to the smart card. From the user perspective, the most performance sensitive part of the protocol is attribute proving. Here, the achieved worst-case running times of 0.87 seconds for the whole set of attributes clearly establishes the practical usability of our implementation. Our performance results also strongly support our idea to use a stand-alone U-Prove smart card rather than the Microsoft device-protection approach, which seems to overlook the current capabilities of smart cards. One other thing that seems to be overlooked by scientists and smart card developers is the existence of the MULTOS smart card platform. During our work it proved itself highly flexible and reasonably fast, hence our next steps are to implement and assess the performance of other anonymity friendly protocols, primarily Idemix, in a (MULTOS) smart card setting.


We are grateful to Jaap-Henk Hoepman, Bart Jacobs, Christian Paquin, Erik Poll and the anonymous reviewers for their valuable comments which helped to improve this work.


  1. Batina, L., Hoepman, J.H., Jacobs, B., Mostowski, W., Vullers, P.: Developing efficient blinded attribute certificates on smart cards via pairings. In: Gollmann, D., Lanet, J.L. (eds.) Smart Card Research and Advanced Applications -- CARDIS 2010. LNCS, vol. 6035, pp. 209--222. Springer-Verlag (April 2010)
  2. Bichsel, P., Camenisch, J., Groß, T., Shoup, V.: Anonymous credentials on a standard Java Card. In: Computer and Communications Security -- CCS 2009. pp. 600--610. ACM (November 2009)
  3. Brands, S., Paquin, C.: U-Prove cryptographic specification v1.0. Tech. rep., Microsoft Corporation (March 2010)
  4. Brands, S.A.: Rethinking Public Key Infrastructures and Digital Certificates: Building in Privacy. MIT Press (August 2000)
  5. 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 (October 2004)
  6. Bundesamt für Sicherheit in der Informationstechnik: Advanced security mechanisms for machine readable travel documents, Version 2.05. Tech. Rep. TR-03110, German Federal Office for Information Security (BSI), Bonn, Germany (2010)
  7. Camenisch, J., Lysyanskaya, A.: An efficient system for non-transferable anonymous credentials with optional anonymity revocation. In: Advances in Cryptology -- EUROCRYPT 2001. pp. 93--118. Springer-Verlag (May 2001)
  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 (November 2002)
  9. Chen, Z.: Java Card Technology for Smart Cards: Architecture and Programmer's Guide. Java Series, Addison-Wesley (June 2000)
  10. France-Massey, T.: MULTOS -- the high security smart card {OS}. Tech. rep., MAOSCO Limited (September 2005)
  11. Paquin, C.: U-Prove cryptographic specification v1.1. Tech. rep., Microsoft Corporation (February 2011)
  12. 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 (September 2009)
  13. 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-Verlag (September 2009)