Математические основы компьютерной безопасности

Валидация поведения передатчика в канале частичного стирания в случае отсутствия абсолютно различимых символов

И. Б. Казаков<sup>ab

a</sup> Российский экономический университет им. Плеханова, г. Москва, Россия
^b Московский государственный технический университет им. Баумана, г. Москва, Россия

Аннотация: Работа принадлежит циклу работ, посвящённых каналу частичного стирания, где были введены понятия структуры частичного стирания, канала частичного стирания, правильной функции и корректного протокола. Структура частичного стирания  — это тройка, состоящая из алфавита $A$, семейства его разбиений и множества вероятностей, приписанных этим разбиениям. Символы $a_1, a_2 \in A$ называются абсолютно различимыми в структуре частичного стирания, если не существует такого разбиения, что они принадлежат одному его классу. Канал частичного стирания функционирует следующим образом: Алиса посылает Бобу символ $a \in A$, но Боб узнаёт только, какое выбрано разбиение и какому классу принадлежит отправленный Алисой символ. Поведение передатчика в канале частичного стирания задаётся функцией $F: S^{*} \to A^{*}$, где $S$  — алфавит входной ленты, с которой передатчик считывает информацию. Функция $F$ однозначно определяет детерминированную функцию $\hat{F}:S^{*} \to A^{*}$: для любого слова $\hat{s} \in S^{*}$, $\hat{s} = s_1 \ldots s_m$, положим $\hat{F}(\hat{s}) = F(\Lambda) F(s_1) F(s_1 s_2) \ldots F(s_1 \ldots s_m)$, где $\Lambda$  — пустое слово. Функция $\hat{F}$ может быть представлена в виде автомата с входным алфавитом $S$ и выходным алфавитом $A^{*}$. Автомат задаётся графом, вершины которого соответствуют состояниям, а рёбра имеют две подписи: $s \in S$ и $\alpha \in A^{*}$. Для существования корректного протокола, включающего в себя функцию $F$ поведения передатчика, необходимо и достаточно принадлежности функции $F$ к классу правильных. Функция является правильной тогда и только тогда, когда отсутствует аномалия 2-го рода, не являющаяся также и аномалией 1-го рода. Под аномалией 2-го рода понимается пара слов $(\hat{s}_1, \hat{s}_2)$, такая, что $|\hat{s}_2| = |\hat{s}_1| + 1$, $|\hat{F}(\hat{s}_2)| \le |\hat{F}(\hat{s}_1)|$; под аномалией 1-го рода  — пара слов $(\hat{s}_1, \hat{s}_2)$, для которой найдётся индекс $i$, что символы $\hat{F}(\hat{s}_1)[i]$ и $\hat{F}(\hat{s}_2)[i]$ абсолютно различимы в структуре частичного стирания. В важном частном случае отсутствия абсолютно различимых символов аномалии 1-го рода не могут существовать и условие правильности упрощается до отсутствия аномалий 2-го рода. Показано, что проверка отсутствия аномалий 2-го рода сводится к проверке отсутствия путей (начинающихся в выделенной вершине) отрицательного веса в автомат-квадратном графе, которая может быть выполнена с помощью алгоритма Беллмана — Форда. Общая сложность такой проверки составляет $O(|Q|^4|S|^2)$ по времени и $O(|Q|^2|S|^2\ln|Q|\ln L\ln |S|)$ по памяти, где $|Q|$  — количество состояний автомата, представляющего функцию $\hat{F}$, и $L$  — максимальная длина передаваемого Алисой слова.

Ключевые слова: скрытые каналы, канал частичного стирания, абсолютно различимые символы, алгоритм Беллмана — Форда, проверка отсутствия аномалий 2-го рода.

УДК: 519.688

DOI: 10.17223/20710410/67/4