ПРОБЛЕМЫ ПЕРЕДАЧИ ИНФОРМАЦИИ

Том 56

2020

Вып. 4

УДК 621.391 : 519.72

Е.Е. Егорова¹, М. Фернандес², Г.А. Кабатянский¹, И. Мяо³

СУЩЕСТВОВАНИЕ И КОНСТРУКЦИИ МУЛЬТИМЕДИЙНЫХ КОДОВ,

СПОСОБНЫХ НАХОДИТЬ ПОЛНУЮ КОАЛИЦИЮ ПРИ АТАКЕ

УСРЕДНЕНИЯ И ШУМЕ

Как было недавно показано в [1], не существует мультимедийных кодов циф-

ровых водяных знаков, способных полностью восстановить коалицию недобро-

совестных пользователей в условиях общей линейной атаки и целенаправлен-

ного шума. Мы покажем, что такие коды существуют, если сузить класс атак

до атаки усреднения. Возникающая математическая задача близка к задаче

построения сигнатурных кодов для двоичного суммирующего канала с шумом.

Ключевые слова: мультимедийный код цифровых отпечатков пальцев, канал

множественного доступа, целенаправленный шум, сигнатурный код, атака на

основе сговора, коды без перекрытия, дизъюнктивные коды.

DOI: 10.31857/S0555292320040087

§ 1. Введение

Математическая постановка задачи защиты цифрового контента от нелегально-

го копирования и перераспределения возникла в конце прошлого века, см. [2-4].

Наибольшее внимание привлекла постановка задачи, известная как коды цифровых

отпечатков пальцев и существующая в различных вариациях, см. [5-8]. Соответ-

ствующие модели являются дискретными, и первая непрерывная модель, мотивиро-

ванная приложениями к защите мультимедийного контента (изображения, музыка),

появилась в работах [9, 10] под названием мультимедийные коды отпечатков паль-

цев. То, что эти коды тесно связаны с сигнатурными кодами для соответствующих

каналов множественного доступа, в частности, для А-канала [11], неявно появилось

в работе [12], а позже - в явной форме в [13]. Затем эта связь была распростра-

нена на сигнатурные коды для взвешенного двоичного суммирующего канала [14].

Этот подход был дальше развит в [1], где было доказано, в частности, что мульти-

медийные коды отпечатков пальцев не способны полностью восстановить коалицию

недобросовестных пользователей в условиях общей линейной атаки и целенаправ-

ленного шума. В данной статье мы покажем, что ситуация более оптимистична, если

несколько ограничить атаки коалиций, а именно при атаке усреднения существуют

коды, которые находят всех членов коалиции даже в присутствии целенаправлен-

ного шума. Отметим, что далее мы будем употреблять термин “цифровые водяные

знаки” вместо “отпечатки пальцев”.

¹ Работа выполнена при частичной финансовой поддержке Российского фонда фундаментальных

исследований (номера проектов 20-51-50007 и 20-07-00652).

² Работа выполнена при частичной финансовой поддержке гранта правительства Испании TCO-

RISEBLOCK (номер гранта PID2019-110224RB-I00, проект MINECO/FEDER) и гранта правитель-

ства Каталонии 2017-SGR-782.

³ Работа выполнена при частичной финансовой поддержке Японского общества содействия раз-

витию науки (JSPS) в рамках научного проекта JPJSBP120204802.

§2. Мультимедийные коды цифровых водяных знаков

Рассмотрим математическую модель защиты мультимедийного контента от неле-

гального перераспределения. Мультимедийный контент представляется как N-мер-

ный вектор x над полем R вещественных чисел. Имеется дистрибьютор, который

видоизменяет x специальным образом для каждого пользователя так, чтобы если

коалиция недобросовестных пользователей подделает x, то он может найти всех

членов коалиции (complete traceability; см. [1]). Для этого дистрибьютор выбира-

ет m попарно ортогональных векторов f₁, . . . , f_m в R^N одинаковой длины (для

простоты - длины 1), которые известны только ему - это важное предположение,

которое будет использоваться в дальнейшем. Затем дистрибьютор формирует так

называемые цифровые водяные знаки (ЦВЗ) как линейные комбинации этих векто-

ров с двоичными коэффициентами (известен и другой вариант “модуляции” ЦВЗ,

когда используются коэффициенты из {-1, +1}).

ЦВЗ w_j, предназначенный j-му пользователю, имеет вид

∑

w_j = h_ijf_i,

(1)

i=1

где h_ij ∈ {0, 1}. Вложение ЦВЗ осуществляется аддитивно, т.е. дистрибьютор выдает

j-му пользователю вектор

y_j = x + w_j

(2)

