Paper Info
Title
Probabilistic Existence Results for Parent-Identifying Schemes.
Abstract
Parent-identifying schemes provide a way to identify causes from effects for some information systems, such as digital fingerprinting and group testing. In this paper, we consider the combinatorial structures for parent-identifying schemes. First, we establish an equivalent relationship between the parent-identifying schemes and forbidden configurations. Based on this relationship, we derive the probabilistic existence lower bounds for two related combinatorial structures, that is, <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$t$ </tex-math></inline-formula> -parent-identifying set systems ( <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$t$ </tex-math></inline-formula> -IPPS) and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$t$ </tex-math></inline-formula> -multimedia parent-identifying codes ( <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$t$ </tex-math></inline-formula> -MIPPC), which are used in broadcast encryption and multimedia fingerprinting, respectively. The probabilistic lower bound for the maximum size of a <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$t$ </tex-math></inline-formula> -IPPS has the asymptotically optimal order of magnitude in many cases, and that for <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$t$ </tex-math></inline-formula> -MIPPC provides the asymptotically optimal code rate when <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$t=2$ </tex-math></inline-formula> and the best known asymptotic code rate when <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$t\ge 3$ </tex-math></inline-formula> . Furthermore, we analyze the structure of 2-IPPS and prove some bounds for certain cases.
Year
DOI
Venue
2019
10.1109/TIT.2019.2927020
IEEE Transactions on Information Theory
Keywords
DocType
Volume
Probabilistic logic,Encryption,Testing,Technological innovation,Multimedia systems,Indexes
Journal
abs/1906.01031
Issue
ISSN
Citations 
10
0018-9448
0
PageRank 
References 
Authors
0.34
0
4
Name
Order
Citations
PageRank
Yujie Gu1969.79
M. Cheng215420.36
Grigory Kabatiansky3115.68
Ying Miao449143.85