The "blinded identities" problem is one of the oldest that we have discussed here (although not much recently, of course!). It is basically similar to what cryptographers call "blinded credentials" and is closely related to electronic cash, as Michael Froomkin's example from Stefan Brands points out. I posted an idea a few years ago for how to use the technique to solve the related problem of remailer abuse. A simple way to approximate what you want is to use a standard blinded signature exactly as is done with David Chaum's DigiCash. The customer comes to you and presents some proof of identity. This may be in person via standard paper documents, or on-line via some cryptographic credential as you suggested. You make a list of all of your customers, and make sure that this customer is new, someone you haven't seen before. Now you simply give him a blinded cryptographic signature, of exactly the same form as the blinded coins given out by DigiCash. He unblinds it, and he is left with a signed credential from you, but one which is unlinkable to his identity. When he interacts with you, he displays this credential as proof that he is a customer in good standing. If he violates the terms of your contract, you disable the credential (add it to a list of bad credentials). He can't use this one any more, and he can't get a new one because he is on the list of people who already got their credential. This simple solution suffers from several problems, some of which are endemic to this class of solutions and others which can be addressed with fancier crypto. Among the fundamental problems we have first that verifying identity reliably is difficult to impossible. If people are motivated badly enough, they can forge whatever documents they need. Then they keep signing up with new identities like the kids who use AOL throwaway accounts. Second, if the customer ever loses his credential, he is screwed. He comes to you with some sob story about how his disk crashed and his dog ate his backups, but you have no way of knowing if he actually lost his credential, or if he is an abuser who got his credential cancelled. Another problem is that groups of users can share credentials, so that some hacker club can get a bunch, one for each of them, and then they can all abuse your ISP, getting credentials cancelled, but able to keep going as long as one is left. Problems which can be fixed include that credentials could be stolen, like phone card numbers, so an innocent person gets his credential cancelled and then we are back to the second problem above. You can mostly solve this by having him create a key when he first registers with his credential and require all his interactions to be protected by this key. There are also more elaborate solutions where he wouldn't actually send his credential over, but use zero knowledge techniques to prove that he had one. Unfortunately David Chaum has a pretty good set of patents covering blind signatures, so for a commercial venture you'd probably have to look into the legal situation. I can send you a list of Chaum's patents in the area if you want it. (I had it on my web page but my ISP quit so I need to get a new page going.) Some of the other practical issues are also mentioned in Michael Froomkin's article, like waiting a while after you get your credential before you use it. Hal