как копию x, где предполагается, что длина вектора x много больше длины ЦВЗ w_j

(т.е. ∥x∥ ≫ ∥w_j ∥, где ∥·∥ здесь и далее обозначает евклидову норму вектора), чтобы

копия y_j мало отличалась от оригинала x.

Пусть имеется M пользователей и среди них коалиция A ⊂ [M] недобросовест-

ных пользователей. Линейная атака состоит в том, что коалиция A генерирует

поддельную копию y как линейную комбинацию имеющихся у нее копий y_j с ве-

∑

щественными коэффициентами λ₁, . . . , λ_M , такими что

λ_j = 1, λ_j > 0 для всех

j=1

j ∈ A и λ_j = 0 для j ∈ A, т.е.

∑

y= λ_jy_j = λ_ay_a,

(3)

j=1

a∈A

∑

Так как λ_j = 1, то y = x+ λ_j w_j , а так как все λ_j ≥ 0, то в силу неравенства

j=1

треугольника (для нормы) имеем



∑

∑



∥y - x∥ =



λ_jw_j



≤ λ_j∥w_j∥ ≤ max∥wj∥ ≪ ∥x∥,

(4)



j=1

и следовательно, y является достаточно хорошей копией оригинала x.

Так как дистрибьютор знает значение x, то чтобы определить, что y - это неле-

гальная копия x, и найти всех участников коалиции, создавших y, он вычисляет

скалярные произведения

(

)

∑

s_k = (y - x, f_k) =

λ_j

h_ijf_i, f_k

= λ_jh_kj

(5)

j=1

i=1

j=1

и формирует вектор-синдром S = S(Λ) = (s₁, . . ., s_m), где Λ := (λ₁, . . . , λ_M ). Отме-

тим, что для вектора Λ его носителем supp(Λ) := {j : λ_j = 0} является коалиция A.

Введем векторы h₁, . . ., h_M, где h_j = (h1j, . . ., h_mj). Тогда (5) можно переписать

в виде

∑

S= λ_jh_j = λ_ah_a.

(6)

j=1

a∈A

Это уравнение, в свою очередь, можно записать как матричное уравнение

S=HΛ^T,

(7)

где H - матрица размера m × M, составленная из векторов-столбцов h₁, . . . , h_M .

Так как векторы f₁, . . . , f_m ортонормированные, а векторы ЦВЗ w₁, . . . , w_M

выражаются в базисе f₁, . . . , f_m с двоичными коэффициентами, а именно

∑

w_j = h_ijf_i, где h_ij ∈ {0, 1},

i=1

то множества W = {w₁, . . . , w_M } и H = {h₁, . . . , h_M } изометричны. При этом век-

торы f₁, . . ., f_m известны дистрибьютору (и только ему), поэтому для него равно-

сильно, работать ли с множеством ЦВЗ W или с множеством H соответствующих

двоичных векторов. Поэтому далее мы будем оба множества называть мультиме-

дийным кодом, а если по синдрому S можно однозначно найти носитель supp(Λ),

т.е. коалицию A, то будем называть их t-мультимедийным кодом со свойством

полного поиска коалиций (t-МППК-кодом).

Определение 1. Двоичный код H

= {h₁, . . . , h_M } ⊂ {0, 1}m называется

t-МППК-кодом, если для любых двух вещественных векторов Λ и Λ^′, таких что

∑

λ_j =

λ^′j = 1

| supp(Λ)|, | supp(Λ^′)| ≤ t,

j=1

из HΛ^T = HΛ^′T следует, что supp(Λ) = supp(Λ^′).

Замечание 1. Заметим, что в данном определении мы не воспользовались огра-

ничением, что все λ_j неотрицательны.

Замечание 2. Всюду далее мы предполагаем, что значение t фиксировано.

Среди всех линейных атак особо выделяется атака усреднения, для которой

λ_j = |A|-1 при j ∈ A и λ_j = 0 в противном случае. Ранее, начиная с первых работ

по этой тематике (см. [9, 10]), считалось, что “атака усреднения является наиболее

справедливой для участников коалиции, чтобы избежать обнаружения” [12]. По-

этому все работы до [13] ограничивались рассмотрением только атаки усреднения.

В этой статье мы покажем, что атака усреднения намного слабее общей линейной

атаки, по крайней мере, в случае целенаправленного шума.

Напомним, что двоичный код H = {h₁, . . ., h_M} ⊂ {0, 1}^m называется t-сигна-

турным кодом для двоичного суммирующего канала (см. [15]), если для любых двух

различных кодовых подмножеств A и B, где оба подмножества мощности не более t,

справедливо неравенство

∑

h_j =

h_j.

(8)

j∈A

j∈B

