Ted Baker
Department of Computer Science
Florida State University
Tallahassee, FL 32306-4530


This short paper is to capture my ideas on how to allow a recipient of e-mail to distinguish between "serious" e-mail and the unwanted kind of mass e-mail that is usually called "spam", using a technique that I am calling here "digital stamps".

The paper is intended for members of the FSU anti-spam working group, and students in the course CEN 5035 for the Fall 2003 semester.

A quick look at the US Patent and Trademark Office web site in early 2003 showed that there were already several patents and patent applications that purport to cover one or another form of electronic stamps, and several that cover methods for filtering e-mail. I do not believe the ideas described here are the same as what was described by any of those patents at that time. However, there seemed to be a number of recently submitted patent applications in Spring 2003, some patent applications are not published, and and it is likely that more applications have been filed as the spam problem has received more and more press coverage.

The terms "digital stamp", "e-stamp", and "electronic stamp" have all been used previously, with a range of different specific meanings, including the purchase of regular postage from the US Postal Service (like a postage meter) over the Internet, and mechanisms by which one person pays an intermediatry to deliver to another person a certified electronic message.

What I am proposing here is is similar to the latter, but there is no need for a special agent to handle the message, and the content of the message is not certified.


The method of sending and receiving e-mail described here, using digital stamps, is intended to provide a means for alleviating the burden of large volumes of "spam", i.e. unwanted bulk e-mail. It provides a means for distinguishing different classes of incoming e-mail, so as to be able to both filter out unwanted mail and to guarantee that certain wanted classes of e-mail are not filtered out.


Our method is intended to satisfy the following specific constraints:

  1. It allows a sender not known to the recipient to send a "first class" e-mail message with the assurance that it will not be filtered out as spam.

  2. The cost to send a first-class message can be set low enough to be competitive with regular hard-copy mail through the US Postal Service, yet high enough to make sending bulk first-class e-mail more expensive than sending regular bulk US mail.

  3. It can be used by recipients who must publish their e-mail addresses. That is it does not rely on hiding one's e-mail address. This is a critical need for organizations such as businesses, universities, and public agencies, where e-mail addresses are published to enable customers, students, and citizens to send e-mail to representatives of the organization.

  4. It does not require key distribution infrastructure. In particular, it does not require that the sender or recipient have a cryptographic key (public or private).

  5. It uses the existing Internet SMTP mail transport protocol. It should not require any changes to SMTP or any other special other handling by forwarding agents.

  6. It is backward-compatible with existing e-mail client software. That is, if the sender of a message includes a digital stamp of the kind described here, but the recipient uses mail-reading software that does not recognize such stamps, the recipient should still be able to receive and read the message without any impediment. The recipient simply will not have the added classification benefit of the stamp.

    In particular, messages can be sent in clear text. Encryption is not required. This may be important for organizations that have a policy against encrypted e-mail, because they want to be able to monitor and audit e-mail traffic. (Of course such monitoring can easily be circumvented by steganography.)

  7. It does not rely on the honesty of origin addresses in e-mail headers.

  8. It does not restrict the content of e-mail messages.

  9. It is backward-compatible with existing e-mail sender software. That is, if the sender of a message does not include a digital stamp, but the recipient is using client software that is aware of stamps, the message will be classifed as unstamped but will not necessarily be simply discarded. The recipient may, as a user-selectable option, choose to do do any of the following:

    1. Discard all unstamped messages.

    2. Reply to all stamped messages, with a challange containing insructions on how to obtain a stamp and send a stamped message.

    3. Selectively allow through certain unstamped messages, based on other filtering criteria, such as the sender address and content of the message.

  10. It is compatible with other present and future spam filtering and mail certificaion methods. If messages without stamps are not discarded they can be routed through any kind of spam filter, subjected to a challenge-response protocol, etc. As envisioned for normal use, messages with first-class stamps would not need any other filtering or other processing. However, there is nothing to prevent a recipient from doing further pre or post processing, or even applying digital encryption and certification techniques to stamped messages.

  11. If allows a recipient to allow through first-class stamped e-mail from senders whose e-mail would otherwise be filtered out as spam, for example because their addresses are in domains that have been black-listed as known sources of spam,or because spammers have used forged their addresses on e-mail in the past, or because the content of the message fits some spam profile.

  12. If a recipient of a message with a stamp wishes to reply, and establish an ongoing exchange of messages there is a way to do this without requiring either party to purchase more digital stamps. Such an exchange can be cut off at any time by either party.

  13. Stolen or intercepted stamps cannot be reused. The worst damage that can be done is to substitute one message for another.

  14. Affixing a digital stamp to a message can be automated, so that a sender can send a first-class message with a single mouse-click or keystroke, without having to do any extra steps to purchase a stamp each time a message is sent.

  15. The checking of stamps can be implemented solely by the receiver's mail reading software, but it can optionally also be implemented at any earlier point, including by the mail receiving software of the recipient's host, or by the mail server of the recipient's organization, or by a communication service provider. For example, an organization may perform filtering based on digital stamps at the point e-mail enters the local area network of the organization. If it does, it could remove the stamps at the organization boundary, after, for example, deleting unstamped mail or modifying the message subject line of unstamped mail; or, it could leave the stamps in place.

  16. Our method protects against stamp forgery, using public-key encryption.

  17. Our method protects against, or limits (subject to certain options on the part of the receiver and sender) attempts by spammers to capture and reuse stamps.

  18. However, our method is *not* intended to provide e-mail security. For example, it does not hide the content of messages, or certify that a message has not been forged or tampered with by a third party. However, it is compatible with such techniques, since it does not restrict the content or format of the message header or limit what can be put in the message body.


