Abstract
We consider how to avoid unsolicited e-mail – so called spam – in a stronger adversarial model than has previously been considered. Our primary concern is the proposal of an architecture and of protocols preventing against successful spamming attacks launched by a strong attacker. This attacker is assumed to control the communication media and to be capable of corrupting large numbers of protocol participants. Additionally, the same architecture can be used as a basis to support message integrity and privacy, though this is not a primary goal of our work. This results in a simple and efficient solution that is largely backwards-compatible while inter-posing new processing modules, and which addresses many of the concerns surrounding e-mail communication.

Keywords
authentication, e-mail, lightweight, spam, strong adversary