Practical forward secure sequential aggregate signatures

A forward secure sequential aggregate (FssAgg) signature scheme allows a signer to iteratively combine signatures generated in different time intervals - and with different keys - into a single constant-size signature. Such a signature offers forward security, storage/communication efficiency, as well as overall integrity of the signed messages. FssAgg schemes are therefore suitable for data-intensive applications on untrusted and/or unattended devices, e.g., logging systems. The first FssAgg signature scheme [21] is based on bilinear maps and is thus rather costly. In this paper, we propose two more practical FssAgg1 signature schemes. A FssAgg1 signature scheme is a special FssAgg signature scheme where exactly ONE message can be signed at each time interval and key update is invoked immediately after each signature generation. Both new schemes are derived from existing forward secure signature schemes. Unlike the scheme in [21], each new scheme has constant-size public and private keys, constant-size signatures as well as constant-time key update and signature generation complexity. We show how to apply proposed schemes in secure logging applications.