The method is described in terms of roles and actions of the following three parties:

Sending a message involves the following steps:

  1. Sender A requests a stamp from Vendor C. The request specifies the e-mail address of Recipient B, and optionally the e-mail address of Sender A and the window of time in for which Sender A wants the stamp to be valid.

  2. Vendor C creates a stamp and returns the stamp to Sender A. The stamp contains the information provided in the request, along with an identifier (e.g., a serial number) that is unique for each stamp. This information is encrypted and digitally signed by Vendor C. The method does not depend on a particular encryption method. For example, Vendor C may use a public-private key pair. Using C's private key, C encrypts the information in the stamp request and the unique identifier, and appends C's own identity in clear text.

    The method by which Sender A and Vendor C communicated to exchange the stamp request and the stamp is not critical to this method. Any method for secure transactions involving service for a fee might be applied. For example, Sender A may request the stamp via a Web page, using the HTTPS protocol. If more security is desired, one might use the same protocol used for Internet purchase of US Postage stamps.

    It is envisioned that, ordinarily, the purchase of a stamp would not require any extra steps by Sender A. That is, it would be peformed automatically by the e-mail software used by Sender A to send the message. If Sender A had previously contracted with Vendor C, and established a method of payment, the sending software would communicate with stamp Vendor C, obtain the stamp, and affix it to the message.

    If Sender A has not previous contracted to purchase stamps, and does not wish to establish an account for the purchase of stamps directly, or reveal A's identity, A may contract with an intermediary fourth party to both purchase the stamp and send the message.

  3. Sender A sends an e-mail message to B, including the digital stamp in the message. The stamp is placed in a conventional location in the message. The convention for the location of the stamp is not critical to the function of the method. For example, it might prepended or appended to the message body, or put into the subject field.

    Optionally, if Sender A wants to allow Recipient B to respond to the message without purchasing a new stamp, A may direct its software to log the stamp as valid for return use, and so indicate in the message.

    A sender may choose not to use this feature, since such return stamps are vulnerable to interception and illegitimate use by spammers. If this option is enabled and Sender A receives spam under the cover of a stamp logged for return use, A may log the stamp as revoked for further use. This removal could be implemented via a single mouse-click or keystroke, even as side-effect of consigning a given message to a waste bin.

  4. When the message is received by Recipient B, the mail receiving or reading software of B notices the presence of a digital stamp, extracts the identity of Vendor C, looks up the public key of Vendor C in one or more trusted public directories, and uses the public key to decrypt the stamp. Decryption of the stamp provides: a unique identifier; the address of Recipient B; optionally also the address of Sender A and a time window for which the stamp is valid.

    Recipient B's e-mail receiving or reading software checks that the stamp contains one of the recipients valid e-mail addresses. If the address is not recognized as valid for Recipient B, the stamp is ordinary rejected as invalid (but see the next paragraphs for special cases). This is to prevent a single stamp from being used for more than one recipient, i.e., to require a sender to pay for a new stamp for every recipient. This is the economic limit on huge first-class e-mailings.

    If Receipient B previously sent a message to A, with a stamp logged as valid for return or multiple use, and B sees such a stamp on an incoming message, it may choose to accept it as valid even though the stamp does not contain B's e-mail address, or even if it fails the time window test below.

    If Recipient B finds a stamp that has been previously validated for return mail or multiple use, but has been revoked because it appeared on spam, the mail receiving or reading software of B may optionally generate a reply message to the sender, indicating that the stamp has been compromised and that a fresh stamp is required.

    Optionally, the recipient's e-mail receiving or reading software checks the unique identifier against its own local log of used stamps. If the stamp is not logged as being valid for return e-mail (explained above) or multiple uses (explained further below), the stamp is rejected as invalid. This can prevent a sender from reusing a stamp for multiple messages without permission. It also prevents a network snooper from capturing addresses and stamps from legitimate stamped messages passing through the network, and using them to send out forged stamped spam to the same recipients.

    Optionally, if there is a specified time window, the mail receiving program checks that the stamp is still valid. If it is no longer valid, the stamp may be rejected. The purpose of the time stamp is to allow the recipient's mail receiver or reader to detect reused stamps without having to keep an unbounded history of used unique stamp identifiers.

  5. If Recipient B wants to reply to Sender A, and allow Sender A to reply in turn without purchasing another stamp, and B is willing to run the risk of spammers capturing and reusing the stamp, B can log the stamp as being valid for multiple uses. As in the case above of validating a stamp for reply mail, the permission to reuse a stamp can be revoked if the stamp shows up later on spam.


An objective of the basic method described above is not to require Sender A or Recipient B to exchange encryption keys, whether public or private. That is because the complexity and overhead of key management may be considered burdensome by ordinary individuals. (In contrast, the publication and maintenance of public keys by Vendor C is considered a necessary cost of doing business, and only need be one for one or a few vendors.)

However, as an option if Sender A and/or Recipient B have their own public/private key pairs, the method may be made more robust for reply mail, multiple e-mail exchanges, and even mailing lists, using public/private keys.

In particular, once contact has been established using stamps purchased through some vendor, two parties may manufacture and exchange their own stamps, acting the role of Vendor C above.

For example, B may create a stamp containing its own ID, a unique identifier, and the e-mail address of A, sign it using B's private key, encrypt it using A's public key, and send it attached to a message to A. Only A can decrypt the the stamp, extract the stamp, and attach it to a letter. This can be a multiple-use stamp, for example for use on a mailing list. To prevent a spammer from capturing and reusing the stamp, every time A attaches the stamp to a message it signs the stamp with A's private key.

© 2003, 2004 T. P. Baker. No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means without written permission.