We present a new way of doing authentication and digital signatures. Previously, digital signatures based on hash functions involved hundreds of hash function computations; our `Guy Fawkes Protocol' enables users to sign messages using only two computations of a hash function and one reference to a timestamping service. We also show how to sign digital streams, and give an integrity equivalent of Diffie-Hellman: two people who share no secret can set up a securely serialised channel into which attackers cannot subsequently intrude. In addition to being of potential use in real applications, our constructions raise interesting questions about the definition of a digital signature.

Click Here to download this article