Коды цифровых отпечатков пальцев для мультимедийного контента

Данная работа посвящена исследованию технологии цифровых отпечатков пальцев для решения задачи разработки средств защиты информации от нелегального распространения и перепродажи, известной как задача борьбы с ``(видео)пиратами''. В первой части данной работы дается формальная постановка дискретной версии данной проблемы. Описываются основные известные конструкции, а также исследуется сравнительно новая концепция - почти IPP коды. В работе доказывается, что не существует двоичных почти IPP кодов предназначенных для борьбы с коалициями, состоящими более чем из двух участников. Также вводится ослабление условия преследования пиратов —— список подозреваемых. Доказываются верхние и нижние границы на мощность таких списков. Во второй части работы дается формулировка задачи цифровых отпечатков пальцев для мультимедийного контента. Первым результатом является доказательство существования хороших мультимедийных кодов, т.е. мощность которых зависит экспоненциально от длины, способных восстанавливать всю виновную коалицию. Заметим, что во всех предыдущих работах предлагаемые конструкции не были хорошими в указанном смысле (даже с учетом предположения об известной стратегии коалиции). Далее, мы показываем, что мультимедийная постановка задачи цифровых отпечатков пальцев эквивалентна задаче построения кодов для одного давно известного канала множественного доступа. Также, мы предлагаем конструкцию таких кодов и приводим алгоритм декодирования, работающий за полиномиальное от длины кода время.