Код, для которого неравенство (8) выполнено для любых двух различных кодовых

подмножеств A и B одинаковой мощности не более t, будем называть (=, t)-сигна-

турным кодом для суммирующего канала. Двоичный код, обладающий свойством

нахождения полной коалиции при атаке усреднения, является (=, t)-сигнатурным

кодом для суммирующего канала. Обратное неверно ни для (=, t)-, ни для t-сигна-

турного кода для двоичного суммирующего канала.

Обозначим через M(m, t) максимально возможную мощность t-МППК-кода дли-

ны m, а через R(m, t) := m-1 log₂ M(m, t) - соответствующую кодовую скорость.

Тогда из сделанного выше замечания об атаке усреднения и обычных соображений

мощности вытекает следующий аналог границы Хэмминга:

CtM(m,t) ≤ (t + 1)^m.

(9)

Отметим, что из известной верхней границы для скорости сигнатурных кодов

для суммирующего канала [16] следует асимптотически в два раза лучшая, чем (9),

граница на скорость кода

log₂ t

lim supR(m, t) ≤

(1 + o(1)).

(10)

С другой стороны, в [14] была доказана следующая нижняя граница:

M (m, t) ≥ 2^⌊m/t⌋,

(11)

из которой следует, что R(m, t) ≥ t-1(1 + o(1)).

Повторим кратко основные аргументы из [14]. Прежде всего отметим, что если

среди векторов h₁, . . ., h_M любые 2t линейно независимы над R, то определение 1

выполнено, и более того, дистрибьютор может найти не только те j, которым соот-

ветствуют λ_j = 0, но и соответствующие значения λ_j (и кроме того, ограничение

∑ λ_j = 1 не требуется). Примером такого множества двоичных векторов являются

j=1

столбцы проверочной матрицы двоичного кода, исправляющего t ошибок, так как

любые 2t ее столбцов линейно независимы над полем из двух элементов, а следова-

тельно, и над R. Теперь, чтобы получить (11), остается взять в качестве h₁, . . ., h_M

столбцы проверочной (m × M)-матрицы неприводимого кода Гоппы (см. [17]) длины

M = 2^ℓ и избыточности m = ℓt, исправляющего t ошибок.

§3. Мультимедийные коды цифровых водяных знаков в присутствии шума

Отметим, что ранее в литературе уже рассматривались модели мультимедийных

кодов цифровых водяных знаков в присутствии шума: вероятностная модель шума

(см. [18]) и модель целенаправленного шума, где нет ограничения на норму (длину)

вектора ошибки, а есть только ограничение на вес Хэмминга ошибки [14].

В этой статье, следуя [1], мы рассматриваем модель, когда коалиция A не только

создает ложную копию

∑

y=x+ λ_jw_j ∈R^N

j∈A

в соответствии с моделью линейной атаки, но еще и целенаправленно добавляет век-

тор шума e ∈ R^N , такой что ∥e∥ ≤ δ, где ∥·∥ - евклидова норма на R^N . В результате

коалиция A формирует и перераспределяет копию

∑

y = x + λ_jw_j + e.

(12)

j∈A

100

Множество ЦВЗ W = {w₁, . . . , w_M } ⊂ R^N будем называть (t, δ)-мультимедий-

ным кодом ЦВЗ со свойством п

∑

если по любой ложной копии y =

λ_jy_j +e можно однозначно найти коалицию A.

j∈A

Это условие равносильно тому, что для любых двух различных коалиций A и B,

|A|, |B| ≤ t, и любых двух вещественных векторов Λ и Λ^′, таких что

∑

λ_j =

λ^′j = 1,

j∈A

j∈B

справедливо неравенство



∑



∑



λ_jw_j - λ^′jw_j

> 2δ.

(13)



j∈A

j∈B

Довольно очевидно, что условие (13) слишком сильное, и таких кодов не суще-

ствует, что и было показано в [1]. Приведем дополнительные к [1] аргументы, почему

таких кодов нет. Положим A = {1, 2, . . . , t} и B = {1, 2, . . . , t - 1, t + 1}. Обозначим

w = max

∥w_j∥ и выберем λ_t = λ′t+1 = λ так, чтобы 0 < λ < min{δw-1, 1}. Выберем

j∈[t+1]

∑

положительные λ_j = λ^′j для j = 1, . . . , t - 1 такими, что λ + λ_j = 1. Тогда

j=1

∑

λ_jw_j + e = λ_jw_j = λ_jw_j + e^′,

j∈A

j=1

j∈B

где e = -λw_t, e^′ = -λwt+1 и ∥e∥, ∥e^′∥ ≤ δ, и неравенство (13) не выполнено.

Этот анализ условия (13) показывает, что если какое-то λ_j отлично от нуля, но

