
-
Previous Article
Another look at success probability of linear cryptanalysis
- AMC Home
- This Issue
-
Next Article
Landscape Boolean functions
Embedding cover-free families and cryptographical applications
Department of Electrical Engineering and Computer Science, University of Ottawa, Ottawa, ON, Canada |
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.
References:
[1] |
D. Boneh, C. Gentry, B. Lynn and H. Shacham, Aggregate and verifiably encrypted signatures from bilinear maps, In: Biham E. (eds) Advances in Cryptology – EUROCRYPT 2003. Lecture Notes in Comput. Sci., vol 2656, Springer, Berlin, Heidelberg, 2003, 416–432.
doi: 10.1007/3-540-39200-9_26. |
[2] |
K. A. Bush,
Orthogonal arrays of index unity, Ann. Math. Statistics, 23 (1952), 426-434.
doi: 10.1214/aoms/1177729387. |
[3] |
C. J. Colbourn and J. H. Dinitz, Handbook of Combinatorial Designs, Second Edition, Chapman & Hall/CRC, 2007. |
[4] |
D. Z. Du and F. K. Hwang, Combinatorial Group Testing and Its Applications, World Scientific, 2000.
![]() |
[5] |
P. Erdös, P. Frankl and Z. Füredi,
Families of finite sets in which no set is covered by the union of r others, Israel J. Math., 51 (1985), 79-89.
doi: 10.1007/BF02772959. |
[6] |
Z. Füredi,
On r-Cover-free Families, J. Combin. Theory Ser. A, 73 (1996), 172-173.
doi: 10.1006/jcta.1996.0012. |
[7] |
E. Gafni, J. Staddon and Y. L. Yin, Efficient Methods for Integrating Traceability and Broadcast Encryption, In: Wiener M. (eds) Advances in Cryptology – CRYPTO 1999. Lecture Notes in Comput. Sci., vol 1666, Springer, Berlin, Heidelberg, 1999, 372–387.
doi: 10.1007/3-540-48405-1_24. |
[8] |
G. Hartung, B. Kaidel, A. Koch, J. Koch and A. Rupp, Fault-tolerant aggregate signatures., In Public-Key Cryptography – PKC 2016. Lecture Notes in Comput. Sci., vol 9614, Springer, Cham, 2016, 331–356.
doi: 10.1007/978-3-662-49384-7_13. |
[9] |
T. B. Idalino and L. Moura, Efficient unbounded fault-tolerant aggregate signatures using nested cover-free families, In: Iliopoulos C., Leong H., Sung WK. (eds) Combinatorial Algorithms – IWOCA 2018. Lecture Notes in Comput. Sci., vol 10979, Springer, Cham, 2018, 52–64.
doi: 10.1007/978-3-319-94667-2_5. |
[10] |
T. B. Idalino, L. Moura, R. F. Custódio and D. Panario,
Locating modifications in signed data for partial data integrity, Inform. Process. Lett., 115 (2015), 731-737.
doi: 10.1016/j.ipl.2015.02.014. |
[11] |
K. M. Kim, Perfect Hash Families: Constructions and Applications, Master's thesis, University of Waterloo, 2003. Google Scholar |
[12] |
P. C. Li, G. H. J. van Rees and R. Wei,
Constructions of 2-cover-free families and related separating hash families, J. Combin. Des., 14 (2006), 423-440.
doi: 10.1002/jcd.20109. |
[13] |
S. Ling, H. Wang and C. Xing, Cover-Free Families and Their Applications, In: Security in Distributed and Networking Systems, chapter 4, 2007. Google Scholar |
[14] |
J. Pastuszak, J. Pieprzyk and J. Seberry, Codes identifying bad signature in batches, In: Roy B., Okamoto E. (eds) Progress in Cryptology – INDOCRYPT 2000. Lecture Notes in Comput. Sci., vol 1977, Springer, Berlin, Heidelberg, 2000, 143–154.
doi: 10.1007/3-540-44495-5_13. |
[15] |
J. Pieprzyk, H. Wang and C. Xing, Multiple-time signature schemes against adaptive chosen message attacks, In: Matsui M., Zuccherato R.J. (eds) Selected Areas in Cryptography – SAC 2003. Lecture Notes in Comput. Sci., vol 3006, Springer, Berlin, Heidelberg, 2004, 88–100.
doi: 10.1007/978-3-540-24654-1_7. |
[16] |
I. S. Reed and G. Solomon,
Polynomial codes over certain finite fields, J. Soc. Indust. Appl. Math., 8 (1960), 300-304.
doi: 10.1137/0108018. |
[17] |
R. Safavi-Naini and H. Wang, New results on multi-receiver authentication codes, In: Nyberg K. (eds) Advances in Cryptology – EUROCRYPT 1998. Lecture Notes in Comput. Sci., vol 1403, Springer, Berlin, Heidelberg, 1998, 527–541.
doi: 10.1007/BFb0054151. |
[18] |
J. N. Staddon, D. R. Stinson and R. Wei,
Combinatorial properties of frameproof and traceability codes, IEEE Trans. Inform. Theory, 47 (2001), 1042-1049.
doi: 10.1109/18.915661. |
[19] |
B. Stevens and E. Mendelsohn,
Packing arrays, Theoret. Comput. Sci., 321 (2004), 25-148.
doi: 10.1016/j.tcs.2003.06.004. |
[20] |
D. R. Stinson and R. Wei,
Combinatorial properties and constructions of traceability schemes and frameproof codes, SIAM J. Discrete Math., 11 (1998), 41-53.
doi: 10.1137/S0895480196304246. |
[21] |
D. R. Stinson and R. Wei,
Generalized cover-free families, Discrete Math., 279 (2004), 463-477.
doi: 10.1016/S0012-365X(03)00287-5. |
[22] |
D. R. Stinson, R. Wei and K. Chen,
On generalized separating hash families, J. Combin. Theory Ser. A, 115 (2008), 105-120.
doi: 10.1016/j.jcta.2007.04.005. |
[23] |
D. R. Stinson, R. Wei and L. Zhu,
New constructions for perfect hash families and related structures using combinatorial designs and codes, J. Combin. Des., 8 (2000), 189-200.
doi: 10.1002/(SICI)1520-6610(2000)8:3<189::AID-JCD4>3.0.CO;2-A. |
[24] |
G. M. Zaverucha and D. R. Stinson, Group testing and batch verification, In: Kurosawa K. (eds) Information Theoretic Security – ICITS 2009. Lecture Notes in Comput. Sci., vol 5973, Springer, Berlin, Heidelberg, 2009, 140–157.
doi: 10.1007/978-3-642-14496-7_12. |
[25] |
G. M. Zaverucha and D. R. Stinson,
Short one-time signatures, Adv. Math. Commun., 5 (2011), 473-488.
doi: 10.3934/amc.2011.5.473. |
show all references
References:
[1] |
D. Boneh, C. Gentry, B. Lynn and H. Shacham, Aggregate and verifiably encrypted signatures from bilinear maps, In: Biham E. (eds) Advances in Cryptology – EUROCRYPT 2003. Lecture Notes in Comput. Sci., vol 2656, Springer, Berlin, Heidelberg, 2003, 416–432.
doi: 10.1007/3-540-39200-9_26. |
[2] |
K. A. Bush,
Orthogonal arrays of index unity, Ann. Math. Statistics, 23 (1952), 426-434.
doi: 10.1214/aoms/1177729387. |
[3] |
C. J. Colbourn and J. H. Dinitz, Handbook of Combinatorial Designs, Second Edition, Chapman & Hall/CRC, 2007. |
[4] |
D. Z. Du and F. K. Hwang, Combinatorial Group Testing and Its Applications, World Scientific, 2000.
![]() |
[5] |
P. Erdös, P. Frankl and Z. Füredi,
Families of finite sets in which no set is covered by the union of r others, Israel J. Math., 51 (1985), 79-89.
doi: 10.1007/BF02772959. |
[6] |
Z. Füredi,
On r-Cover-free Families, J. Combin. Theory Ser. A, 73 (1996), 172-173.
doi: 10.1006/jcta.1996.0012. |
[7] |
E. Gafni, J. Staddon and Y. L. Yin, Efficient Methods for Integrating Traceability and Broadcast Encryption, In: Wiener M. (eds) Advances in Cryptology – CRYPTO 1999. Lecture Notes in Comput. Sci., vol 1666, Springer, Berlin, Heidelberg, 1999, 372–387.
doi: 10.1007/3-540-48405-1_24. |
[8] |
G. Hartung, B. Kaidel, A. Koch, J. Koch and A. Rupp, Fault-tolerant aggregate signatures., In Public-Key Cryptography – PKC 2016. Lecture Notes in Comput. Sci., vol 9614, Springer, Cham, 2016, 331–356.
doi: 10.1007/978-3-662-49384-7_13. |
[9] |
T. B. Idalino and L. Moura, Efficient unbounded fault-tolerant aggregate signatures using nested cover-free families, In: Iliopoulos C., Leong H., Sung WK. (eds) Combinatorial Algorithms – IWOCA 2018. Lecture Notes in Comput. Sci., vol 10979, Springer, Cham, 2018, 52–64.
doi: 10.1007/978-3-319-94667-2_5. |
[10] |
T. B. Idalino, L. Moura, R. F. Custódio and D. Panario,
Locating modifications in signed data for partial data integrity, Inform. Process. Lett., 115 (2015), 731-737.
doi: 10.1016/j.ipl.2015.02.014. |
[11] |
K. M. Kim, Perfect Hash Families: Constructions and Applications, Master's thesis, University of Waterloo, 2003. Google Scholar |
[12] |
P. C. Li, G. H. J. van Rees and R. Wei,
Constructions of 2-cover-free families and related separating hash families, J. Combin. Des., 14 (2006), 423-440.
doi: 10.1002/jcd.20109. |
[13] |
S. Ling, H. Wang and C. Xing, Cover-Free Families and Their Applications, In: Security in Distributed and Networking Systems, chapter 4, 2007. Google Scholar |
[14] |
J. Pastuszak, J. Pieprzyk and J. Seberry, Codes identifying bad signature in batches, In: Roy B., Okamoto E. (eds) Progress in Cryptology – INDOCRYPT 2000. Lecture Notes in Comput. Sci., vol 1977, Springer, Berlin, Heidelberg, 2000, 143–154.
doi: 10.1007/3-540-44495-5_13. |
[15] |
J. Pieprzyk, H. Wang and C. Xing, Multiple-time signature schemes against adaptive chosen message attacks, In: Matsui M., Zuccherato R.J. (eds) Selected Areas in Cryptography – SAC 2003. Lecture Notes in Comput. Sci., vol 3006, Springer, Berlin, Heidelberg, 2004, 88–100.
doi: 10.1007/978-3-540-24654-1_7. |
[16] |
I. S. Reed and G. Solomon,
Polynomial codes over certain finite fields, J. Soc. Indust. Appl. Math., 8 (1960), 300-304.
doi: 10.1137/0108018. |
[17] |
R. Safavi-Naini and H. Wang, New results on multi-receiver authentication codes, In: Nyberg K. (eds) Advances in Cryptology – EUROCRYPT 1998. Lecture Notes in Comput. Sci., vol 1403, Springer, Berlin, Heidelberg, 1998, 527–541.
doi: 10.1007/BFb0054151. |
[18] |
J. N. Staddon, D. R. Stinson and R. Wei,
Combinatorial properties of frameproof and traceability codes, IEEE Trans. Inform. Theory, 47 (2001), 1042-1049.
doi: 10.1109/18.915661. |
[19] |
B. Stevens and E. Mendelsohn,
Packing arrays, Theoret. Comput. Sci., 321 (2004), 25-148.
doi: 10.1016/j.tcs.2003.06.004. |
[20] |
D. R. Stinson and R. Wei,
Combinatorial properties and constructions of traceability schemes and frameproof codes, SIAM J. Discrete Math., 11 (1998), 41-53.
doi: 10.1137/S0895480196304246. |
[21] |
D. R. Stinson and R. Wei,
Generalized cover-free families, Discrete Math., 279 (2004), 463-477.
doi: 10.1016/S0012-365X(03)00287-5. |
[22] |
D. R. Stinson, R. Wei and K. Chen,
On generalized separating hash families, J. Combin. Theory Ser. A, 115 (2008), 105-120.
doi: 10.1016/j.jcta.2007.04.005. |
[23] |
D. R. Stinson, R. Wei and L. Zhu,
New constructions for perfect hash families and related structures using combinatorial designs and codes, J. Combin. Des., 8 (2000), 189-200.
doi: 10.1002/(SICI)1520-6610(2000)8:3<189::AID-JCD4>3.0.CO;2-A. |
[24] |
G. M. Zaverucha and D. R. Stinson, Group testing and batch verification, In: Kurosawa K. (eds) Information Theoretic Security – ICITS 2009. Lecture Notes in Comput. Sci., vol 5973, Springer, Berlin, Heidelberg, 2009, 140–157.
doi: 10.1007/978-3-642-14496-7_12. |
[25] |
G. M. Zaverucha and D. R. Stinson,
Short one-time signatures, Adv. Math. Commun., 5 (2011), 473-488.
doi: 10.3934/amc.2011.5.473. |




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 |
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 |
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 | 4294967296 | 4294967296 |
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 | 4294967296 | 4294967296 |
0 | 4 | 1 | 2 | 16 | 12 | 1.33 |
1 | 16 | 7 | 2 | 4294967296 | 240 | 17895697.07 |
2 | 256 | 127 | 2 | 65280 | ||
3 | 65536 | 32767 | 2 | 4294901760 |
0 | 4 | 1 | 2 | 16 | 12 | 1.33 |
1 | 16 | 7 | 2 | 4294967296 | 240 | 17895697.07 |
2 | 256 | 127 | 2 | 65280 | ||
3 | 65536 | 32767 | 2 | 4294901760 |
0 | 4 | 1 | 3 | 16 | 16 | 1 |
1 | 16 | 5 | 3 | 16777216 | 256 | 65536 |
2 | 256 | 85 | 3 | 65536 | ||
3 | 65536 | 21845 | 3 | 4294967296 |
0 | 4 | 1 | 3 | 16 | 16 | 1 |
1 | 16 | 5 | 3 | 16777216 | 256 | 65536 |
2 | 256 | 85 | 3 | 65536 | ||
3 | 65536 | 21845 | 3 | 4294967296 |
Feature | ||||
Corollary 1 | fixed | increasing |
||
Corollary 2 | increasing | fixed | optimal ratio | |
Theorem 3.5 | fixed | fixed | monotone |
Feature | ||||
Corollary 1 | fixed | increasing |
||
Corollary 2 | increasing | fixed | optimal ratio | |
Theorem 3.5 | fixed | fixed | monotone |
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 |
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
Tools
Metrics
Other articles
by authors
[Back to Top]