Cover-free families, constructions and cryptographical applications

Abstract: Cover-free families have been investigated under different names such as disjunct matrices, superimposed codes and strongly selective families. They are interesting combinatorial objects used in combinatorial group testing as well as various applications in communications.

A $d$-cover-free family $d$-$\mathrm{CFF}(t,n)$ is a set system consisting of n subsets of a $t$-set, where the union of any $d$ subsets does not contain any other. In combinatorial group testing, a $d$-$\mathrm{CFF}(t, n)$ allows for the identification of up to $d$ defective elements in a set of $n$ elements by performing only $t$ tests (typically $t ≪ n$).

This talk begins with an introduction of cover-free families, constructions and applications. We then focus on applications in cryptography and in particular discuss our work in the use of cover-free families to add fault-tolerance to classical problems in cryptography. In order to add fault-tolerance in aggregation of signatures, we construct infinite sequences of cover-free families with desired properties such as high compression ratio. In the context of malleable digital signatures, we propose a method that uses cover-free families to locate modifications in signed documents. Works by the authors on this topic can be found in the proceedings of IWOCA2018 and Indocrypt2019, and in Advances in Mathematics of Communications (2019) and Theoretical Computer Science (2021).

combinatorics

Audience: researchers in the topic

( video )

---

Carleton Combinatorics Meeting 2021

Series comments: See the external webpage for more details: people.math.carleton.ca/~dthomson/CCM2021

To contact, please use CCM2021@math.carleton.ca and prefix your subject with "[CCM2021-request]"

---