A few weeks ago Adam Back sent me a pointer to a paper with what was basically a new anonymous credential system, by Brickell, Camenisch and Chen, http://www.hpl.hp.com/techreports/2004/HPL-2004-93.pdf. I've followed Jan Camenisch's work pretty closely over the years and although he is only the 2nd author here, the paper is very much based on his ideas. Actually the paper is about a very controversial topic, trusted computing: TCPA, TCG, TPM, the Fritz chip, etc. Despite the questions about that technology, the paper has some interesting ideas which could be applied more widely. One of the concepts in trusted computing is that the computer would have a chip in it with an embedded key. This chip is called the TPM officially but is widely known as the Fritz chip after the senator who was pushing some legislation that might mandate technology controls. Fritz Hollings is gone and so is his CBDTPA but now the FCC seems to be taking up the gauntlet. But that's another story. Anyway, the TPM generates a key internally and it gets certified by some kind of CA established by the TCG (the TCG is the new name for the TCPA). When someone wants to, say, download some DRM-protected data, they could prove they have a real TPM by providing this certificate from the TCG CA on their TPM key. This would let the data supplier know he was talking to a system with a genuine TPM that would protect the data and keep the user from defeating the DRM. That would be the simple way to work, but the TCG didn't do it that way, because having the user show his TPM certificate everywhere would violate his privacy. It may seem strange that a proposal which is built on the idea that the user is the enemy will care about his privacy, especially since most TCG uses will require the user to pay for things, meaning showing a credit card number, so he has no privacy anyway. But that's the political decision the TCG made. Instead, they came up with a "Privacy CA", where the user would in effect show his TPM certificate to the PCA, and the PCA would then certify a temporary "pseudonym key" that the user would then use in place of his TPM key and certificate. The problem here is that this doesn't protect privacy all that well, plus the PCA needs to have both high availability and high security, two requirements that don't work well together. So TCG has approved this new proposal, cryptographically based, called Direct Anonymous Attestation or DAA. There is no more Privacy CA. Instead, the user directly proves that he has a valid certificate on his TPM key, but he does it in zero knowledge. He doesn't reveal the TPM key or the certificate, nevertheless the verifier (which would typically be a seller of DRM'd content) gets convinced that he is talking to a real TPM. The way it works is a modification of a group signature. Camenisch has done a lot of work on these over the years, with various co-authors. But the general idea is the same, that group members each generate a key, which gets certified by a "group ownership manager" and that means they're officially part of the group. Then they can create signatures of which it can only be determined that they came from someone in the group, but you can't tell which one. This is done by the method described above, a zero knowledge proof that you know a key and you have a certificate (signature) on it by the group manager key. That establishes that you are a group member. One of the new ideas in the DAA paper relates to revocation. The TPM private keys are supposed to remain locked in the chip. But suppose someone uses some fancy lab equipment or perhaps a side channel attack and extracts one. They could spread it around to their friends, who could use it to pretend to have TPMs, download DRM-protected data and easily remove the protections. The TCG wanted to deal with this. The assumption is that a secret this good can't be kept quiet for long, so soon there will be lists of TPM-cracked keys floating out there. TCG-based vendors are assumed to have access to such a list, so when someone shows up with their ZK proof about having a good TPM, they want to know if the TPM key is on the list. The problem is that the TPM key is not revealed in the ZK proof. So the authors propose that, if the key is k, another value of the form u^k mod p gets revealed, where u is perhaps chosen by the vendor, or is perhaps random. This doesn't reveal k but there is a proof that the k used in u^k is the same k that got certified as a TPM key. Now the vendor can compare the reported u^k value with computed u^k based on all known "bad" keys. If it matches for any of them, he knows that he is being offered a bogus TPM key proof. That's the basic idea of the DAA, but there are two additional points of interest. The first is that DAA is really complicated, more so than most group signatures of this type I have seen. The main reason seems to be a desire to not make the TPM work too hard. The authors have cleverly and diligently split up the protocol so that as much work as possible is done by the host computer and not the TPM, even though the host is not trusted. The concept is similar to the old "wallet with observer" protocols of Chaum and Brands. But the effect is to add many extra phases and passes, which could probably be eliminated if we didn't care about that. The second point relates to the system as a credential system. This idea of proving in zero knowledge that you have a cert on your key is the basis of an earlier credential system from Camenisch and Lysyanskaya. The concept is that credentials are represented by particular signatures from particular signers. Say, AAA could give me a credential as a member for the year 2004 by a certain signature. Then I could show possession when I made a hotel reservation and get a discount, by proving that I had that signature by AAA on a key I owned. Doing it in ZK protects my privacy. I actually looked at implementing the C&L credential system a few years ago, but there was a big stumbling block right at the beginning. It would only work with an RSA key of a special form, one composed of the product of two strong primes (primes p and q where (p-1)/2 and (q-1)/2 were themselves prime). And worse, it was necessary to prove that the modulus was of that form, without of course revealing p and q. Well, Camenisch had a protocol for this, but it was very complicated. I implemented it and it was intolerably slow, it took many minutes or even hours. It just didn't appear feasible as the foundation for a practical credential system. One of the improvements in the new DAA system is that it escapes from the need to prove that the RSA key is built of strong primes. This means that it could conceivably be the foundation for a credential system that would actually be efficient enough to use. That's very exciting! Unfortunately, as I said the DAA system in its present form is not quite right; it is too complicated due to the need to split up the work between TPM and untrusted host. That complication is not necessary for a plain credentialling system. So some work would have to be done to clean it up and get it into a form that would work for credentials. Crypto is next week and I hope to see Jan there and ask him about this. If he thinks it would work then this is another project I might try in the near future. I would really like to see some kind of anonymous credential system available for people to experiment with. I had looked into doing one with ring signatures but it would not be very efficient. Camenisch's technology is far superior. Hal Finney