Fast anonymous credentials on smart cards

My group in Nijmegen, together with colleagues from TNO, have been working on efficient implementations of anonymous credentials on smart cards. Last year we managed to implement a simple authentication protocol (using self-blindable credentials) that executes a full protocol run in roughly 1.6 seconds on the card. We will present these results at the CARDIS 2010 conference at Passau, Germany, in a few weeks. But we have made some interesting progress the last month, that allows us to run the protocol in 0.6 seconds on the card instead.

Self blindable credentials were invented by Eric Verheul¹ in 2001. They can be constructed using elliptic curve cryptography, and use a so-called pairing function e with the following property

e(aP,bQ) = e(P,Q)^ab,

(where P and Q are points on the curve, and a and b are natural numbers). On elliptic curves, multiplication behaves a bit like exponentiation on groups of natural numbers. In particular, when P is known and aP given, a is hard to compute.

Let card i have a private k_i and corresponding public key K_i = k_iP. Let the certification authority have private key a and public key A = aQ. The signs the public key of the card using a. This yields a certificate C_i = aK_i.

The authentication protocol now runs as follows. First the card generates a random blinding factor b and sends bK_i, bC_i (ie the blinded public key and certificate) to the terminal. The terminal receives K, C and verifies whether the first is certified by the second using the following test: e(C,Q) = e(K,A). The terminal then generates a random nonce n and requests a signature from the card. The card signs this with his blinded private key using (r,s) = signECDSA(n,bk_i). The terminal verifies whether verifyECDSA(r,s,K) holds using the blinded public key K it received earlier.

The results cited above apply to such curves using 128 bit keys (and 128 bit blinding factors). The main slowdown in our first implementation stemmed from the fact that we had to implement big integer multiplication in Java to compute bk_i. We use JavaCards with a crypto co-processor (of course), but the co-processor can only be accessed through an API with very limited functionality. It supports the most common EC and RSA cryptographic operations, but not plain multiplication unfortunately.

But by rewriting the protocol, and cleverly abusing the API functions that are available, we are able to improve the speed of our implementation by a factor 3. In fact the following protocol does the trick.

The terminal first generates a random nonce n and sends nP it to the card. The card receives this nonce as N. Then the card generates a random blinding factor b and sends bK_i, bC_i, bk_iN (ie the blinded public key and certificate and the response to the challenge) to the terminal. The terminal receives K, C, M and verifies whether the first is certified by the second using the following test: e(C,Q) = e(K,A). The terminal then verifies whether the challenge is correctly answered by testing M = nK.

The trick we use is to use genKeyPair() to generate a random blinding factor b. If we seed this function with the point nP it also returns (as the 'public key') the value bnP!

We are now working on implementing revocation of self-blindable credentials in an efficient manner. This is a bit tougher nut to crack than we initially thought.…