An example of the kind of token transformation I'm thinking of follows. Assume RSA signatures from the site that looks at your ID having public key (e,m) where

An example of the kind of token transformation I'm thinking of follows. Assume RSA signatures from the site that looks at your ID having public key (e,m) where e is the exponent and m is the modules, and private key d. The signature s of a blob of data, b, that you give them is b^d mod m. To verify the signature one computes s^e mod m and checks if that matches b. Here's the transformation. You generate a random r from 1 to m-1 such that r is relatively prime to m. Compute r' such that r r' = 1 mod m. Instead of sending b to be signed, send b r^e mod m. The signature s of b r^e is (b r^e)^d mod m = b^d r mod m. You take that signature and multiply by r'. That gives you b^d mod m. Note that this is the signature you would have gotten had you sent them b to sign instead of b r^e. Net result: you've obtained the signature of b, but the signing site never saw b. They just saw b r^e mod m. That gives them no useful information about b, due to r being a random number that you picked (assuming you used a good random number generator!). For any possible b, as long as it is relatively prime to m, there is some r that would result in b r^e having the same signature as your b, so the signing site has no way to tell which is really yours. b is unlikely to not be relatively prime to m. If m is the product of two large primes, as is common, b is relatively prime to it unless one of those primes divides b. We can ensure that b is relatively prime to m by simply limiting b to be smaller than either of the prime factors of m. Since those factors are likely to each be over a thousand bits this is not hard. In practice b would probably be something like a random 128 bits.