достаточно мало, то от него можно “избавиться”, введя взамен другое ненулевое λ_i,

что и не позволяет найти коалицию целиком. Однако у атаки усреднения все λ_j

равны и достаточно отделены от нуля, что позволяет надеяться, что если ограничить

класс линейных атак только атакой усреднения, то существуют коды, находящие

коалицию целиком; см. следующее

Определение 2. Множество W = {w₁,...,w_M} будем называть (t,δ)-муль-

тимедийным кодом со свойством полного поиска коалиций, устойчивым к атаке

усреднения и δ-шуму, если для любых двух различных подмножеств кода A, B ⊂ W,

таких что |A|, |B| ≤ t, справедливо неравенство



∑



 1



w_j -

w_j

> 2δ.

(14)

 |A|

|B|



j∈A

j∈B

Ниже нам будет удобнее рассматривать не код W, а изометричный ему двоичный

код H длины m, для которого условие (14) перепишется в виде



∑



 1



h_j -

h_j

> 2δ.

(15)

 |A|

|B|



j∈A

j∈B

Обозначим через M(m, t, δ) максимальную мощность (t, δ)-мультимедийного ко-

да со свойством полного поиска коалиций, устойчивого к атаке усреднения и δ-шуму.

Определим, как обычно, соответствующую максимальную скорость

R(m, t, δ) := m-1 log₂ M(m, t, δ).

101

Основным результатом статьи является доказательство существования соответству-

ющих (t, δ)-мультимедийных кодов со скоростью, отделенной от нуля.

Теорема 1. Для любых фиксированных t и δ

γ_t log₂ e

0, 346

lim inf

R(m, t, δ) ≥

(16)

t(1 + γ_t log₂ e)

t(1 + e(log₂ e)-1)

где γ_t = (1 - t-1)t-1.

Разобьем построение таких кодов на две подзадачи: первая, когда мощность коа-

лиции заранее известна, вторая - построение кодов, которые позволяют найти мощ-

ность коалиции по любой ложной копии. Начнем с первой подзадачи.

Если мощность коалиции известна, то возникающая задача - это по существу

задача о сигнатурном коде для двоичного суммирующего канала с шумом (ДСКШ).

А именно, дадим

Определение 3. Двоичный код C = {c₁,...,c_M} называется (=,t,Δ)-сигна-

турным кодом для ДСКШ, если для любых двух различных подмножеств кода

A, B ⊂ C, таких что |A| = |B| ≤ t, справедливо неравенство

∑

∥

c - c^′∥ > 2Δ.

(17)

c∈A

c^′∈B

Очевидно, что (=, t, Δ)-сигнатурный код для ДСКШ позволяет однозначно найти

всю коалицию при атаке усреднения и δ-шуме, где δ = Δ/t, если мощность коалиции

заранее известна и не превышает t. Заметим также, что в определении 3 условие

|A| = |B| ≤ t можно без ограничения общности заменить на условие |A| = |B| = t.

Воспользуемся конструкцией, предложенной в [19] для построения сигнатурных

кодов для двоичного суммирующего по модулю 2 канала, и переоткрытой в [20] как

коды, исправляющие ошибки в канале и синдроме.

Начнем с кода

H₌ {h1, . . . ,hM } ⊂ {0, 1}^m длины m, слова которого - это столб-

цы проверочной (m × M)-матрицы линейного двоичного кода V , исправляющего t

ошибок. Закодируем слова

h₁, . . . ,hM двоичным кодом U длины n с m информаци-

онными символами и минимальным кодовым расстоянием d (в метрике Хэмминга).

Обозначим полученные векторы через h₁, . . . , h_M и зададим код H = {h₁, . . . , h_M }.

Лемма 1. Код H = {h₁,...,h_M} ⊂ {0,1}ⁿ является (=,t,Δ)-сигнатурным

√

кодом для ДСКШ с Δ =

d/2.

Доказательство. Рассмотрим два произвольных различных подмножества

A, B кода H одинаковой мощности не более t и соответствующие им векторы

∑

h(A) =

h и h(B) =

h∈A

h∈B

Будем обозначать через

a mod 2 = (a₁ mod 2, . . . , a_n mod 2) ∈ {0, 1}ⁿ

двоичную проекцию произвольного целочисленного вектора a = (a₁, . . . , a_n). Так

как различные суммы по модулю 2 из t и менее векторов

h_j различны (и отличны от

нуля), то это же справедливо и для сумм по модулю 2 векторов h_j . Следовательно,

h(A) mod 2 = h(B) mod 2. Так как векторы h(A) mod 2 и h(B) mod 2 принадлежат

коду U (в силу линейности кода), то

