zbMATH — the first resource for mathematics

Secure frameproof codes, key distribution patterns, group testing algorithms and related structures. (English) Zbl 1054.94013
Summary: Frameproof codes were introduced by Boneh and Shaw as a method of ”digital fingerprinting” which prevents a coalition of a specified size c from framing a user not in the coalition. Stinson and Wei then gave a combinatorial formulation of the problem in terms of certain types of extremal set systems. In this paper, we study frameproof codes that provide a certain (weak) form of traceability. We extend our combinatorial formulation to address this stronger requirement, and show that the problem is solved by using \((i,j)\)-separating systems, as defined by Friedman, Graham and Ullman. Using constructions based on perfect hash families, we give the first efficient explicit constructions for these objects for general values of \(i\) and \(j\). We also review nonconstructive existence results that are based on probabilistic arguments.
Then we look at two other, related concepts, namely key distribution patterns and nonadaptive group testing algorithms. We again approach these problems from the point of view of extremal set systems, and we describe a natural common setting in which these two problems are complementary special cases. This approach also demonstrates a close relationship between these two problems and frameproof codes. Explicit constructions are given, and some nonconstructive existence results are reviewed. In the case of key distribution patterns, our explicit constructions are the most efficient ones known.

94A62 Authentication, digital signatures and secret sharing
Full Text: DOI
[1] Alon, N., Spencer, J.H., 1992. The Probabilistic Method. Wiley, New York.
[2] Atici, M.; Magliveras, S.S.; Stinson, D.R.; Wei, W.-D., Some recursive constructions for perfect hash families, J. combin. des., 4, 353-363, (1996) · Zbl 0914.68087
[3] Biehl, I., Meyer, B., 1997. Protocols for collusion-secure asymmetric fingerprinting. 14th Symposium on Theoretical Aspects of Computing. Lecture Notes in Computer Science, Vol. 1200, Springer, Berlin, pp. 399-412.
[4] Blackburn, S., 1999. Combinatorics and threshold cryptography. In Combinatorial Designs and their Applications, Chapman and Hall Research Notes in Mathematics, Vol. 403, pp. 49-70. · Zbl 0932.94029
[5] Blackburn, S., Burmester, M., Desmedt, Y., Wild, P.R., 1996. Efficient multiplicative sharing schemes. Advances in Cryptology — Eurocrypt ’96. Lecture Notes in Computer Science, Vol. 1070. Springer, Berlin, pp. 107-118. · Zbl 1304.94095
[6] Boneh, D., Shaw, J., 1995. Collusion-secure fingerprinting for digital data. Advances in Cryptology — Crypto ’95. Lecture Notes in Computer Science, Vol. 963. Springer, Berlin, pp. 452-465. · Zbl 0876.94024
[7] Bush, K.A.; Federer, W.T.; Pesotan, H.; Raghavarao, D., New combinatorial designs and their application to group testing, J. statist. plann. inference, 10, 335-343, (1984) · Zbl 0571.62062
[8] Chee, Y.M., 1996. Turán-type problems in group testing, coding theory and cryptography. Ph.D. Thesis, University of Waterloo.
[9] Chor, B., Fiat, A., Naor, M., 1994. Tracing traitors. Advances in Cryptology — Crypto ’94. Lecture Notes in Computer Science, Vol. 839. Springer, Berlin, pp. 257-270. · Zbl 0939.94555
[10] Du, D.-Z., Hwang, F.K., 1993. Combinatorial Group Testing and Applications. World Scientific, Singapore. · Zbl 0867.90060
[11] Dyachkov, A.G.; Rykov, V.V.; Rashad, A.M., Superimposed distance codes, Problems control inform. theory, 18, 237-250, (1989) · Zbl 0693.94005
[12] Dyer, M.; Fenner, T.; Frieze, A.; Thomason, A., On key storage in secure networks, J. cryptol., 8, 189-200, (1995) · Zbl 0840.94015
[13] Erdös, P.; Frankl, P.; Füredi, Z., Families of finite sets in which no set is covered by the union of two others, J. combin. theory A, 33, 158-166, (1982) · Zbl 0489.05003
[14] Erdös, P.; Frankl, P.; Füredi, Z., Families of finite sets in which no set is covered by the union of r others, Isreal J. math., 51, 75-89, (1985) · Zbl 0587.05021
[15] Fiat, A., Naor, M., 1994. Broadcast encryption. Advances in Cryptology — Crypto ’93, Lecture Notes in Computer Science, Vol. 773. Springer, Berlin, pp. 480-491. · Zbl 0870.94026
[16] Friedman, A.D.; Graham, R.Ł.; Ullman, J.D., Universal single transition time asynchronous state assignments, IEEE trans. comput., C-18, 541-547, (1969)
[17] Gong, L.; Wheeler, D.L., A matrix key-distribution scheme, J cryptol., 2, 51-59, (1990) · Zbl 0701.94007
[18] Hwang, F.K.; Sós, V.T., Nonadaptive hypergeometric group testing, Stud. sci. math. hungar., 22, 257-263, (1987) · Zbl 0639.62076
[19] Kautz, W.H.; Singleton, R.G., Nonrandom binary superimposed codes, IEEE trans. inform. theory, 10, 363-373, (1964) · Zbl 0133.12402
[20] Körner, J.; Simonyi, G., Separating partition systems and locally different sequences, SIAM J. discrete math., 1, 355-359, (1988) · Zbl 0723.05039
[21] Körner, J., On the extremal combinatorics of the Hamming space, J. combin. theory A, 71, 112-126, (1995) · Zbl 0826.05054
[22] Mehlhorn, K., 1982. On the program size of perfect and universal hash functions. In Proceedings of 23rd Annual IEEE Symposium on Foundations of Computer Science, pp. 170-175.
[23] Mehlhorn, K., 1984. Data Structures and Algorithms, Vol. 1. Springer, Berlin. · Zbl 0556.68002
[24] Mitchell, C.J.; Piper, F.C., Key storage in secure networks, Discrete appl. math., 21, 215-228, (1988) · Zbl 0661.94012
[25] Pfitzmann, B., 1996. Trials of traced traitors. Workshop on Information Hiding, Lecture Notes in Computer Science, Vol. 1174. Springer, Berlin, pp. 49-64.
[26] Pfitzmann, B., Schunter, M., 1996. Asymmetric fingerprinting. Advances in Cryptology — Eurocrypt ’96. Lecture Notes in Computer Science, Vol. 1070. Springer, Berlin, pp. 84-95. · Zbl 1304.94081
[27] Pfitzmann, B., Waidner, M., 1997a. Asymmetric fingerprinting for larger collusions. Fourth ACM Conference on Computer and Communications Security.
[28] Pfitzmann, B., Waidner, M., 1997b. Anonymous fingerprinting. Advances in Cryptology — Eurocrypt ’97. Lecture Notes in Computer Science, Vol. 1233. Springer, Berlin, pp. 88-102.
[29] O’Keefe, C.M., Key distribution patterns using Minkowski planes, Des. codes cryptogr., 5, 261-267, (1995) · Zbl 0819.94023
[30] Quinn, K.A.S., Some constructions for key distribution patterns, Des. codes cryptogr., 4, 177-191, (1994) · Zbl 0790.94002
[31] Quinn, K.A.S., 1999. Bounds for key distribution patterns. J. Cryptol., to appear. · Zbl 0944.94009
[32] Quinn, K.A.S., 1982. On construction methods for key distribution patterns. Preprint.
[33] Stinson, D.R., On some methods for unconditionally secure key distribution and broadcast encryption, Des. codes cryptogr., 12, 215-243, (1997) · Zbl 0880.94009
[34] Stinson, D.R.; Van Trung, T., Some new results on key distribution patterns and broadcast encryption, Des. codes cryptogr., 14, 261-279, (1998) · Zbl 1125.94331
[35] Stinson, D.R.; Wei, R., Combinatorial properties and constructions of traceability schemes and frameproof codes, SIAM J. discrete math., 11, 41-53, (1998) · Zbl 0972.94028
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.