Abstract
Frameproof codes have been introduced for use in digital fingerprinting that prevent a coalition of \(w\) or fewer legitimate users from constructing a fingerprint of another user not in the coalition. It turns out that \(w\)-frameproof codes are equivalent to separating hash families of type \(\{1,w\}\). In this paper we prove a tight bound for frameproof codes in terms of separating hash families.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bazrafshan M., van Trung T.: Bounds for separating hash families. J. Comb. Theory Ser. A 118, 1129–1135 (2011)
Bazrafshan M.: Separating hash families, PhD thesis, University of Duisburg-Essen (2011)
Bazrafshan M., van Trung T.: Improved bounds for separating hash families. Des. Codes Cryptogr. (2012). doi:10.1007/s10623-012-9673-7
Blackburn S.R.: Frameproof codes. SIAM J. Discret. Math. 16(3), 499–510 (2003)
Blackburn S.R., Etzion T., Stinson D.R., Zaverucha G.M.: A bound on the size of separating hash families. J. Comb. Theory Ser. A 115, 1246–1256 (2008)
Boneh D., Shaw J.: Collusion-free fingerprinting for digital data. IEEE Trans. Inf. Theory 44, 1897–1905 (1998)
Bush K.A.: A generalization of a theorem due to MacNeish. Ann. Math. Stat. 23, 293–295 (1952)
Bush K.A.: Orthogonal arrays of index unity. Ann. Math. Stat. 23, 426–434 (1952)
Chor B., Fiat A., Naor M.: Tracing traitors, in advances in cryptology—CRYPTO’94. In: Desmedt, Y.G. (ed.) Lecture Notes in Computer Science, pp. 257–270. Springer, Berlin (1994)
Colbourn C.J., Horsley D., Syrotiuk V.R. Frameproof codes and compressive sensing. In: Forty-Eighth Annual Allerton Conference, Allerton House, UIUC, Illinois, USA, September 29–October 1, pp. 985–990 (2010)
Colbourn C.J., Horsley D., McLean C.: Compressive sensing matrices and hash families. Trans. Commun. 59(7), 1840–1845 (2011)
Colbourn C.J., Dinitz J.H. (eds.): The CRC Handbook of Combinatorial Designs, 2nd edn. Chapman and Hall/CRC, Boca Raton, FL (2007)
Fiat A., Tassa T.: Dynamic traitor tracing, in advances in cryptology—CRYPTO’99. In: Weiner M. (ed.) Lecture Notes in Computer Science, vol. 1666, pp. 354–371. Springer, Berlin (1999)
Li P.C., Wei R., van Rees G.H.J.: Constructions of 2-cover-free families and related separating hash families. J. Comb. Des. 14, 423–440 (2006)
Sarkar P., Stinson D.R.: Frameproof and IPP codes, progress in cryptology—Indocrypt. In: Pandu Rangan C., Ding C. (eds.) Lecture Notes in Computer Science, vol. 2247, pp. 117–126. Springer, Berlin (2001)
Staddon J.N., Stinson D.R., Wei R.: Combinatorial properties of frameproof and traceability codes. IEEE Trans. Inf. Theory 47, 1042–1049 (2001)
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., van Trung T., Wei R.: Secure frameproof codes, key distribution patterns, group testing algorithms and related structures. J. Stat. Plan. Inference 86, 595–617 (2000)
Stinson D.R., Wei R., Chen K.: On generalized separating hash families. J. Comb. Theory Ser. A 115, 105–120 (2008)
Stinson D.R., Zaverucha G.M.: Some improved bounds for secure frameproof codes and related separating hash families. IEEE Trans. Inf. Theory 54, 2508–2514 (2008)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by T. Etzion.
Rights and permissions
About this article
Cite this article
Trung, T.v. A tight bound for frameproof codes viewed in terms of separating hash families. Des. Codes Cryptogr. 72, 713–718 (2014). https://doi.org/10.1007/s10623-013-9800-0
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10623-013-9800-0