(

)

d_H

h(A) mod 2, h(B) mod 2

≥ d.

102

Теперь остается применить неравенство

√

d_E(a, b) ≥

d_H(a mod 2, b mod 2),

(18)

справедливое для любых двух целочисленных векторов a, b ∈ Rⁿ, где через d_E

обозначено евклидово расстояние, а через d_H - расстояние Хэмминга.

Таким образом, код H = {h₁, . . . , h_M } позволяет найти полностью коалицию

недобросовестных пользователей в условиях атаки усреднения и целенаправленно-

√

го шума длины не более δ = (2t)-1

d, если число таких пользователей заранее

известно и не превосходит t. ▴

§ 4. Коды, определяющие мощность коалиции

Определение 4. Будем называтьдвоичный код C кодом, определяющим мощ-

ность коалиции вплоть до t в условиях δ-шума, если для любых двух его подмно-

жеств A, B различной мощности не более t справедливо неравенство



∑



 1



c′



> 2δ.

(19)

 |A|

|B|



c∈A

c^′∈B

С помощью такого кода дистрибьютор сформирует итоговый код, приписывая

в качестве “хвостов” к словам кода H, построенного выше, слова кода, определяю-

щего мощность. По “хвостам” дистрибьютор найдет мощность коалиции, а затем по

коду H - и саму коалицию. Параметры получаемых кодов мы оценим в самом конце

статьи.

Введем, как нам представляется, новое понятие в комбинаторной теории коди-

рования.

Определение 5. Двоичный код называется слабым t-дизъюнктивным кодом,

если для любых t^′ различных кодовых слов, 1 ≤ t^′ ≤ t, существует координата,

в которой ровно одно слово равно 1.

Иначе говоря, для любого кодового подмножества A, такого что 1 ≤ |A| ≤ t,

существует координата i, такая что π_i(A) = 1, где π_i(A) := |{a ∈ A : a_i = 1}|.

Отметим очевидную связь с дизъюнктивными кодами (см. [21,22]). Напомним,

что код называется t-дизъюнктивным кодом, если для любого кодового подмноже-

ства A мощности не более t и любого кодового слова b ∈ A существует координата

i, такая что a_i = 0 для всех a ∈ A и b_i = 1. Очевидно, что (t - 1)-дизъюнктивный

код является слабым t-дизъюнктивным кодом, так как для любых t различных ко-

довых слов существует t соответствующих координат i, в проекциях на которые

встречаются все t слов веса Хэмминга 1, а для свойства слабой дизъюнктивности

достаточно всего одного такого слова и одной такой координаты, но для любых t^′

слов, 1 ≤ t^′ ≤ t.

Дизъюнктивные коды были переоткрыты в экстремальной комбинаторике под

названием семейства множеств без t-перекрытий [23,24]. Напомним, что семейство

множеств F = {F₁, . . . , F_M } называется семейством без t-перекрытий, если ни одно

множество семейства не покрывается объединением t других множеств этого семей-

ства.

Обобщим понятие слабого t-дизъюнктивного кода, введя, по существу, соответ-

ствующее расстояние.

Определение 6. Двоичный код называетсяслабым (t,T)-дизъюнктивным ко-

дом, если для любого кодового подмножества A, такого что 2 ≤ |A| ≤ t, существует

не менее T координат i, таких что π_i(A) = 1.

103

В качестве примера заметим, что слабый (2, 1)-дизъюнктивный код - это любой

двоичный код, состоящий из различных слов, а слабый (2, T )-дизъюнктивный код

- это двоичный код с минимальным кодовым расстоянием (в метрике Хэмминга) не

менее T .

Обозначим через F(t, T; L) максимальное число слов в слабом (t, T)-дизъюнктив-

ном коде длины L, а через R_F (t, T ; L) = L-1 log₂ F (t, T ; L) - соответствующую мак-

симальную скорость. Докажем следующий аналог границы Варшамова - Гилберта

для слабых (t, T )-дизъюнктивных кодов.

Теорема 2. Для фиксированных t и T

(

log₂ e

lim inf

R_F (t, T; L) ≥

)t-1 log₂ e >

(20)

Доказательство. Рассмотрим случайный двоичный код C мощности M и

длины L, в котором координаты кодовых слов выбираются независимо с вероят-

ностью p = t-1 того, что координата равна 1. Возьмем произвольное множество A

из t^′ слов кода C, 2 ≤ t^′ ≤ t, и посчитаем вероятность P того, что для i-й координаты

π_i(A) = 1. Очевидно, что

P = P(t^′) = t^′p(1 - p)t′-¹.

(21)

Тогда для вероятности p_bad того, что у A нет искомых T координат, справедливо

