ТЕСТИРОВАНИЕ АЛГОРИТМА ГОМОМОРФНОГО
ШИФРОВАНИЯ НА СИСТЕМЕ С ОТКРЫТЫМ КЛЮЧОМ
Д. К. Чечулина
Новосибирский государственный университет
Лаборатория современных компьютерных технологий НИЧ НГУ
В рамках проекта «Защищенная база данных» при финансовой
поддержке Минобрнауки РФ (договор № 02.G25.31.0054) была
разработана схема полностью гомоморфного шифрования, основанная на
модулярной арифметике. Алгоритм Hom Enc представляет собой
отображение F: Z → Zn.
Схема позволяет выполнять операции сложения и
умножения над зашифрованными данными, причем за счет использования
специальной таблицы умножения удается избежать роста объема
результирующих данных.
С целью проверки корректности работы алгоритмов была построена
линейная криптосистема с открытым ключом, представляющая собой
модифицированный шифр Хилла, который в простейшем случае уязвим к
атаке с открытым текстом.
В предлагаемой криптосистеме закрытый ключ – пара (x,m), где x –
секретный вектор, m – секретный модуль. Открытым ключом является
квадратная матрица A, обратимая по модулю m, и таблица умножения γ_ijk.
На вход шифрования подается вектор целых чисел:
P = (p1,...,pn) : 0 < pi <= d, i = (1,...n),
где d < m – ограничение на входные данные. Далее с помощью ранее
описанного алгоритма вычисляется encA=Hom Enc(A) и encP=Hom Enc§,
после чего на выход шифрования отправляется результат умножения
encA * encP – вектор векторов cipher = (c1,…,cn). Заметим, что, благодаря
использованию таблицы γ_ijk, при умножении двух векторов длины n
получается вектор той же длины.
Дешифрование сводится к выполнению двух операций умножения:
сначала полученный шифртекст умножается на секретный вектор
закрытого ключа x, а затем – на матрицу, обратную матрице A. Результат
этих операций необходимо вычислить по секретному модулю m
cipher * x * A^(-1) mod m = P
Научный руководитель – канд. физ.-мат. наук С. Ф. Кренделев