# American Institute of Mathematical Sciences

November  2019, 13(4): 629-643. doi: 10.3934/amc.2019039

## Embedding cover-free families and cryptographical applications

 Department of Electrical Engineering and Computer Science, University of Ottawa, Ottawa, ON, Canada

Received  October 2018 Published  June 2019

Fund Project: Thais Bardini Idalino acknowledges funding granted from CNPq-Brazil [233697/2014-4] and OGS. Lucia Moura was supported by an NSERC discovery grant

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.

Citation: Thais Bardini Idalino, Lucia Moura. Embedding cover-free families and cryptographical applications. Advances in Mathematics of Communications, 2019, 13 (4) : 629-643. doi: 10.3934/amc.2019039
##### References:

show all references

##### References:
Example of a $2$-CFF($9,12$) used in group testing
Example of a 0-CFF(3; 9), 1-CFF(6; 9) and a 2-CFF(9; 9)
Example of a 4-CFF(81; 729)
Compression ratio for $q = 16,256; 1 \leq k \leq 3,; d = \log_4 n$
An SHF(2; 6; 4; {1; 2})
Example of prioritizing $d$ increases with fixed $k = 2$
 $i$ $q$ $k$ $d$ $n$ $t$ $n/t$ 0 4 2 1 64 12 5.33 1 16 2 7 4096 240 17.06 2 256 2 127 16777216 65280 257.00 3 65536 2 32767 281474976710656 4294901760 65537.00
 $i$ $q$ $k$ $d$ $n$ $t$ $n/t$ 0 4 2 1 64 12 5.33 1 16 2 7 4096 240 17.06 2 256 2 127 16777216 65280 257.00 3 65536 2 32767 281474976710656 4294901760 65537.00
Example of prioritizing $d$ increases with fixed $k = 3$
 $i$ $q$ $k$ $d$ $n$ $t$ $n/t$ 0 4 3 1 256 16 16 1 16 3 5 65536 256 256 2 256 3 85 4294967296 65536 65536 3 65536 3 21845 $65536^4$ 4294967296 4294967296
 $i$ $q$ $k$ $d$ $n$ $t$ $n/t$ 0 4 3 1 256 16 16 1 16 3 5 65536 256 256 2 256 3 85 4294967296 65536 65536 3 65536 3 21845 $65536^4$ 4294967296 4294967296
Example of prioritizing ratio increase with fixed $d = 2$
 $i$ $q$ $k$ $d$ $n$ $t$ $n/t$ 0 4 1 2 16 12 1.33 1 16 7 2 4294967296 240 17895697.07 2 256 127 2 $256^{128}$ 65280 $2.75 \times 10^{303}$ 3 65536 32767 2 $65536^{32768}$ 4294901760 $6.04 \times 10^{157816}$
 $i$ $q$ $k$ $d$ $n$ $t$ $n/t$ 0 4 1 2 16 12 1.33 1 16 7 2 4294967296 240 17895697.07 2 256 127 2 $256^{128}$ 65280 $2.75 \times 10^{303}$ 3 65536 32767 2 $65536^{32768}$ 4294901760 $6.04 \times 10^{157816}$
Example of prioritizing ratio increase with fixed $d = 3$
 $i$ $q$ $k$ $d$ $n$ $t$ $n/t$ 0 4 1 3 16 16 1 1 16 5 3 16777216 256 65536 2 256 85 3 $256^{86}$ 65536 $1.95 \times 10^{202}$ 3 65536 21845 3 $65536^{21846}$ 4294967296 $1.54 \times 10^{105211}$
 $i$ $q$ $k$ $d$ $n$ $t$ $n/t$ 0 4 1 3 16 16 1 1 16 5 3 16777216 256 65536 2 256 85 3 $256^{86}$ 65536 $1.95 \times 10^{202}$ 3 65536 21845 3 $65536^{21846}$ 4294967296 $1.54 \times 10^{105211}$
