Embedding cover-free families and cryptographical applications

Thais Bardini Idalino; Lucia Moura

doi:10.3934/amc.2019039

Article Contents

2019, Volume 13, Issue 4: 629-643. Doi: 10.3934/amc.2019039

This issue Previous Article Landscape Boolean functions Next Article Another look at success probability of linear cryptanalysis

Embedding cover-free families and cryptographical applications

Thais Bardini Idalino and
Lucia Moura

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

Received: October 2018

Published: June 2019

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

Abstract / Introduction Full Text(HTML) Figure(5) / Table(6) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 05B99, 94C12; Secondary: 11T71.

Citation:

Full Text(HTML)

Figure 1. Example of a $ 2 $-CFF($ 9,12 $) used in group testing

Download: Full-size image PowerPoint slide

Figure 2. Example of a 0-CFF(3; 9), 1-CFF(6; 9) and a 2-CFF(9; 9)

Download: Full-size image PowerPoint slide

Figure 3. Example of a 4-CFF(81; 729)

Download: Full-size image PowerPoint slide

Figure 4. Compression ratio for $ q = 16,256; 1 \leq k \leq 3,; d = \log_4 n $

Download: Full-size image PowerPoint slide

Figure 5. An SHF(2; 6; 4; {1; 2})

Download: Full-size image PowerPoint slide

Table 1. 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

| Show Table

DownLoad: CSV

Table 2. 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

| Show Table

DownLoad: CSV

Table 3. 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} $

| Show Table

DownLoad: CSV

Table 4. 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} $

| Show Table

DownLoad: CSV

Table 5. 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

| Show Table

DownLoad: CSV

Table 6. 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

| Show Table

DownLoad: CSV

Related Papers

Cited by

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.