Spliced signatures

Tech report: High throughput asynchronous algorithms for message authentication

Abstract
Public-key digital signatures are a mainstay of cryptographic protocols and are widely used in practice. However, the performance gap between digital signatures and conventional cryptographic operations is significant, particularly with Internet messaging systems, chat systems, and the like, which would like to generate and verify digital signatures at high speeds. Consequently, our research considers hybrid schemes, derived from Merkle trees and newer hash-based data structures, that can optimize signing and verification of messages in bulk, while still preserving traditional single-message signature and verifications semantics. We show that hash trees can increase the signing throughput of any public key signature algorithm to tens of thousands of messages per second. In addition, our system's throughput degrades gracefully when the requested message signature rate saturates the CPU. Our techniques similarly create efficiencies when verifying groups of messages from the same source. In particular, by delaying any given signature verification until it's absolutely necessary, we can often verify multiple messages at the same time with minimal additional cost. We verify our system with detailed microbenchmarks of our hybrid signature algorithms as well as full-system simulations driven from traces taken from Google Wave.

A PDF version of the tech report is available.

@techreport{crosbyfastsig,
    author = {Scott A. Crosby and Dan S. Wallach},
    title = {High throughput asynchronous algorithms for message authentication},
    institution = {Rice University},
    number = {CS TR10-15},
    address = {Houston, TX},
    month = dec,
    year = 2010
}

Code

The Java code implementing these algorithms and an asynchronous signing and verifying API is posted up at: The code implementing these algorithms is available locally here and at github at https://github.com/scrosby/fastsig. This code includes the reference implementation of the History tree.