{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:18:54Z","timestamp":1778807934846,"version":"3.51.4"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2008,5,1]],"date-time":"2008-05-01T00:00:00Z","timestamp":1209600000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["329527"],"award-info":[{"award-number":["329527"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003549","name":"Orsz\u00e1gos Tudom\u00e1nyos Kutat\u00e1si Alapprogramok","doi-asserted-by":"publisher","award":["T-046234AT-048826NK-62321T-029255T-030059"],"award-info":[{"award-number":["T-046234AT-048826NK-62321T-029255T-030059"]}],"id":[{"id":"10.13039\/501100003549","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2008,5]]},"abstract":"<jats:p>\n            We construct binary codes for fingerprinting digital documents. Our codes for\n            <jats:italic>n<\/jats:italic>\n            users that are \u03f5-secure against\n            <jats:italic>c<\/jats:italic>\n            pirates have length\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>c<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            log(\n            <jats:italic>n<\/jats:italic>\n            \/\u03f5)). This improves the codes proposed by Boneh and Shaw [1998] whose length is approximately the square of this length. The improvement carries over to works using the Boneh--Shaw code as a primitive, for example, to the dynamic traitor tracing scheme of Tassa [2005].\n          <\/jats:p>\n          <jats:p>By proving matching lower bounds we establish that the length of our codes is best within a constant factor for reasonable error probabilities. This lower bound generalizes the bound found independently by Peikert et al. [2003] that applies to a limited class of codes. Our results also imply that randomized fingerprint codes over a binary alphabet are as powerful as over an arbitrary alphabet and the equal strength of two distinct models for fingerprinting.<\/jats:p>","DOI":"10.1145\/1346330.1346335","type":"journal-article","created":{"date-parts":[[2008,5,15]],"date-time":"2008-05-15T18:28:05Z","timestamp":1210876085000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":140,"title":["Optimal probabilistic fingerprint codes"],"prefix":"10.1145","volume":"55","author":[{"given":"G\u00e1bor","family":"Tardos","sequence":"first","affiliation":[{"name":"Simon Fraser University, Burnaby, BC, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,5,15]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2008.921859"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of Crypto '85","author":"Blakley G. R."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of Crypto '99","author":"Boneh D."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.705568"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of Crypto '94","volume":"839","author":"Chor B."},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Chung F. Graham R. and Leighton T. 2001. Guessing secrets. Electron. J. Combinat. 8.  Chung F. Graham R. and Leighton T. 2001. Guessing secrets. Electron. J. Combinat. 8.","DOI":"10.37236\/1557"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-001-0006-7"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/647596.731691"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the IEEE International Symposium on Information Theory. IEEE Computer Society Press","author":"Kilian J."},{"key":"e_1_2_1_10_1","volume-title":"Lecture Notes in Computer Science","volume":"1403","author":"Kurosawa K."},{"key":"e_1_2_1_11_1","unstructured":"Lindkvist T. 1999. Fingerprinting digital documents. Ph.D. dissertation. Link\u00f6ping Studies in Science and Technology. Thesis No. 798.  Lindkvist T. 1999. Fingerprinting digital documents. Ph.D. dissertation. Link\u00f6ping Studies in Science and Technology. Thesis No. 798."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM","author":"Peikert C."},{"key":"e_1_2_1_13_1","volume-title":"North-Holland Series in Applied Mathematics and Mechanics","volume":"10","author":"R\u00e9nyi A.","year":"1970"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/646765.704115"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.915661"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780561"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-004-0214-z"},{"key":"e_1_2_1_18_1","volume-title":"Fingerprinting. In Proceedings of the 1983 IEEE Symposium on Security and Privacy. IEEE Computer Society Press","author":"Wagner N.","year":"1983"},{"key":"e_1_2_1_19_1","volume-title":"Topics in Cryptology\u2014CT-RSA","author":"Yacobi Y.","year":"2001"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1346330.1346335","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1346330.1346335","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:38:58Z","timestamp":1750253938000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1346330.1346335"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,5]]},"references-count":19,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,5]]}},"alternative-id":["10.1145\/1346330.1346335"],"URL":"https:\/\/doi.org\/10.1145\/1346330.1346335","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,5]]},"assertion":[{"value":"2003-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-05-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}