
-
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. |
[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. |
[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. |
[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. |
[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] |
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 and Continuous Dynamical Systems, 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 and 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 and Continuous Dynamical Systems, 2006, 16 (4) : 857-869. doi: 10.3934/dcds.2006.16.857 |
[6] |
Bing Gao, Rui Gao. On fair entropy of the tent family. Discrete and Continuous Dynamical Systems, 2021, 41 (8) : 3797-3816. doi: 10.3934/dcds.2021017 |
[7] |
Alexandre Alves, Mostafa Salarinoghabi. On the family of cubic parabolic polynomials. Discrete and Continuous Dynamical Systems - B, 2022, 27 (4) : 2051-2064. doi: 10.3934/dcdsb.2021121 |
[8] |
Shouchuan Hu, Xin Lu. Cover page and Preface. Conference Publications, 2015, 2015 (special) : i-i. doi: 10.3934/proc.2015.2015.si |
[9] |
Bastian Laubner, Dierk Schleicher, Vlad Vicol. A combinatorial classification of postsingularly finite complex exponential maps. Discrete and Continuous Dynamical Systems, 2008, 22 (3) : 663-682. doi: 10.3934/dcds.2008.22.663 |
[10] |
Linh V. Nguyen. A family of inversion formulas in thermoacoustic tomography. Inverse Problems and Imaging, 2009, 3 (4) : 649-675. doi: 10.3934/ipi.2009.3.649 |
[11] |
Fuchen Zhang, Xiaofeng Liao, Guangyun Zhang, Chunlai Mu, Min Xiao, Ping Zhou. Dynamical behaviors of a generalized Lorenz family. Discrete and Continuous Dynamical Systems - B, 2017, 22 (10) : 3707-3720. doi: 10.3934/dcdsb.2017184 |
[12] |
Sorin Micu, Jaime H. Ortega, Lionel Rosier, Bing-Yu Zhang. Control and stabilization of a family of Boussinesq systems. Discrete and Continuous Dynamical Systems, 2009, 24 (2) : 273-313. doi: 10.3934/dcds.2009.24.273 |
[13] |
Oliver Juarez-Romero, William Olvera-Lopez, Francisco Sanchez-Sanchez. A simple family of solutions for forest games. Journal of Dynamics and Games, 2017, 4 (2) : 87-96. doi: 10.3934/jdg.2017006 |
[14] |
Yang Liu, Wenke Li. A family of potential wells for a wave equation. Electronic Research Archive, 2020, 28 (2) : 807-820. doi: 10.3934/era.2020041 |
[15] |
Victor J. W. Guo. A family of $ q $-congruences modulo the square of a cyclotomic polynomial. Electronic Research Archive, 2020, 28 (2) : 1031-1036. doi: 10.3934/era.2020055 |
[16] |
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 |
[17] |
Inês Cruz, Helena Mena-Matos, Esmeralda Sousa-Dias. The group of symplectic birational maps of the plane and the dynamics of a family of 4D maps. Journal of Geometric Mechanics, 2020, 12 (3) : 363-375. doi: 10.3934/jgm.2020010 |
[18] |
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 and Continuous Dynamical Systems, 2020, 40 (6) : 3291-3304. doi: 10.3934/dcds.2020127 |
[19] |
Shinji Imahori, Yoshiyuki Karuno, Kenju Tateishi. Pseudo-polynomial time algorithms for combinatorial food mixture packing problems. Journal of Industrial and Management Optimization, 2016, 12 (3) : 1057-1073. doi: 10.3934/jimo.2016.12.1057 |
[20] |
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 and Optimization, 2014, 4 (4) : 287-293. doi: 10.3934/naco.2014.4.287 |
2021 Impact Factor: 1.015
Tools
Metrics
Other articles
by authors
[Back to Top]