(

)_i

∑

p_bad = p_bad(t^′) =

C^iLPi(1 - P)L-i = (1 - P)L

Cⁱ

(22)

1-P

i=0

В силу того, что P ≤ 1/2 и

∑

C^iL < L^T

i=0

при L > 1, получаем, что p_bad = p_bad(t^′) ≤ (1 - P)^LL^T .

Так как имеется всего Ct′M < Mt′ различных t^′-подмножеств, то для вероятно-

сти P_bad того, что существует хотя бы одно “плохое” t^′-подмножество A, т.е. такое,

у которого нет T искомых координат, справедливо неравенство P_bad < Mt′p_bad. По-

требуем, чтобы

P_bad(t^′) < Mt′ p_bad(t^′) ≤ (2t)-1,

(23)

для чего достаточно, чтобы выполнялось неравенство

(

)-1/t′

M = M(t^′) ≤

2tL^T (1 - P(t^′))^L

(24)

Оценим теперь скорость кода R(t^′) :=¹

log₂ M(t^′):

R(t^′) ≥ -

(log₂(1 - P(t^′)) + o(1) ≥

P (t^′) log₂ e + o(1) =

t^′

= t-1(1 - t-1)t′-1 log2 e + o(1),

(25)

где второе неравенство следует из оценки ln(1 + x) ≤ x. Так как правая часть (25)

монотонно убывает по t^′, то выберем t^′ = t и итоговую скорость кода

(

)t-1

log₂ e

R :=

log₂ e + o(1) >

+ o(1).

104

Тогда для случайного кода с данной скоростью вероятность того, что при некото-

ром t^′ не выполнено требуемое условие - для любого t^′-подмножества кода суще-

ствует как минимум T искомых координат - не превосходит (2t)-1 (см. (23)). Так

как таких условий не более t, то следовательно, с вероятностью не меньше 1/2 слу-

чайный код является слабым (t, T )-дизъюнктивным кодом. ▴

Перейдем теперь к доказательству того, что слабый (t, T)-дизъюнктивный код

позволяет найти мощность коалиции в присутствии шума и, более того, приведем

алгоритм вычисления мощности коалиции.

Рассмотрим следующие непересекающиеся отрезки на числовой оси:

]

^[1

S_k :=

k = 1,2,...,t.

2t²

Пусть C - слабый (t, T )-дизъюнктивный код, A ⊂ C - некоторая коалиция мощности

не более t и y = x + |A|-1w(A) + e - ложная копия x, распространяемая этой∑

коалицией (напомним, что w(A) :=

w). Так как дистрибьютор знает x, то он

может вычислить z := y - x.

w∈A

Алгоритм нахождения мощности коалиции

1. Вычислить q_k := |{i : z_i ∈ S_k}|.

2. Положить мощность коалиции равной максимальному k, такому что q_k ≥ T/2,

k ≤ t.

Лемма 2. Для любого слабого (t,T)-дизъюнктивного кода алгоритм правильно

находит мощность коалиции, если длина шума

√

∥e∥ ≤ δ =

√ t-2.

Доказательство. Из определения кода и того, что z := y-x = |A|-1w(A)+e,

следует, что как минимум T/2 координат z_i попадут в отрезок S_|A|. Действительно,

из определения слабого (t, T )-дизъюнктивного кода следует, что по меньшей мере T

координат вектора |A|-1w(A) равны 1/|A|, и следовательно, если более T/2 этих

координат вектора z не принадлежат отрезку S_|A|, то для квадрата длины вектора

шума справедливо неравенство

(

)₂

∥e∥² >

=δ²,

2t²

что противоречит предположению ∥e∥ ≤ δ.

Предположим, что есть такое k, что |A| < k ≤ t и q_k ≥ T/2. Пусть координата z_i

попала в отрезок S_k. Если w(A)i ≥ 1, то

(A)

)

w_i

⁽1

|e_i| ≥

≥

|A|

2t²

|A|

2t²

t(t - 1)

2t²

Если же w(A)i = 0, то

|e_i| ≥ t-1 - (2t²)-1 >

t²

2t²

Общее число таких координат, которые могли бы привести к неправильному опре-

делению |A|, равно q_k. Тогда ∥e∥² > q_k(2t²)-2, а так как по предположению леммы

105

∥e∥² ≤^T

(2t²)-2, то q_k < T/2, и следовательно, алгоритм не может выдать k как

свой выход, что и требовалось доказать. ▴

§5. Выбор кодов

Естественно выбрать параметры d и T таким образом, чтобы обеспечиваемый

леммами 1 и 2 уровень шума δ совпадал. Таким образом,

√

δ=

√

2t²

