2.5 Метод универсального хеширования по рациональным функциям алгебраических кривых

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

Пусть

- абсолютно неразложимая, несингулярная проективная кривая над полем ;

- точки кривой ;

- точка на бесконечности или особая точка кривой ;

- рациональные функции функционального поля кривой ;

значение дивизора или порядок полюса рациональной функции в точке;

- значение рациональной функции в точке .

Хеш функция для сообщения, в точке определяется выражением

, (2.16)

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

Свойства универсального хеширования по рациональным функциям алгебраических кривых определяются утверждением 2.7[].

Утверждение 2.7. Хеш функция определяет универсальный хеш класс, где- число точек алгебраической кривой,- объём пространства сообщений,- объём пространства хеш кодов и вероятность коллизии определяется выражением

, (2.17)

где - значение полюса рациональной функций.

Замечание 2.7.

1. Параметры универсального хеш класса на основе хеширования по рациональным функциям определяются свойствами алгебраической кривой. Подгруппа Вейерштрассаопределяется полюсами рациональных функций в особой точке кривой и рациональные функции упорядоченные по значениям полюсов образуют векторное линейное пространство размерности.

2. Ключевой параметр хеш функции определяется вычислением в точкеалгебраической кривой.

3. Для построения алгоритма вычислений необходимо определить проективное многообразие алгебраической кривой (её точки), построить линейное векторное пространство для функционального поля алгебраической кривой, задать хеш функцию, как скалярное произведение слов данных и значений рациональных функций в точке кривой, выбранной по ключу.

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

Р_кол. (2.18)

Универсальное хеширование по рациональным функциям алгебраических кривых имеет лучшие асимптотические результаты. Верхняя граница вероятности коллизии для алгеброгеометрического универсального хеширования определена в области малых значений , является прямо пропорциональной корню квадратному из и лучше оценки универсального хеширования по РС кодам и асимптотической оценки алгеброгеометрических кодов.

2.6 Строго универсальное хеширование

Строго (почти строго) универсальное хеширование определяет безусловную аутентификацию и было представлено Стинсоном []. Коллизионные оценки почти строго универсального хеширования связываются с распределениями хешей для пар сообщений по ключевому пространству, что определяет безусловную аутентификацию на массивах аутентификаторов.

Коллизионные свойства почти строго универсальных МАС кодов представлены следующими утверждениями.

Утверждение 1.5. Пусть семейство хеш функций является– строго универсальным (). Тогда,P_им. и P_под.

Утверждение 1.7. Пусть семейство почти строго универсальных хеш функций. При равновероятном выборе хеш функции вероятность успеха имитационной атаки равнаP_им и вероятность подмены P_под. Доказательство аналогично предыдущему.

Замечание 2.4.

1. Строгая универсальность определена для .

2. При смягчении требования класс функций определяется как почти строго универсальный.

Характеристики универсальных классов хеш функций приведены в табл. 1.11.

Таблица 1.11

Оценки секретности кодов аутентификации сообщений для универсальных классов хеш функций.

Виды аутентификации	Универсальные классы хеш функций	Pим.	Pпод
Доказуемо стойкая аутентификация со счетчиком	e–U(N;n,m)		1/m
	e–AU(N;n,m)		e
Безусловная аутентификация	e–SU(N;n,m)	1/m	1/m
	e–ASU(N;n,m)	1/m

Замечание 2.5.

1. Универсальное хеширование определяет требование - размер ключевого пространства должен быть не меньше пространства сообщения. Почти универсальное хеширования ослабляет это условие, размер ключа может быть больше или равен размеру хеш кода.

2. Строго универсальный хеш класс характеризуется предельным наименьшим значением вероятности имитации и подмены, но размер ключевого пространства не меньше чем в квадрат раз превышает размер хеш кода.

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