Digital watermarks resistant to collusion attacks.pdf В настоящее время основным способом борьбы с пиратством в сфере цифровых технологийявляется внедрение в медиа-данные цифровых водяных знаков. В большинствеслучаев водяной знак выбирается как произвольный идентификатор пользователяили логотип какой-либо организации, а его стойкость обеспечивается лишь алгоритмомвнедрения. Однако при таком выборе водяных знаков метод защиты оказываетсямалоэффективным против серьезных атак, направленных на полное или частичноеудаление или изменение водяного знака. В частности, он абсолютно неустойчив к атакесговором, а для систем с большим количеством пользователей, таких, как IPTV,это недопустимо.В данной работе вводятся допустимые множества водяных знаков, использованиекоторых позволяет противостоять атакам сговором, изучаются свойства и оцениваютсяколичественные характеристики таких множеств с целью их построения и обсуждаетсяпроблема идентификации участников сговора по созданному ими ложному водяномузнаку.Под атакой сговором понимается следующее. Злоумышленник побитно сравниваетимеющиеся у него копии некоторого медиа-данного с различными водяными знакамив них и заключает, что биты, в которых сравниваемые данные различаются, суть битыводяного знака. Затем он эти биты устанавливает в некоторые значения так, чтобыполученный водяной знак, называемый ложным, не совпадал ни с одним из использованныхпри сравнении. Делая это, злоумышленник преследует одну из следующихдвух целей: уничтожить водяной знак, т. е. сделать его распознавание невозможным,либо изменить водяной знак так, чтобы он идентифицировал какого-либо законопослушногопользователя.Предлагается следующий подход к противодействию этой атаке.При атаке сговором злоумышленник может различить и уничтожить без потерикачества медиа-данного лишь те биты водяного знака, которые различаются в имеющихсяу него копиях медиа-данного. В связи с этим водяной знак необходимо внедрятьв одинаковые позиции во всех копиях любого медиа-данного.Отходя от деталей внедрения, под водяными знаками будем понимать булевы векторынекоторой размерности n и их множество обозначать Wn или W , если размерностьвекторов в нём несущественна. Для того чтобы противостоять атаке сговором,предлагается в качестве последнего использовать такое подмножество W С {0 ,1}n,называемое допустимым, которое удовлетворяет условию: каждому подмножествуP С W минимальный интервал I (P ) в {0 ,1}n, его покрывающий, сопоставляетсявзаимно-однозначно, т. е. если Pi,P2 С W и Pi = P2, то I (Pi) = I (P2), и, кроме того,если |P | > 1, то I (P ) = P .В этом случае злоумышленник, проводящий атаку сговором,имеет копии некоторого медиа-данного с водяными знаками в некотором P С Wс |P | ^ 2 и получает копию этого медиа-данного с ложным водяным знаком w, выбираяего произвольно из множества I (P ) \ P . Для такого w верно w ^ W , ибо иначеI (P ) = I (P U {w}), что противоречит допустимости W .Таким образом, при атаке сговором на водяные знаки из допустимого множестваневозможно получить ложный водяной знак, который идентифицировал бы невиновногопользователя.Тем самым противодействие атаке сговором на водяные знаки, защищающие медиапродукциюот пиратства, сводится к построению больших допустимых множеств булевыхвекторов некоторой размерности. В этой связи полезно изучить предварительносвойства и установить количественные характеристики таких множеств, что, собственно,и делается далее.Обозначим k(I) размерность (количество переменных компонент векторов) интервалаI в {0 ,1}n.Утверждение 1. k (I(P )) ^ |P| для любого P С W мощности |P| > 2 и допустимогоW .Утверждение 2. Для любых допустимых множеств W и W' в {0 ,1}n еслиW С W', то |W'| ^ |W | + n - k(I(W)).Утверждение 3. Мощность любого допустимого множества Wn не больше n.Отсюда следует, что количество всех допустимых множеств векторов в {0 ,1}n непревосходит числа . ™=1 C^n.Пусть Oi(a) обозначает окружность радиуса 1 вокруг булева вектора а в пространстве{0 ,1}n, т. е. O1(a) = {x Е {0 ,1}n: d(x,a) = 1}, где d(x,y) -расстояние Хэммингамежду булевыми векторами x и у.Утверждение 4.1) O1(a) - допустимое множество;2) всякое допустимое множество мощности n имеет вид O1 (а).Ввиду утверждения 3 это значит, что все допустимые множества векторов в { 0 ,1}nнаибольшей мощности суть O1 (а) для а Е {0 ,1}n, и их количество равно 2n.Два интервала будем называть эквивалентными, если их множества внутренних(переменных) компонент совпадают. Все интервалы размерности 0 являются эквивалентнымипо определению. Пусть также E (W ) = { I (P ): P С W, |P| > 1}.Утверждение 5. Для любого допустимого множества W все элементы в E (W )попарно не эквивалентны.Подмножества W и W' в {0 ,1}n будем называть эквивалентными, если |W| = |W;|и для каждого интервала любого одного из множеств E (W) и E (W;) найдётся эквивалентныйему интервал в другом. Если W и W' допустимые, то по утверждению 5 последнеесоответствие устанавливается единственным образом. Заметим также, что любоемножество, эквивалентное допустимому, также допустимо. Непосредственно проверяется,что для любого n все допустимые множества O1(a) С {0 ,1}n образуют классэквивалентности.Утверждение 6. Мощность любого класса эквивалентности допустимых множестввекторов в {0 ,1}n не меньше 2n.В доказательстве этого утверждения показывается, как по любому допустимомумножеству можно построить ещё, как минимум, 2n - 1 эквивалентных ему другихдопустимых множеств с линейной сложностью построения одного множества.При обнаружении ложного водяного знака w в копии некоторого медиа-данноговозникает задача идентификации создавших его участников атаки сговором, состоящаяв вычислении подмножества водяных знаков, из которого атакой сговором полученэтот знак, т. е. такого P С W (или непустой его части), что w Е I (P ) \ P .Ввиду возможности пересечения минимальных интервалов, покрывающих различныеподмножества булевых векторов, эта задача может иметь несколько решений - «подозреваемых» подмножеств в W. В этом случае среди последних выбираются все минимальныепо включению (их множество обозначается M(W, w)), и из них, рассматриваемыхв порядке неубывания мощности, находится настоящий «нарушитель» путём«следственных мероприятий».Качество допустимого множества W можно оценить по его характеристическомувектору H(W) = H1(W)H2(W) . . . Hm(W), где m = |W| и для любого i = 1 ,... ,mHj(W) = max ( max |M(W,w)|) p cw,|p |=^we(/(P)\P) J .В случае, если Hj(W) = 1 для i = 1 ,...,t и некоторого t ^ m и атака сговоромпроводится группой из t или менее пользователей, т. е. ложный водяной знак w построенпо некоторому множеству P С W мощности |P | ^ t, то непустая часть этого Pвычисляется по w однозначно и, следовательно, некоторые участники этого сговораидентифицируются знаком w безошибочно.Допустимое множество водяных знаков W называется разделимым, если для любыхразличных подмножеств P1, P2, . . . , Pk С W верноk kП Pi = 0 ^ П i (Pi) = 0 .i=1 i=1В случае разделимого множества W решением задачи идентификации участниковсговора по ложному водяному знаку w является множество P = Р|p€q P , где Q == {P С W : |P| > 1, w e I(P ) \ P }.Утверждение 7. Длина векторов в разделимом множестве W не меньше, чем2|W|-1 - 1 - количества разбиений множества Wна два блока.Эта оценка является существенным препятствием для практического примененияразделимых множеств: чтобы обеспечить водяными знаками из разделимого множествахотя бы 100 пользователей, потребуются булевы векторы, длина которых не меньше299 - 1.

Скачать электронную версию публикации