Summary of results for $k \geq 2$
 $k$ $d$ $\rho(n)$ Feature Corollary 1 fixed $d \sim \frac{n^{1/(k+1)}}{k}$ $n^{1-\frac{2}{k+1}}$ increasing $d$ Corollary 2 increasing fixed $\frac{n}{\log n}$ optimal ratio Theorem 3.5 fixed fixed $n^{1 - \frac{1}{k+1}}$ monotone
 $k$ $d$ $\rho(n)$ Feature Corollary 1 fixed $d \sim \frac{n^{1/(k+1)}}{k}$ $n^{1-\frac{2}{k+1}}$ increasing $d$ Corollary 2 increasing fixed $\frac{n}{\log n}$ optimal ratio Theorem 3.5 fixed fixed $n^{1 - \frac{1}{k+1}}$ monotone
Compression ratio for $q = 16,256;1 \leq k \leq 3; d = \log_4 n$
 $q$ $k$ $d$ $n$ $t$ $\rho(n)=n/t$ 16 1 3 128 64 2.00 16 1 4 256 80 3.20 16 2 4 512 144 3.55 16 2 5 1024 176 5.81 16 2 5 2048 176 11.63 16 2 6 4096 208 19.69 256 2 6 8192 3328 2.46 256 2 7 16384 3840 4.26 256 2 7 32768 3840 8.53 256 2 8 65536 4352 15.05 256 2 8 131072 4352 30.11 256 2 9 262144 4864 53.89 256 2 9 524288 4864 107.78 256 2 10 1048576 5376 195.04 256 2 10 2097152 5376 390.09 256 2 11 4194304 5888 712.34 256 2 11 8388608 5888 1424.69 256 2 12 16777216 6400 2621.44 256 3 12 33554432 9472 3542.48 256 3 13 67108864 10240 6553.60 256 3 13 134217728 10240 13107.20
 $q$ $k$ $d$ $n$ $t$ $\rho(n)=n/t$ 16 1 3 128 64 2.00 16 1 4 256 80 3.20 16 2 4 512 144 3.55 16 2 5 1024 176 5.81 16 2 5 2048 176 11.63 16 2 6 4096 208 19.69 256 2 6 8192 3328 2.46 256 2 7 16384 3840 4.26 256 2 7 32768 3840 8.53 256 2 8 65536 4352 15.05 256 2 8 131072 4352 30.11 256 2 9 262144 4864 53.89 256 2 9 524288 4864 107.78 256 2 10 1048576 5376 195.04 256 2 10 2097152 5376 390.09 256 2 11 4194304 5888 712.34 256 2 11 8388608 5888 1424.69 256 2 12 16777216 6400 2621.44 256 3 12 33554432 9472 3542.48 256 3 13 67108864 10240 6553.60 256 3 13 134217728 10240 13107.20
 [1] A. A. Kirillov. Family algebras. Electronic Research Announcements, 2000, 6: 7-20. [2] Artur Avila, Carlos Matheus, Jean-Christophe Yoccoz. The Kontsevich–Zorich cocycle over Veech–McMullen family of symmetric translation surfaces. Journal of Modern Dynamics, 2019, 14: 21-54. doi: 10.3934/jmd.2019002 [3] S. Gatti, M. Grasselli, V. Pata, M. Squassina. Robust exponential attractors for a family of nonconserved phase-field systems with memory. Discrete & Continuous Dynamical Systems - A, 2005, 12 (5) : 1019-1029. doi: 10.3934/dcds.2005.12.1019 [4] Juan J. Nieto, M. Victoria Otero-Espinar, Rosana Rodríguez-López. Dynamics of the fuzzy logistic family. Discrete & Continuous Dynamical Systems - B, 2010, 14 (2) : 699-717. doi: 10.3934/dcdsb.2010.14.699 [5] Godofredo Iommi, Bartłomiej Skorulski. Multifractal analysis for the exponential family. Discrete & Continuous Dynamical Systems - A, 2006, 16 (4) : 857-869. doi: 10.3934/dcds.2006.16.857 [6] Linh V. Nguyen. A family of inversion formulas in thermoacoustic tomography. Inverse Problems & Imaging, 2009, 3 (4) : 649-675. doi: 10.3934/ipi.2009.3.649 [7] Fuchen Zhang, Xiaofeng Liao, Guangyun Zhang, Chunlai Mu, Min Xiao, Ping Zhou. Dynamical behaviors of a generalized Lorenz family. Discrete & Continuous Dynamical Systems - B, 2017, 22 (10) : 3707-3720. doi: 10.3934/dcdsb.2017184 [8] Sorin Micu, Jaime H. Ortega, Lionel Rosier, Bing-Yu Zhang. Control and stabilization of a family of Boussinesq systems. Discrete & Continuous Dynamical Systems - A, 2009, 24 (2) : 273-313. doi: 10.3934/dcds.2009.24.273 [9] Oliver Juarez-Romero, William Olvera-Lopez, Francisco Sanchez-Sanchez. A simple family of solutions for forest games. Journal of Dynamics & Games, 2017, 4 (2) : 87-96. doi: 10.3934/jdg.2017006 [10] Jean-François Biasse, Michael J. Jacobson, Jr.. Smoothness testing of polynomials over finite fields. Advances in Mathematics of Communications, 2014, 8 (4) : 459-477. doi: 10.3934/amc.2014.8.459 [11] Shouchuan Hu, Xin Lu. Cover page and Preface. Conference Publications, 2015, 2015 (special) : i-i. doi: 10.3934/proc.2015.2015.si [12] Bastian Laubner, Dierk Schleicher, Vlad Vicol. A combinatorial classification of postsingularly finite complex exponential maps. Discrete & Continuous Dynamical Systems - A, 2008, 22 (3) : 663-682. doi: 10.3934/dcds.2008.22.663 [13] B. S. Lee, Arif Rafiq. Strong convergence of an implicit iteration process for a finite family of Lipschitz $\phi -$uniformly pseudocontractive mappings in Banach spaces. Numerical Algebra, Control & Optimization, 2014, 4 (4) : 287-293. doi: 10.3934/naco.2014.4.287 [14] Bernard Ducomet, Alexander Zlotnik, Ilya Zlotnik. On a family of finite-difference schemes with approximate transparent boundary conditions for a generalized 1D Schrödinger equation. Kinetic & Related Models, 2009, 2 (1) : 151-179. doi: 10.3934/krm.2009.2.151 [15] Shinji Imahori, Yoshiyuki Karuno, Kenju Tateishi. Pseudo-polynomial time algorithms for combinatorial food mixture packing problems. Journal of Industrial & Management Optimization, 2016, 12 (3) : 1057-1073. doi: 10.3934/jimo.2016.12.1057 [16] Rafael De La Llave, Michael Shub, Carles Simó. Entropy estimates for a family of expanding maps of the circle. Discrete & Continuous Dynamical Systems - B, 2008, 10 (2&3, September) : 597-608. doi: 10.3934/dcdsb.2008.10.597 [17] Jana Majerová. Correlation integral and determinism for a family of $2^\infty$ maps. Discrete & Continuous Dynamical Systems - A, 2016, 36 (9) : 5067-5096. doi: 10.3934/dcds.2016020 [18] John Sheekey. A new family of linear maximum rank distance codes. Advances in Mathematics of Communications, 2016, 10 (3) : 475-488. doi: 10.3934/amc.2016019 [19] Tarik Aougab, Stella Chuyue Dong, Robert S. Strichartz. Laplacians on a family of quadratic Julia sets II. Communications on Pure & Applied Analysis, 2013, 12 (1) : 1-58. doi: 10.3934/cpaa.2013.12.1 [20] Gamaliel Blé. External arguments and invariant measures for the quadratic family. Discrete & Continuous Dynamical Systems - A, 2004, 11 (2&3) : 241-260. doi: 10.3934/dcds.2004.11.241

2018 Impact Factor: 0.879

## Tools

Article outline

Figures and Tables