Paper 2016/052

Fault-Tolerant Aggregate Signatures

Gunnar Hartung, Björn Kaidel, Alexander Koch, Jessica Koch, and Andy Rupp


Aggregate signature schemes allow for the creation of a short aggregate of multiple signatures. This feature leads to significant reductions of bandwidth and storage space in sensor networks, secure routing protocols, certificate chains, software authentication, and secure logging mechanisms. Unfortunately, in all prior schemes, adding a single invalid signature to a valid aggregate renders the whole aggregate invalid. Verifying such an invalid aggregate provides no information on the validity of any individual signature. Hence, adding a single faulty signature destroys the proof of integrity and authenticity for a possibly large amount of data. This is largely impractical in a range of scenarios, e.g. secure logging, where a single tampered log entry would render the aggregate signature of all log entries invalid. In this paper, we introduce the notion of fault-tolerant aggregate signature schemes. In such a scheme, the verification algorithm is able to determine the subset of all messages belonging to an aggregate that were signed correctly, provided that the number of aggregated faulty signatures does not exceed a certain bound. We give a generic construction of fault-tolerant aggregate signatures from ordinary aggregate signatures based on cover-free families. A signature in our scheme is a small vector of aggregated signatures of the underlying scheme. Our scheme is bounded, i.e. the number of signatures that can be aggregated into one signature must be fixed in advance. However the length of an aggregate signature is logarithmic in this number. We also present an unbounded construction, where the size of the aggregate signature grows linearly in the number of aggregated messages, but the factor in this linear function can be made arbitrarily small. The additional information encoded in our signatures can also be used to speed up verification (compared to ordinary aggregate signatures) in cases where one is only interested in verifying the validity of a single message in an aggregate, a feature beyond fault-tolerance that might be of independent interest. For concreteness, we give an instantiation using a suitable cover-free family.

Available format(s)
Public-key cryptography
Publication info
Published by the IACR in PKC 2016
Aggregate SignaturesFault-ToleranceCover-free Family
Contact author(s)
gunnar hartung @ kit edu
2016-01-22: received
Short URL
Creative Commons Attribution


      author = {Gunnar Hartung and Björn Kaidel and Alexander Koch and Jessica Koch and Andy Rupp},
      title = {Fault-Tolerant Aggregate Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2016/052},
      year = {2016},
      doi = {10.1007/978-3-662-49384-7_13},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.