или, что то же самое, T = 2dt². Всюду далее и t, и δ - константы.

Напомним, что мы строим код следующим образом. Мы начинаем с t-МППК-кода

мощности M = 2^ℓ и длины m = ℓt. Затем мы удлиняем слова этого кода, рассмат-

ривая их как информационные последовательности для линейного (n, m)-кода V

с минимальным кодовым расстоянием d. Известная в этом случае избыточность

= n - m кода V имеет порядок

log₂ n и достигается, если взять соответству-

ющие двоичные коды БЧХ или Гоппы. Заметим, что это удлинение не влияет на

асимптотику итоговой длины кода. Следующее удлинение (конкатенация) происхо-

дит с помощью слабого (t, T )-дизъюнктивного кода длины L. Ясно, что дистрибью-

тору следует выбрать длины кодов так, чтобы мощности кодов были (примерно)

равными, т.е.

t-1n ≈ t-1Lγ_t log₂ e, где γ_t = (1 - t-1)t-1.

Итоговая длина кода m равна n + L, и следовательно, для скорости R(m, t, δ)

наилучшего (t, δ)-мультимедийного кода со свойством полного поиска коалиций,

устойчивого к атаке усреднения и δ-шуму, справедлива следующая асимптотиче-

ская оценка:

γ_t log₂ e

0,346

R( m, t, δ) ≥

+ o(1) >

+ o(1),

t(1 + γ_t log₂ e)

t(1 + e(log₂ e)-1)

что и завершает доказательство теоремы 1. ▴

Таким образом, мы доказали существование мультимедийных кодов со скоростью

не меньше 0,346t-1, способных находить целиком коалицию из не более чем t недоб-

росовестных пользователей, которые применяют атаку усреднения и целенаправлен-

ный шум ограниченной евклидовой длины. Отметим, что главный член асимптотики

скорости кода (см. выше) зависит от t, но не зависит от длины шума δ.

§ 6. Заключение

В заключение следует отметить, что рассмотренные в этой статье задачи близки

к задаче о евклидовых “дизьюнктивных” кодах, см. [25,26], которую можно полу-

чить, если неравенство (14) в определении 2 заменить на



∑



∑



w_j - w_j

> 2δ.

(26)



j∈A

j∈B

Другое отличие состоит в том, что в задаче из [25, 26] в качестве w_j рассматри-

вались произвольные векторы евклидова пространства, а в данной статье - только

двоичные.

106

Авторы считают своим приятным долгом выразить благодарность И.В. Воробье-

ву за полезные обсуждения.

СПИСОК ЛИТЕРАТУРЫ

Fan J., Gu Y., Hachimori M., Miao Y. Signature Codes for Weighted Binary Adder Channel

and Multimedia Fingerprinting // IEEE Trans. Inform. Theory. 2020 (to appear).

Wagner N.R. Fingerprinting // Proc. 1983 IEEE Symp. on Security and Privacy. Oakland,

CA, USA. April 25-27, 1983. P. 18-22.

Blakley G.R., Meadows C., Purdy G.B. Fingerprinting Long Forgiving Messages // Advances

in Cryptology—CRYPTO’85 (Proc. Conf. on the Theory and Application of Cryptographic

Techniques. Santa Barbara, CA, USA. August 18-22, 1985). Lect. Notes Comp. Sci. V. 218.

Berlin: Springer, 1986. P. 180-189.

Chor B., Fiat A., Naor M. Tracing Traitors // Advances in Cryptology—CRYPTO’94 (Proc.

14th Annu. Int. Cryptology Conf. Santa Barbara, CA, USA. August 21-25, 1994). Lect.

Notes Comp. Sci. V. 839. Berlin: Springer, 1994. P. 257-270.

Hollmann H.D.L., van Lint J.H., Linnartz J.-P., Tolhuizen L.M.G.M. On Codes with the

Identifiable Parent Property // J. Combin. Theory Ser. A. 1998. V. 82. № 2. P. 121-133.

Boneh D., Shaw J. Collusion-Secure Fingerprinting for Digital Data // IEEE Trans. Inform.

Theory. 1998. V. 44. № 5. P. 1897-1905.

Barg A., Blakley G.R., Kabatiansky G.A. Digital Fingerprinting Codes: Problem State-

ments, Constructions, Identification of Traitors // IEEE Trans. Inform. Theory. 2003. V. 49.

№ 4. P. 852-865.

Tardos G. Optimal Probabilistic Fingerprint Codes // Proc. 35th Annu. ACM Symp. on

Theory of Computing (STOC’03). San Diego, CA, USA. June 9-11, 2003. P. 116-125.

Trappe W., Wu M., Wang Z.J., Liu K.J.R. Anti-Collusion Fingerprinting for Multimedia //

