Public-key cryptosystem based on fully homomorphic encryption.pdf В Лаборатории современных компьютерных технологий НИЧ НГУ в рамках проекта «Защищённая база данных» разработана и реализована схема полностью гомоморфного шифрования, позволяющая выполнять операции сложения и умножения над зашифрованными данными. Рассмотрим подробнее эту схему. Пусть требуется шифровать целые числа размера t бит. Для этого необходимо выбрать целое число - модуль m, по которому будут производиться все вычисления в схеме. Модуль является частью секретного ключа. Для того чтобы однозначно восстановить любое зашифрованное число, модуль должен удовлетворять условию 2* < m. Кроме того, для шифрования требуется секретный вектор k Е Zn, который строится следующим образом. Сгенерируем матрицу W размера n х n, обратимую по модулю m, а также вектор u Е Zn, компоненты которого по модулю не превосходят m. Вектор k определим как решение системы линейных уравнений (W ■ k) mod m = u, которая всегда разрешима, так как матрица W обратима по модулю m. Таким образом, k = (W-1 -u) mod m. Матрица W и вектор u также являются частью секретного ключа. Перейдём к описанию алгоритма шифрования. Пусть p < 2* < m - целое число, которое требуется зашифровать. Алгоритм гомоморфного шифрования заключается в построении такого вектора с Е что (с, k) mod m = p. (1) Заметим, что в процессе построения вектора k сформирован набор векторов Wj (строк матрицы W), i = 1,..., n, таких, что (wj, k) mod m = и. Выберем из этого набора любые s, s Е {2,..., n}, векторов w1,..., ws, которые будем использовать для шифрования. Тогда вектор с, являющийся шифртекстом, будем строить как линейную комбинацию этих векторов: s С = Е «г ■ Wj. г=1 Коэффициенты аг найдём из диофантова уравнения и1а1 + ... + usas = p. Для того чтобы данное уравнение было разрешимо, необходимо существование как минимум двух взаимно простых компонент вектора и. Сформированный таким образом шифртекст c однозначно расшифровывается согласно формуле (1): sss (с, k) mod m = ( Е k I mod m = E a(w,, k) mod m = E mod m = p. \i=1 / i=1 i=1 Описанная схема шифрования является гомоморфной по сложению и умножению в силу свойств скалярного произведения и модулярной арифметики [1]. Рассмотрим подробнее операцию умножения. Найдём шифртекст для произведения чисел p1 и p2, которым соответствуют шифротексты a и b: Р1 ■ Р2(mod m) = (a, k)(b, k) = (a1k1 + ... + a„k„)(b1k1 + ... + b„k„) = = a1&1 k^1 + a1b2 k1k2 + ... + a„bra-1 k„k„-1 + a„b„krakra = = (a1b1 ,a1b2,... ,a„b„-1, a„b„)(k1k1, k1k2,..., k Таким образом, в результате умножения двух шифртекстов длины n получается шифртекст длины n2: 2 с = a ■ b = (a1b1, a1b2,..., anbn-1, anbn) Е . Для решения этой проблемы предлагается использовать специальную таблицу умножения - матрицу (Yjk). С её помощью компоненты вектора с = (с1,... , cn) -результата произведения двух шифртекстов - вычисляются следующим образом: cfc = Е Е Yj ■ a, ■ bj, k = 1,..., n. i j Если таблица умножения несимметрична, то для операции умножения шифртек-стов не выполняются свойства коммутативности и ассоциативности. За счёт этого гомоморфное шифрование является недетерминированным. Таблица умножения не является секретной и предъявляется в открытом виде недоверенной стороне, на которой выполняются вычисления над зашифрованными данными. Далее рассмотрим применение гомоморфного шифрования для построения криптосистемы с открытым ключом, с помощью которой проверяется корректность вычисления полиномиальных функций над зашифрованными данными. Описываемая криптосистема формируется на основе некоторого аналога известного алгоритма RSA [2], в котором модуль объявляется секретом. К сожалению, такая криптосистема является нестойкой, однако её можно модифицировать за счёт использования гомоморфного шифрования. Таким образом, предлагается возводить в степень предварительно зашифрованное исходное число. Секретным ключом назовем модуль m и вектор k, которые используются в гомоморфном шифровании. В качестве открытого ключа возьмем векторы wi,w2 и соответствующие им взаимно простые числа ui,u2: (w^,k) mod m = u^, i = 1, 2, и, кроме того, выберем целое число e, обратимое по модулю 0(m), где 0(x) -функция Эйлера. В открытом ключе хранится также таблица умножения (Yijfc). Предположим, что требуется зашифровать целое число p < 2t < m. Для этого сначала применим к p алгоритм гомоморфного шифрования, в результате чего получим шифртекст с. Затем подействуем на вектор c полиномиальной функцией F(x) = xe: F (с) = ce = z. Обратим внимание на то, что функцию F можно вычислять различными способами. Так как операция умножения шифртекстов не коммутативна и не ассоциативна, результат возведения шифртекста C в степень e определяется расстановкой скобок при выполнении умножения, например, с• (с•... • с) = (с•... • с) • с. Благодаря этому алгоритм шифрования является недетерминированным. При расшифровании необходимо сначала найти скалярное произведение (z, k) по модулю m: (z, k) mod m = (се, k) mod m = pe mod m. Кроме этого, отметим, что так как вектор с получен с помощью гомоморфного шифрования, вычисление функции F(с) эквивалентно вычислению функции F(p). Далее для восстановления исходного числа, аналогично алгоритму RSA, результат скалярного произведения (z, k) mod m возводится в степень d = e-i mod 0(m): (pe mod m)d = ped mod m = p. Приведённую криптосистему с открытым ключом можно модифицировать за счёт использования более сложных полиномиальных функций, функций от нескольких переменных или за счёт операции замены переменных. Помимо рассмотренной криптосистемы, исследована криптосистема с открытым ключом, построенная на основе шифра Хилла с использованием гомоморфного шифрования. Однако такая система сводится к описанной выше, если заменить линейное преобразование на полиномиальное и применить предложенные модификации. Поэтому в работе описан только полиномиальный вариант, который является более общим.

Скачать электронную версию публикации