# 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] Bing Gao, Rui Gao. On fair entropy of the tent family. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021017 [2] Jann-Long Chern, Sze-Guang Yang, Zhi-You Chen, Chih-Her Chen. On the family of non-topological solutions for the elliptic system arising from a product Abelian gauge field theory. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3291-3304. doi: 10.3934/dcds.2020127 [3] Buddhadev Pal, Pankaj Kumar. A family of multiply warped product semi-Riemannian Einstein metrics. Journal of Geometric Mechanics, 2020, 12 (4) : 553-562. doi: 10.3934/jgm.2020017 [4] Álvaro Castañeda, Pablo González, Gonzalo Robledo. Topological Equivalence of nonautonomous difference equations with a family of dichotomies on the half line. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020278 [5] Divine Wanduku. Finite- and multi-dimensional state representations and some fundamental asymptotic properties of a family of nonlinear multi-population models for HIV/AIDS with ART treatment and distributed delays. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021005 [6] Min Xi, Wenyu Sun, Jun Chen. Survey of derivative-free optimization. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 537-555. doi: 10.3934/naco.2020050 [7] Claude-Michel Brauner, Luca Lorenzi. Instability of free interfaces in premixed flame propagation. Discrete & Continuous Dynamical Systems - S, 2021, 14 (2) : 575-596. doi: 10.3934/dcdss.2020363 [8] Aurelia Dymek. Proximality of multidimensional $\mathscr{B}$-free systems. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021013 [9] Rong Wang, Yihong Du. Long-time dynamics of a diffusive epidemic model with free boundaries. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020360 [10] Maho Endo, Yuki Kaneko, Yoshio Yamada. Free boundary problem for a reaction-diffusion equation with positive bistable nonlinearity. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3375-3394. doi: 10.3934/dcds.2020033 [11] Maoli Chen, Xiao Wang, Yicheng Liu. Collision-free flocking for a time-delay system. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 1223-1241. doi: 10.3934/dcdsb.2020251 [12] Chueh-Hsin Chang, Chiun-Chuan Chen, Chih-Chiang Huang. Traveling wave solutions of a free boundary problem with latent heat effect. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021028 [13] Yoichi Enatsu, Emiko Ishiwata, Takeo Ushijima. Traveling wave solution for a diffusive simple epidemic model with a free boundary. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 835-850. doi: 10.3934/dcdss.2020387 [14] Shudi Yang, Xiangli Kong, Xueying Shi. Complete weight enumerators of a class of linear codes over finite fields. Advances in Mathematics of Communications, 2021, 15 (1) : 99-112. doi: 10.3934/amc.2020045 [15] Laura Aquilanti, Simone Cacace, Fabio Camilli, Raul De Maio. A Mean Field Games model for finite mixtures of Bernoulli and categorical distributions. Journal of Dynamics & Games, 2020  doi: 10.3934/jdg.2020033 [16] Huijuan Song, Bei Hu, Zejia Wang. Stationary solutions of a free boundary problem modeling the growth of vascular tumors with a necrotic core. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 667-691. doi: 10.3934/dcdsb.2020084 [17] Lei Yang, Lianzhang Bao. Numerical study of vanishing and spreading dynamics of chemotaxis systems with logistic source and a free boundary. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 1083-1109. doi: 10.3934/dcdsb.2020154 [18] Jingjing Wang, Zaiyun Peng, Zhi Lin, Daqiong Zhou. On the stability of solutions for the generalized vector quasi-equilibrium problems via free-disposal set. Journal of Industrial & Management Optimization, 2021, 17 (2) : 869-887. doi: 10.3934/jimo.2020002 [19] Liupeng Wang, Yunqing Huang. Error estimates for second-order SAV finite element method to phase field crystal model. Electronic Research Archive, 2021, 29 (1) : 1735-1752. doi: 10.3934/era.2020089 [20] Wenya Qi, Padmanabhan Seshaiyer, Junping Wang. A four-field mixed finite element method for Biot's consolidation problems. Electronic Research Archive, , () : -. doi: 10.3934/era.2020127

2019 Impact Factor: 0.734