{"corpus_id":9950264,"paper_sha":"048e6fd2ed98aec0be5a6a382aa8e6db3b5cf7e1","doi":"10.1109/TIFS.2008.2012201","arxiv_id":"0710.2705","pmid":null,"pmcid":null,"mag_id":2115669982,"dblp_id":"journals/tifs/LinSG09","acl_id":null,"title":"Fingerprinting With Minimum Distance Decoding","year":2007,"publication_date":"2007-10-14","venue":"IEEE Transactions on Information Forensics and Security","journal":{"name":"IEEE Transactions on Information Forensics and Security","pages":"59-69","volume":"4"},"journal_issn":null,"journal_title":null,"publication_types":["JournalArticle"],"pubmed_pub_types":null,"s2_fields_of_study":["Mathematics","Computer Science"],"reference_count":23,"citation_count":7,"influential_citation_count":0,"is_open_access":true,"arxiv_categories":["cs.IT","cs.CR","math.IT"],"arxiv_license":null,"arxiv_journal_ref":"IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY, VOL. 4,\n  NO. 1, MARCH 2009 pp.59-69","mesh_headings":null,"chemicals":null,"comments_corrections":null,"source_flags":1,"s2_open_access_pdf_url":"http://arxiv.org/pdf/0710.2705","s2_open_access_landing_url":"https://www.semanticscholar.org/paper/048e6fd2ed98aec0be5a6a382aa8e6db3b5cf7e1","s2_open_access_license":null,"s2_open_access_status":"GREEN","pmc_open_access_pdf_url":null,"pmc_open_access_landing_url":null,"pmc_open_access_license":null,"pmc_open_access_status":null,"unpaywall_open_access_pdf_url":null,"unpaywall_open_access_landing_url":null,"unpaywall_open_access_license":null,"unpaywall_open_access_status":null,"abstract":"This paper adopts an information-theoretic framework for the design of collusion-resistant coding/decoding schemes for digital fingerprinting. More specifically, the minimum distance decision rule is used to identify 1 out of t pirates. Achievable rates, under this detection rule, are characterized in two scenarios. First, we consider the averaging attack where a random coding argument is used to show that the rate 1/2 is achievable with t=2 pirates. Our study is then extended to the general case of arbitrary t highlighting the underlying complexity-performance tradeoff. Overall, these results establish the significant performance gains offered by minimum distance decoding compared to other approaches based on orthogonal codes and correlation detectors which can support only a subexponential number of users (i.e., a zero rate). In the second scenario, we characterize the achievable rates, with minimum distance decoding, under any collusion attack that satisfies the marking assumption. For t=2 pirates, we show that the rate 1-H(0.25) ap 0.188 is achievable using an ensemble of random linear codes. For t ges 3, the existence of a nonresolvable collusion attack, with minimum distance decoding, for any nonzero rate is established. Inspired by our theoretical analysis, we then construct coding/decoding schemes for fingerprinting based on the celebrated belief-propagation framework. Using an explicit repeat-accumulate code, we obtain a vanishingly small probability of misidentification at rate 1/3 under averaging attack with t=2. For collusion attacks, which satisfy the marking assumption, we use a more sophisticated accumulate repeat accumulate code to obtain a vanishingly small misidentification probability at rate 1/9 with t=2. These results represent a marked improvement over the best available designs in the literature.","claims":[{"public_id":"cl_e4f727f50a07b6df807f624669912beb","status":"active","text":"An accumulate repeat accumulate code achieves vanishingly small misidentification probability at rate 1/9 under collusion attacks satisfying the marking assumption with t=2 pirates.","confidence":0.9,"contributors":[{"id":32,"public_id":"7c402c1b98","public_label":"뀨 (7c402c1b98)","roles":["extraction"],"url":"https://sah.borca.ai/u/7c402c1b98"},{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["review"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_e4f727f50a07b6df807f624669912beb"},{"public_id":"cl_37b0a110014a4c245f101e868a234c7d","status":"active","text":"An explicit repeat-accumulate code achieves vanishingly small misidentification probability at rate 1/3 under averaging attack with t=2 pirates.","confidence":0.9,"contributors":[{"id":32,"public_id":"7c402c1b98","public_label":"뀨 (7c402c1b98)","roles":["extraction"],"url":"https://sah.borca.ai/u/7c402c1b98"},{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["review"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_37b0a110014a4c245f101e868a234c7d"},{"public_id":"cl_1f11353c6a6affee532cd7ef552a5cbc","status":"active","text":"For t ≥ 3 pirates, no nonzero rate is achievable with minimum distance decoding under a nonresolvable collusion attack satisfying the marking assumption.","confidence":0.85,"contributors":[{"id":32,"public_id":"7c402c1b98","public_label":"뀨 (7c402c1b98)","roles":["extraction"],"url":"https://sah.borca.ai/u/7c402c1b98"},{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["review"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_1f11353c6a6affee532cd7ef552a5cbc"},{"public_id":"cl_7ba2dcc02d5e8c63ed21d52c5c953e0a","status":"active","text":"Minimum distance decoding achieves rate 1-H(0.25) ≈ 0.188 for t=2 pirates under any collusion attack satisfying the marking assumption, using an ensemble of random linear codes.","confidence":0.9,"contributors":[{"id":32,"public_id":"7c402c1b98","public_label":"뀨 (7c402c1b98)","roles":["extraction"],"url":"https://sah.borca.ai/u/7c402c1b98"},{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["review"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_7ba2dcc02d5e8c63ed21d52c5c953e0a"},{"public_id":"cl_59cb98e6211f74bf90179ee967545dbd","status":"active","text":"Minimum distance decoding achieves rate 1/2 for t=2 pirates under averaging attack.","confidence":0.9,"contributors":[{"id":32,"public_id":"7c402c1b98","public_label":"뀨 (7c402c1b98)","roles":["extraction"],"url":"https://sah.borca.ai/u/7c402c1b98"},{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["review"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_59cb98e6211f74bf90179ee967545dbd"}],"concepts":[{"public_id":"co_4b971ae22ce59e7f47f088d387b1195e","status":"active","name":"rate 1-H(0.25)","description":"An achievable rate approximately 0.188 for t=2 pirates under any collusion attack satisfying the marking assumption.","types":["performance metric"],"aliases":[],"contributors":[{"id":32,"public_id":"7c402c1b98","public_label":"뀨 (7c402c1b98)","roles":["extraction"],"url":"https://sah.borca.ai/u/7c402c1b98"},{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["review"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_4b971ae22ce59e7f47f088d387b1195e"},{"public_id":"co_7c5709306015d879575ccbef9a6c5433","status":"active","name":"accumulate repeat accumulate code","description":"A more sophisticated code construction used to obtain vanishingly small misidentification probability at rate 1/9 under collusion attacks satisfying the marking assumption with t=2.","types":["method"],"aliases":[],"contributors":[{"id":32,"public_id":"7c402c1b98","public_label":"뀨 (7c402c1b98)","roles":["extraction"],"url":"https://sah.borca.ai/u/7c402c1b98"},{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["review"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_7c5709306015d879575ccbef9a6c5433"},{"public_id":"co_971bb98b1d1b77d3ee3d1a7523c58cd7","status":"active","name":"minimum distance decoding","description":"A decision rule used to identify one out of t pirates by selecting the codeword closest to the received sequence.","types":["method"],"aliases":[],"contributors":[{"id":32,"public_id":"7c402c1b98","public_label":"뀨 (7c402c1b98)","roles":["extraction"],"url":"https://sah.borca.ai/u/7c402c1b98"},{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["review"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_971bb98b1d1b77d3ee3d1a7523c58cd7"},{"public_id":"co_a5c10986c96410b8e15543d0eb09886b","status":"active","name":"averaging attack","description":"A collusion attack where pirates average their fingerprints to produce a forgery.","types":["attack model"],"aliases":[],"contributors":[{"id":32,"public_id":"7c402c1b98","public_label":"뀨 (7c402c1b98)","roles":["extraction"],"url":"https://sah.borca.ai/u/7c402c1b98"},{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["review"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_a5c10986c96410b8e15543d0eb09886b"},{"public_id":"co_ade7093a5cd26470ca90b1794c77d5cb","status":"active","name":"nonresolvable collusion attack","description":"A collusion attack that prevents minimum distance decoding from achieving any nonzero rate for t ≥ 3 pirates under the marking assumption.","types":["attack model"],"aliases":[],"contributors":[{"id":32,"public_id":"7c402c1b98","public_label":"뀨 (7c402c1b98)","roles":["extraction"],"url":"https://sah.borca.ai/u/7c402c1b98"},{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["review"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_ade7093a5cd26470ca90b1794c77d5cb"},{"public_id":"co_be97331e12c0f05d66d5376dac9457a3","status":"active","name":"marking assumption","description":"A constraint on collusion attacks that forbids pirates from producing a symbol not present in any of their fingerprints at a given position.","types":["assumption"],"aliases":[],"contributors":[{"id":32,"public_id":"7c402c1b98","public_label":"뀨 (7c402c1b98)","roles":["extraction"],"url":"https://sah.borca.ai/u/7c402c1b98"},{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["review"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_be97331e12c0f05d66d5376dac9457a3"},{"public_id":"co_c92c612ca97eeaba72b58886bb8ed64e","status":"active","name":"misidentification probability","description":"The probability that the decoder incorrectly identifies the pirate, shown to be vanishingly small for the proposed schemes.","types":["performance metric"],"aliases":[],"contributors":[{"id":32,"public_id":"7c402c1b98","public_label":"뀨 (7c402c1b98)","roles":["extraction"],"url":"https://sah.borca.ai/u/7c402c1b98"},{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["review"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_c92c612ca97eeaba72b58886bb8ed64e"},{"public_id":"co_cfd4891bb6366b5054cb2d5235c94939","status":"active","name":"repeat-accumulate code","description":"An explicit code construction used to obtain vanishingly small misidentification probability at rate 1/3 under averaging attack with t=2.","types":["method"],"aliases":[],"contributors":[{"id":32,"public_id":"7c402c1b98","public_label":"뀨 (7c402c1b98)","roles":["extraction"],"url":"https://sah.borca.ai/u/7c402c1b98"},{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["review"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_cfd4891bb6366b5054cb2d5235c94939"},{"public_id":"co_d3c0436952a4420b4021416f1fb8592e","status":"active","name":"rate 1/2","description":"An achievable rate of 0.5 for fingerprinting with t=2 pirates under averaging attack using minimum distance decoding.","types":["performance metric"],"aliases":[],"contributors":[{"id":32,"public_id":"7c402c1b98","public_label":"뀨 (7c402c1b98)","roles":["extraction"],"url":"https://sah.borca.ai/u/7c402c1b98"},{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["review"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_d3c0436952a4420b4021416f1fb8592e"},{"public_id":"co_ffc25825fe91f3bd19fdbcc2ab0b1fe3","status":"active","name":"random linear codes","description":"An ensemble of codes used to achieve rate 1-H(0.25) for t=2 pirates under any collusion attack satisfying the marking assumption.","types":["method"],"aliases":[],"contributors":[{"id":32,"public_id":"7c402c1b98","public_label":"뀨 (7c402c1b98)","roles":["extraction"],"url":"https://sah.borca.ai/u/7c402c1b98"},{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["review"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_ffc25825fe91f3bd19fdbcc2ab0b1fe3"}],"external_ids":{"DOI":"10.1109/TIFS.2008.2012201","ArXiv":"0710.2705","PubMed":null,"PubMedCentral":null,"MAG":2115669982,"DBLP":"journals/tifs/LinSG09","ACL":null},"open_access":{"is_open_access":true,"pdf_url":"http://arxiv.org/pdf/0710.2705","landing_url":"https://www.semanticscholar.org/paper/048e6fd2ed98aec0be5a6a382aa8e6db3b5cf7e1","source":"semantic_scholar","pdf_url_source":"semantic_scholar_open_access_pdf","license":null,"status":"GREEN","reason":null},"reference_availability":{"status":"available","references_indexed":true,"full_text_available":true,"full_text_source":"arxiv","count_basis":"semantic_scholar_metadata","extraction_status":"not_applicable","reason":null},"source":{"provider":"episteme2","base_corpus":"semantic_scholar_dump","freshness_mode":"unknown","basis":["semantic_scholar_metadata","postgres_metadata"],"limits":["paper metadata is based on indexed upstream scholarly datasets","claims and concepts are available only for extracted papers","absence of claims or concepts means no extracted graph data is available in this response"],"status":"available","degraded":false,"degraded_reasons":[],"diagnostics":{"status":"available","degraded":false,"degraded_reasons":[],"metadata_status":"available","graph_status":"available","abstract_status":"available"},"source_flags":1},"paper_id":635699,"paper_uid":"4d85ed52-3655-4296-b5c6-a76103bb54a8","canonical_identity":{"paper_id":635699,"paper_uid":"4d85ed52-3655-4296-b5c6-a76103bb54a8","identity_status":"available","lookup_basis":"semantic_scholar_external_id","compatibility_path":"corpus_id"},"url":"https://sah.borca.ai/papers/9950264"}