One idea we have often discussed is to use a public message pool such as a newsgroup or mailing list reflector as a means of receiving messages anonymously. Each message would be encrypted with my public key (or that of my pseudonym), but with the identifying information stripped. Then I need to scan them all to see which ones are encrypted to me. Those are the ones which decrypt under the public key system to a correctly padded session key. Doing it this way eavesdroppers can't even tell how much mail my nym is receiving. The problem is that doing a PK decrypt is time consuming, and if we had to do it to all the anonymous mail traffic in the world it could become impractical. I had hoped that Shamir's idea which I posted earlier would help with this, but I can't see an application. His idea helps to check for specific signatures, which is a thing anyone can do, but he lets you do it faster. We need a faster way to do a check which only the holder of the secret key can do. I have thought of a small improvement based on Shamir's ideas, though. Use Rabin encryption rather than RSA. In this system the decryption involves taking square roots. This is done by taking the square root of the ciphertext mod p and q (the two secret primes) and using the Chinese Remainder Theorem to get the square root mod n. (This is also done in RSA with eth roots.) If p and q are 3 mod 4, you can get the square root of x mod p as x^((p+1)/4) mod p. This is done for p and q and you then combine them. So the amount of work is pretty much the same as for RSA. However a speedup is possible to do a quicker check for a validly formed encrypted message. The idea is that the encrypted message is of the form M^2 mod n. This means that it is a quadratic residue mod n, and also therefore a q.r. mod p and q. So the speedup is simply to check whether it is a q.r. mod one of the primes and to reject it if not. This takes about half the amount of time to actually try the decryption. All valid messages will pass the test, and half of the invalid messages will be rejected. So this is not very strong, but it is perhaps better than nothing. Maybe Shamir will come up with some idea for this problem. As I wrote before, testing for a q.r. is done by raising to the (p-1)/2 power mod p, and seeing if the answer is 1. I think this can be done in such a way that if it does come out to be 1 we can use our intermediate results to calculate the (p+1)/4 needed for the square root very quickly. Also, BTW Rabin encryption is not specifically patented, only the relatively-untested and almost-expired patent which covers all public key systems (with the failed knapsack algorithm as its specific embodiment) would supposedly prevent its use. However even PKP is apparently becoming more reluctant to throw its weight around on this patent, while they are still quite possessive about RSA. So perhaps a migration to Rabin is in order. Hal