HORSE: an extension of an r-time signature scheme with fast signing and verification

Source authentication of messages is a valuable tool in communication networks where the source of a message can easily be spoofed. Often, when two parties are communicating, a shared-key message authentication code is sufficient for providing source authentication to both parties. Unfortunately, the utility of a MAC does not extend to a broadcast situation involving three or more parties, so public-key digital signatures have traditionally been used to attain source authentication in group broadcast communications. In this paper, we introduce HORSE, an r-time signature scheme that yields source authentication in the group setting like a public-key signature scheme, only with signature and verification times much closer to those of a MAC. Additionally, HORSE makes much more efficient use of its keys than previous r-time signature schemes.