Nested Cover-Free Families for Unbounded Fault-Tolerant Aggregate Signatures

preprint2022arXivOpen access

Abstract

Aggregate signatures are used to create one short proof of authenticity and integrity from a set of digital signatures. However, one invalid signature in the set invalidates the entire aggregate, giving no information on which signatures are valid. Hartung et al. (2016) propose a fault-tolerant aggregate signature scheme based on combinatorial group testing. Given a bound dd on the number of invalid signatures among nn signatures to be aggregated, this scheme uses dd-cover-free families to determine which signatures are invalid. These combinatorial structures guarantee a moderate increase on the size of the aggregate signature that can reach the best possible compression ratio of O(nlog⁡n)O(\frac{n}{\log n}), for fixed dd, coming from an information theoretical bound. The case where the total number of signatures grows dynamically (unbounded scheme) was not satisfactorily solved in their original paper, since explicit constructions had constant compression ratios. In the present paper, we propose efficient solutions for the unbounded scheme, relying on sequences of dd-cover-free families that we call {\em nested families}. Some of our constructions yield high compression ratio close to \rmv{the information theoretical bound}\todo{the best known upper bound}. We also propose the use of (d,λ)(d,λ)-cover-free families to support the loss of up to λ−1λ-1 parts of the aggregate.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.