Digital signatures for flows and multicasts

We present chaining techniques for signing/verifying multiple packets using a single signing/verification operation. We then present flow signing and verification procedures based upon a tree-chaining technique. Since a single signing/verification operation is amortized over many packets, these procedures improve signing and verification rates by one to two orders of magnitude, compared to the approach of signing/verifying packets individually. Our procedures do not depend upon reliable delivery of packets. They also provide delay-bounded signing, and are thus suitable for delay-sensitive flows and multicast applications. To further improve our procedures, we propose several extensions to the Feige-Fiat-Shamir (1987) digital signature scheme to substantially speed up both the signing and verification operations, as well as to allow “adjustable and incremental” verification. The extended scheme, called eFFS, is compared to four other digital signature schemes (RSA, DSA, ElGamal (1985), and Rabin). We compare their signing and verification times, as well as key and signature sizes. We observe that: (1) eFFS is the fastest in signing (by a large margin over any of the other four schemes) and as fast as RSA in verification (tie for a close second behind Rabin (1979)); (2) eFFS allows a tradeoff between memory and signing/verification time; and (3) eFFS allows adjustable and incremental verification by receivers