Основные определения и обозначения
Пусть АУТ(m) - обычный (оригинальный) алгоритм аутентификации сообщений и АУТa(m)- функция маркирования сообщения m, индуцированная схемойАУТ с ключом аутентификации a. Пусть ВЕРa(m,b) - соответствующий алгоритм верификации, где b={true, false} – предикат корректности проверки.
Далее будут использоваться деревья поиска и, следовательно, необходимо напомнить, что 2-3-дерево имеет все концевые узлы (листья) на одном и том же самом уровне/высоте (как и в случае сбалансированных двоичных деревьев) и каждая внутренняя вершина имеет или 2, или 3 дочерних узла [АХУ]. В данном случае 2-3-дерево подобно двоичному дереву является упорядоченным деревом и, таким образом, концевые узлы являются упорядоченными. Пусть Vh
– определяет множество всех строк длины не больше h, ассоциированных очевидным образом с вершинами сбалансированного 2-3-дерева высоты h. Маркированное дерево может рассматриваться как функция Т: Vh®{0,1}*, которая приписывает аутентификационный признак (АП) каждой вершине.
Пусть совокупный аутентификационный признак файла F получен посредством использования 2-3-дерева аутентификационных признаков для каждого из блоков файла F=F[1],...,F[l] (далее такое дерево будет называться маркированным деревом). Каждая вершина w ассоциирована с меткой, которая состоит из АП (аутентифицирующих дочерние узлы) и счетчика, представляющего число узлов в поддереве с корнем w.
