AND攻撃に対する耐性をもつ結託耐性符号の容量について

摘要

Embedding anti-collusion fingerprinting codes to digital contents enables us to protect the digital contents from piracy. Recently, Trappe et al. proposed an anti-collusion code (AND-ACC) such that illegal users are exactly detected from a binary sequence obtained from AND of all the codewords of the illegal users, where the number of the illegal users is assumed to be less than or equal to k. In this paper we focus on the AND-ACC and analyze the number of codewords M with increasing the codeword length n for an arbitrary fixed k. First, we define the zero-error capacity C_k* of the AND-ACC and give a lower and an upper bounds of C_k*. The lower bound of C_k* is obtained by using a lemma used in a coding theorem on the identification codes. In addition, we extend the AND-ACC to the case where negligible detection error is permitted. We define the capacity C_k and give a lower bound of C_k. We use a method similar to the random coding argument used in a coding theorem on the multiple-access channel.%ディジタルコンテンツに結託耐性符号を埋め込んでおくことは．特定多数のユーザにインターネット経由で有料のコンテンツを配信する場合に，不正コピーの流出防止策として有用である．近年，Trappeらは，た個以下の2値符号語のANDをとった系列から，もとのk個以下の符号語をすべて誤りなく復元できる結託耐性符号（AND-ACC）を提案した．本稿では，任意に固定したkに対し，AND-ACCの最大の符号語数Mを，符号語長nの関数として解析することを目的とする．本稿ではまず，た人以下の不正者を誤りなく特定できる条件のもとで，1log_2Mの上限をゼロエラー容量C_k*芸と定義し，ゼロエラー容量の上界と下界を与える．ゼロエラー容量の下界は同定符号の順定理の証明で用いられる手法を用いて導出され一般に正であることが示される．次に，た人以下の不正者の特定に対して微小な誤り確率を許容したときの1log_2Mの上限を容量C_kと定義し，容量の下界を与える．下界の導出では，多重アクセス通信路の符号化順定理で用いられる手法を用いる．