Embedding cover-free families and cryptographical applications
Thaís Bardini Idalino, Lucia Moura · Advances in Mathematics of Communications · 2019
Cover-free families are set systems used as solutions for a large variety of problems, and in particular, problems where we deal with $ n $ elements and want to identify $ d $ defective ones among them by performing only $ t $ tests ($ t \leq n $). We are especially interested in cryptographic problems, and we note that some of these problems need cover-free families with an increasing size $ n $. Solutions that propose the increase of $ n $, such as monotone families and nested families, have been recently considered in the literature. In this paper, we propose a generalization that we call embedding families, which allows us to increase both $ n $ and $ d $. We propose constructions of embedding families using polynomials over finite fields embedded via extension fields; we study how different parameter combinations can be used to prioritize increase of $ d $ or of the compression ratio as $ n $ grows. We also provide new constructions for monotone families with improved compression ratio. Finally, we show how to use embedded sequences of orthogonal arrays and packing arrays to build embedding families.