Abstract
Various kinds of fingerprinting codes and their related combinatorial structures are extensively studied for protecting copyrighted materials. This paper concentrates on one specialised fingerprinting code named wide-sense frameproof codes in order to prevent innocent users from being framed. Let Q be a finite alphabet of size q. Given a t-subset \(X=\{ x ^1,\ldots , x ^t \}\subseteq Q^n\), a position i is called undetectable for X if the values of the words of X match in their ith position: \(x_i^1=\cdots =x_i^t\). The wide-sense descendant set of X is defined by \({{\text {wdesc}}}(X)=\{y\in Q^n:y_i=x_i^1,i\in {U}(X)\},\) where U(X) is the set of undetectable positions for X. A code \(\mathcal{C}\subseteq Q^n\) is called a wide-sense t-frameproof code if \({{\text {wdesc}}}(X) \cap \mathcal{C} = X\) for all \(X \subseteq \mathcal{C}\) with \(|X| \le t\). The paper improves the upper bounds on the sizes of wide-sense 2-frameproof codes by applying techniques on non 2-covering Sperner families and intersecting families in extremal set theory.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alon N., Fischer E., Szegedy M.: Parent-identifying codes. J. Comb. Theory A 95(2), 349–359 (2001).
Anderson I.: Combinatorics of Finite Sets, Dover Publications. INC, Mineola (1987).
Barg A., Blakley G.R., Kabatiansky G.A.: Digital fingerprinting codes: problem statements, constructions, identification of traitors. IEEE Trans. Inf. Theory 49(4), 852–865 (2003).
Barg A., Cohen G., Encheva S., Kabatiansky G., Zémor G.: A hypergraph approach to the identifying parent property: the case of multiple parents. SIAM J. Discret. Math. 14(3), 423–431 (2001).
Blackburn S.R.: An upper bound on the size of a code with the \(k\)-identifiable parent property. J. Comb. Theory A 102(1), 179–185 (2003).
Blackburn S.R.: Combinatorial schemes for protecting digital content, surveys in combinatorics, In: C.D. Wensley (ed.), London Mathematical Society Lecture Note Series, vol. 307, pp. 43-78. Cambridge University Press, Cambridge (2003).
Blackburn S.R.: Frameproof codes. SIAM J. Discret. Math. 16(3), 499–510 (2003).
Blackburn S.R., Etzion T., Ng S.-L.: Traceability codes. J. Comb. Theory A 117(8), 1049–1057 (2010).
Boneh D., Shaw J.: Collusion-secure fingerprinting for digital data. IEEE Trans. Inf. Theory 44(5), 1897–1905 (1998).
Chee Y.: Tur\(\acute{a}\)n-Type Problems in Group Testing, Coding Theory and Cryptography. Department of Computer Science, University of Waterloo, Waterloo (1996).
Chee Y., Zhang X.: Improved constructions of frameproof codes. IEEE Trans. Inf. Theory 58(8), 5449–5453 (2012).
Cheng M., Miao Y.: On anti-collusion codes and detection algorithms for multimedia fingerprinting. IEEE Trans. Inf. Theory 57(7), 4843–4851 (2011).
Chor B., Fiat A., Naor M.: Tracing traitors. In: Y.G. Desmedt (ed.) Advances in Cryptology-CRYPTO’94. Lecture Notes in Computer Science, vol. 839, pp. 257–270. Springer, Berlin (1994).
Cohen G., Encheva S.: Efficient constructions of frameproof codes. Electron. Lett. 36(22), 1840–1842 (2000).
Engel K.: Sperner Theory (Encyclopedia of Mathematics and Its Applications Book). Cambridge University Press, Cambridge (1997).
Fiat A., Tassa T.: Dynamic traitor tracing. J. Cryptol. 14(3), 211–223 (2001).
Guo C., Stinson D.R., Van Trung T.: On tight bounds for binary frameproof codes. Des. Codes Cryptogr. 77(2–3), 301–319 (2015).
Jukna S.: Extremal Combinatorics: With Applications in Computer Science, 2nd edn. Springer, Berlin (2011).
Katona G.O.H.: Intersection theorems for systems of finite sets. Acta Math. Acad. Sci. Hung. 15(3), 329–337 (1964).
Milner E.C.: A combinatorial theorem on systems of sets. J. Lond. Math. Soc. s1–43(1), 204–206 (1968).
Panoui A.: Wide-Sense Fingerprinting Codes and Honeycomb Arrays. Royal Holloway, University of London, Egham (2012).
Shangguan C., Ma J., Ge G.: New upper bounds for parent-identifying codes and traceability codes. Des. Codes Cryptogr. 86(8), 1727–1737 (2018).
Shangguan C., Wang X., Ge G., Miao Y.: New bounds for frameproof codes. IEEE Trans. Inf. Theory 63(11), 7247–7252 (2017).
Staddon J.N., Stinson D.R., Wei R.: Combinatorial properties of frameproof and traceability codes. IEEE Trans. Inf. Theory 47(3), 1042–1049 (2001).
Stinson D.R., van Trung T., Wei R.: Secure frameproof codes, key distribution patterns, group testing algorithms and related structures. J. Stat. Plan. Inference 86(2), 595–617 (2000).
Stinson D.R., Wei R.: Combinatorial properties and constructions of traceability schemes and frameproof codes. SIAM J. Discret. Math. 11, 41–53 (1998).
Stinson D.R., Wei R., Chen K.: On generalized separating hash families. J. Comb. Theory A 115(1), 105–120 (2008).
Van Trung T.: A tight bound for frameproof codes viewed in terms of separating hash families. Des. Codes Cryptogr. 72(3), 713–718 (2014).
Xing C.: Asymptotic bounds on frameproof codes. IEEE Trans. Inf. Theory 48(11), 2991–2995 (2002).
Yang Y., Zhang Y., Ge G.: New lower bounds for secure codes and related hash families: a hypergraph theoretical approach. IEEE Trans. Inf. Theory 63(4), 2446–2453 (2017).
Acknowledgements
The authors would like to thank the anonymous referees for their helpful comments and valuable suggestions, which have greatly improved the presentation and quality of this paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by J. D. Key.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Supported by NSFC Grants 11571034 and 11971053.
Rights and permissions
About this article
Cite this article
Zhou, J., Zhou, W. Wide-sense 2-frameproof codes. Des. Codes Cryptogr. 88, 2507–2519 (2020). https://doi.org/10.1007/s10623-020-00797-w
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10623-020-00797-w