Probabilistic Existence Results for Parent-Identifying Schemes
| Autor: | Minquan Cheng, Yujie Gu, Grigory Kabatiansky, Ying Miao |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
FOS: Computer and information sciences
Discrete Mathematics (cs.DM) Computer Science - Information Theory Structure (category theory) 02 engineering and technology Library and Information Sciences Encryption Upper and lower bounds Set (abstract data type) 0202 electrical engineering electronic engineering information engineering FOS: Mathematics Mathematics - Combinatorics Mathematics Discrete mathematics business.industry Information Theory (cs.IT) Probabilistic logic 020206 networking & telecommunications Code rate Computer Science Applications Asymptotically optimal algorithm Combinatorics (math.CO) business Broadcast encryption Computer Science - Discrete Mathematics Information Systems |
| DOI: | 10.48550/arxiv.1906.01031 |
| Popis: | 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 combinatorial structures for parent-identifying schemes. First, we establish an equivalent relationship between parent-identifying schemes and forbidden configurations. Based on this relationship, we derive probabilistic existence lower bounds for two related combinatorial structures, that is, $t$-parent-identifying set systems ($t$-IPPS) and $t$-multimedia parent-identifying codes ($t$-MIPPC), which are used in broadcast encryption and multimedia fingerprinting respectively. The probabilistic lower bound for the maximum size of a $t$-IPPS has the asymptotically optimal order of magnitude in many cases, and that for $t$-MIPPC provides the asymptotically optimal code rate when $t=2$ and the best known asymptotic code rate when $t\geq 3$. Furthermore, we analyze the structure of $2$-IPPS and prove some bounds for certain cases. Comment: 14 pages |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|