IEEE Trans. Signal Process. 2003. V. 51. № 4. P. 1069-1087.

10.

Liu K.J.R., Trappe W., Wang Z.J., Wu M., Zhao H. Multimedia Fingerprinting Forensics

for Traitor Tracing. Cairo, Egypt: Hindawi, 2005.

11.

Chang S.C., Wolf J.K. On the T -User M-Frequency Noiseless Multiple-Access Channel

with and without Intensity Information // IEEE Trans. Inform. Theory. 1981. V. 27. № 1.

P. 41-48.

12.

Cheng M., Miao Y. On Anti-Collusion Codes and Detection Algorithms for Multimedia

Fingerprinting // IEEE Trans. Inform. Theory. 2011. V. 57. № 7. P. 4843-4851.

13.

Egorova E., Fernandez M., Kabatiansky G., Lee M.H. Signature Codes for the A-Channel

and Collusion-Secure Multimedia Fingerprinting Codes // Proc. 2016 IEEE Int. Symp. on

Information Theory (ISIT’2016). Barcelona, Spain. July 10-15, 2016. P. 3043-3047.

14.

Egorova E., Fernandez M., Kabatiansky G., Lee M.H. Signature Codes for Weighted Noisy

Adder Channel, Multimedia Fingerprinting and Compressed Sensing // Des. Codes Cryp-

togr. 2019. V. 87. № 2-3. P. 455-462.

15.

Györfi L., Győri S., Laczay B., Ruszinkó M. Lectures on Multiple Access Channels. Book

draft, 2005. Available at http://www.szit.bme.hu/~gyori/AFOSR_05/book.pdf.

16.

D’yackov A.G. On a Search Model of False Coins // Topics in Information Theory (Proc.

2nd Colloq. on Information Theory. Keszthely, Hungary. August 25-30, 1975). Colloq. Math.

Soc. János Bolyai. V. 16. Amsterdam: Horth Holland, 1977. P. 163-170.

17.

Мак-Вильямс Ф.Дж., Слоэн Н.Дж.А. Теория кодов, исправляющих ошибки. М.:

Связь, 1979.

18.

Kabatiansky G., Fernandez M., Egorova E. Multimedia Fingerprinting Codes Resistant

against Colluders and Noise // Proc. 8th IEEE Int. Workshop on Information Forensics

and Security (WIFS’2016). Abu Dhabi, UAE. December 4-7, 2016. P. 1-5.

19.

Ericson T., Levenshtein V.I. Superimposed Codes in the Hamming Space // IEEE Trans.

Inform. Theory. 1994. V. 40. № 6. P. 1882-1893.

20.

Влэдуц С.Г., Кабатянский Г.А., Ломаков В.В. Об исправлении ошибок при искажени-

ях в канале и синдроме // Пробл. передачи информ. 2015. Т. 51. № 2. С. 50-56.

107

21. Kautz W.H., Singleton R.C. Nonrandom Binary Superimposed Codes // IEEE Trans. In-

form. Theory. 1964. V. 10. № 4. P. 363-377.

22. Дьячков А.Г., Рыков В.В. Границы длины дизъюнктивных кодов // Пробл. передачи

информ. 1982. Т. 18. № 3. С. 7-13.

23. Erdős P., Frankl P., Füredi Z. Families of Finite Sets in Which No Set Is Covered by the

Union of Two Others // J. Combin. Theory Ser. A. 1982. V. 33. № 2. P. 158-166.

24. Erdős P., Frankl P., Füredi Z. Families of Finite Sets in Which No Set Is Covered by the

Union of r Others // Israel J. Math. 1985. V. 51. № 1-2. P. 79-89.

25. Ericson T., Györfi L. Superimposed Codes in Rⁿ // IEEE Trans. Inform. Theory. 1988.

V. 34. № 4. P. 877-880.

26. Füredi Z., Ruszinkó M. An Improved Upper Bound of the Rate of Euclidean Superimposed

Codes // IEEE Trans. Inform. Theory. 1999. V. 45. № 2. P. 799-802.

Егорова Елена Евгеньевна

Поступила в редакцию

Сколковский институт науки и технологий (Сколтех)

23.10.2020

egorovahelene@gmail.com

После доработки

Фернандес Марсель

24.11.2020

Политехнический университет Каталонии,

Принята к публикации

Барселона, Испания

24.11.2020

marcelf@entel.upc.edu

Кабатянский Григорий Анатольевич

Сколковский институт науки и технологий (Сколтех)

g.kabatyansky@skoltech.ru

Мяо Ин

Университет Цукубы, Цукуба, префектура Ибараки, Япония

miao@sk.tsukuba.ac.jp

108