ГОМОМОРФНОЕ ШИФРОВАНИЕ

Говоря о задаче в области информационной безопасности, рассмотрим одно из перспективных направлений развития информационных технологий — облачные вычисления и хранилища данных. Данная технология позволяет значительно уменьшить расходы на ИТ-инфраструктуру и гибко реагировать на изменения вычислительных потребностей. С другой стороны, подобное хранение и обработка конфиденциальных данных не является безопасной ввиду возможности неконтролируемого доступа к этим данных со стороны провайдера облачной инфраструктуры, а также риска вредоносных вторжений в облако.

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

1. Области применения гомоморфного шифрования

1.1 Облачные системы (cloud systems, cloud computing)

Облачные системы — удаленные системы хранения данных и сервисы, позволяющие производить обработку этих данных. Конечно же, для защиты информации предоставляются определенные криптографические механизмы. Однако почти сразу обнаруживается один недостаток таких систем: для модификации удаленных данных необходима передача по сети секретного ключа, т.е. попросту его раскрытие, что ставит безопасность под угрозу.

Представим себе следующую ситуацию: некий облачный сервер содержит информацию о наших доходах, данные с него периодически обрабатываются налоговым сервисом, рассчитывая таким образом сумму налога. Но для выполнения подсчетов сервис должен иметь доступ к расшифрованной информации, что вынуждает нас передавать ему секретный ключ по каналам связи. Не проще ли было бы использовать средства, позволяющие оперировать зашифрованными данными так же, как и открытыми? Существуют ли такие средства? Ответ — да, и это — гомоморфное шифрование.

1.2. Электронное голосование (electronic voting)

Криптография нашла широкое применение в системах голосования. В этой части статьи речь пойдет о том, как гомоморфное шифрование может помочь в проведении процедуры коллективного выбора.

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

Итак, мы имеем:

— бюллетень как вектор (К₁, К₂, ..., К_n)

— открытый ключ — ОК

Тогда каждый из избирателей составляет вектор предпочтения — (П₁, П₂, ..., П_n), где каждое П_i ∈ {0, 1}, после чего шифрует каждый элемент из него и отправляет список зашифрованных нулей и единиц инициатору голосования. Последнему для подсчета голосов остается всего лишь сложить соответствующие элементы полученных массивов и произвести расшифровку. Помимо безопасности, данная схема вносит вклад в производительность системы, в отличие от негомоморфных схем шифрования. В случае использования криптосистемы, не обладающей гомоморфными свойствами, инициатору голосования потребуется произвести N расшифровок полученных векторов, где N – общее число проголосовавших, и только затем произвести суммирования для подведения итогов. Гомоморфная же система позволяет сначала сложить полученные от избирателей шифротексты, а затем один раз расшифровать суммарный вектор.

Это самая простая схема голосования с использованием гомоморфного шифрования, возможны, конечно, ее модификации.

Тем не менее, описанная процедура позволяет поддерживать конфиденциальность выбора участников, довольно проста и может использоваться для организации голосования по сети, что представляет собой немалый плюс.

1.3. Поиск без раскрытия (private information retrieval)

Так сложилось, что человеку необходимо работать с информацией: уметь производить её поиск, обработку, усваивание, решать вопросы, связанные с хранением. К счастью, на сегодняшний день имеется много сервисов, упрощающих жизнь в этом отношении и помогающих преодолевать некоторые трудности. Однако они могут не всегда соответствовать требованиям клиентов. Например, не все поисковые системы на данный момент поддерживают приватный поиск — поиск, при котором поисковый сервер ничего не знает о том, какие запросы присылают ему пользователи. Хотя такая вещь очень бы понадобилась людям, желающим сохранить конфиденциальность своих интересов.

Самым тривиальным решением вышеописанной проблемы была бы передача всех данных с сервера пользователю. Тогда владелец базы точно не узнает, что именно нужно пользователю. Но, а что, если данных много? Если их еще нужно шифровать? Сжимать? Появляются серьезные проблемы, связанные с временем и ресурсами. Но тут нам приходит на помощь гомоморфное шифрование.

Для простоты давайте предположим, что на каком-то сервере хранится n-битный вектор x, а клиенту необходимо узнать i-ый бит, да так, чтоб его запрос был конфиденциален. Идея очень проста, как и все гениальное. Пользователь отсылает серверу зашифрованный бинарный вектор, каждый бит которого — зашифрованный ноль (естественно, с помощью гомоморфного алгоритма), кроме i-го бита. На сервере тогда выполняется скалярное умножение полученного вектора на x. Результат передается клиенту, который просто расшифровывает пришедшие данные и получает ответ на свой запрос. [2, с. 5]

2. Исторические факты

Идея полностью гомоморфного шифрования была предложена в 1978 году изобретателями алгоритма шифрования с открытым ключом RSA Ривестом и Шамиром совместно с Дертузо. Они предположили возможность выполнения произвольных операций над зашифрованными данными без потребности их расшифровывания. В то время все попытки создания полностью гомоморфной криптосистемы были неуспешны. Разработанные в последующие годы криптосистемы Эль-Гамаля, Гольдвассер — Микали, Пайе и многие другие являлись лишь частично гомоморфными.

Долгое время полностью гомоморфная криптосистема оставалась для всех криптографов мира священным Граалем, недостижимым идеалом. Прорыв в исследовании полностью гомоморфного шифрования произошел в 2009 году, когда Крейг Джентри, используя криптографию на решетках, впервые представил вариант полностью гомоморфной криптосхемы. С тех пор появилось немалое количество работ, предлагающих модификацию криптосистемы Джентри, улучшающую ее производительность. Параллельно с этим криптографы работают над альтернативными способами построения полностью гомоморфных криптосистем, включающими в себя использование симметричного шифрования вместо шифрования с открытым ключом, полиномов от одной или многих переменных, а также матричных полиномов.

3.  Обзор и реализация некоторых систем гомоморфного шифрования.

В данной статье мы хотим сделать обзор, сравнение и программную реализацию на гомоморфные системы Грейга Джентри, а также предложить свои нововведения в алгоритмы, которые должны обеспечить улучшение производительности. Некоторые описываемые алгоритмы обладают высокой математической сложностью, из-за чего затрудняется программная реализация таких математических выкладок. Наша работа в данной статье направлена на преодоление различных трудностей, связанных с переносом схемы с листа в реально работающую систему. Реализация всех представленных в статье систем была произведена на языке программирования Python 2.7 ввиду наличия математической библиотеки sage, а также высокой переносимости и встраиваемости в различные виды программных решений.

В каждой гомоморфной криптосистеме можно выделить некоторые общие алгоритмы

• Генерация ключей - KeyGen:
  
  • Секретный ключ – sk
  • Открытый ключ – pk
• Алгоритм шифрования – Encrypt
• Алгоритм дешифрования – Decrypt
• Гомоморфное вычисление – Eval

Необходимая терминология:

• Открытый тест - Opentext O
• Шифротекст - Ciphertext C

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

                                          (1)

Алгоритм дешифрования принимает на вход шифротекст и закрытый ключ. На выходе получаем открытый текст.

O                                        (2)

Гомоморфное вычисление Eval оперирует некоторой математической функцией f() и парой шифротекстов С1, С2. Результатом вычисления будет некий шифротекст C, причем такой, что

                                            (3)

                                         (4)

3.1 Somewhat Homomorphic Encryption

Рассмотрим частично гомоморфную схему, а именно схему гомоморфную относительно операции сложения [2, с. 71]. Данная схема построена на группе вычетов целого числа N. Таким образом, закрытый ключ в данной схеме представляет собой целое число, на которое накладываются следующие условия:

1. Число должно быть много больше N;
2. Число должно быть взаимно простым с N.

Этапы шифрования и некоторые подробности нашей реализации:

1) Выбор числа N

Группа целых чисел, с которыми будет способна работать криптосистема генерируется как, группа вычетов по модулю N. Таким образом в качестве открытого текста могут выступать числа от 0 до N.

2) Генерация ключей (KeyGen)

1. Секретный ключ - sk.

Генерируется случайное число sk, такое что sk >> N и НОД(sk, N) = 1.  В нашей реализации накладывается еще одно условие: sk не может быть больше 2^31, для того, чтобы число не вышло за пределы такой структуры данных, как int.

2. Открытый ключ - pk.

Открытым ключом является набор больших чисел {a₁,a₂,..,a_n} таких что a_i mod N=2e_i, где e_i числа намного меньше N. В нашей реализации n является константой и равняется 100.

3) Шифрование (Encrypt)

Алгоритм шифрования принимает на вход открытый текст m и открытый ключ pk. Из набора pk случайным образом выбирается 50 элементов ai и суммируются с m. Таким образом шифротекст = m + i = 050ai

4) Дешифрование (Decrypt)

Алгоритм дешифрования принимает на вход шифротекст c и секретный ключ sk. Открытый текст m = (с mod sk) mod N.

5) Операции над шифротекстом (Eval)

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

Плюсы данной гомоморфной системы относительно других гомоморфных систем:

1. Малая потребность в вычислительных ресурсах.  Единственный плюс данной системы вытекает из ее минусов, которые мы рассмотрим ниже.

Минусы данной гомоморфной системы относительно других гомоморфных систем:

1. Данная схема оперирует с числами из группы вычетов некоторого числа N, что означает, что множество открытых текстов - конечное.
2. Опытным путем было установлено, что из-за наличия так называемого математического “шума” имеется ограничение на количество операций над шифротекстами.
3. Не стоит забывать, что описанная схема - частично гомоморфная, поэтому в ней доступна лишь операция сложения.

Реализация и пример работы данной системы:

Исходный код программы доступен на ресурсе: https://pastebin.com/C9ENtdit

Пример работы алгоритма: Выбираем основание N - 3000. Таким образом мы ограничили себя группой целых чисел по вычету 3000. Алгоритм сгенерировал секретный ключ: 1471382873

Далее зададим два числа из этой группы.  А = 30, Б  = 50. Зашифруем оба числа описанным выше алгоритмом и на выходе получим два шифротекста: АШ = 228281179345; БШ = 231231610111

Произведем операцию сложения над шифротекстами:

 РШ = АШ + БШ = 228281179345 + 231231610111 = 459512789456

Расшифруем полученный результат РШ описанным выше алгоритмом. Для этого приведем число 459512789456 по модулю sk - 1471382873 получим число 441333080. Его в свою очередь приведем по основанию - N = 3000 , получим 80. Таким образом мы получили тот результат, который получился бы при обычном сложении двух открытых текстов 30 + 50 = 80.

3.2 Схема гомоморфного шифрования на основе матриц

Рассмотрим гомоморфную схему, позволяющую производить операции сложения и умножения над шифротекстами. Данная схема построена на основе квадратных матриц n×n. Секретным ключом будет вектор длины n. Поэтому для данной криптосистемы выбирается число n.

Этапы шифрования:

1) Генерация секретного ключа (sk)

Секретным ключом является произвольный вектор длины n. Он используется для шифровки и дешифровки данных.

2) Шифрование (Encrypt)

Алгоритм шифрования принимает на вход открытый текст m и секретный ключ sk.  Далее генерируется матрица M размером  такая, что произведение матрицы М на sk равно произведению открытого текста m на sk.

                                           (5)

Матрица M и будет шифротекстом.

3) Дешифрование (Decrypt)

Алгоритм дешифрования принимает на вход шифротекст M и секретный ключ sk. Открытый текст находится путем перемножения М на sk, после чего полученный вектор приводится к виду m × sk, где m и есть открытый текст.

4) Операции над шифротекстом (Eval)

Данная схема гомоморфна относительно операций сложения и умножения.  Для получения корректного результата достаточно просто сложить или умножить два шифротекста ( матрицы ), а затем полученную матрицу расшифровать алгоритмом Decrypt. Таким образом выполняется соотношение: E(A+B) = E(A) + E(B), где E алгоритм шифрования, A и B – шифротексты ( матрицы ).

Плюсы данной гомоморфной системы относительно других гомоморфных систем:

1. Гомоморфность относительно как сложения, так и умножения.

Минусы данной гомоморфной системы относительно других гомоморфных систем:     

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

Реализация и пример работы данной системы:

Исходный код программы доступен на ресурсе: https://pastebin.com/DvsmuHQp

Пример работы алгоритма:

Алгоритм генерирует секретный ключ – вектор =  sk  (-22, -2, -1)

Зашифруем два числа x = 100 и y = 224. В результате работы алгоритма шифрования получим  

X=  – матрица-шифротекст числа х

Y = – матрица-шифротекст числа у

В результате умножения матриц X и Y получаем результирующий шифротекст:

R =

Для расшифровки шифротекста R умножим его на секретный             ключ – вектор sk (-22, -2, -1). Получим соотношение: R x sk = 22400 x sk.

Отделив известный sk от правой части выражения, получим правильный ответ – 22400.

3.3 Схема полного гомоморфного шифрования на основе матричных полиномов

Рассмотрим схему полного гомоморфного шифрования на основе матричных полиномов [1, с. 18]. Сразу стоит отметить, что реализация данной схемы находится в процессе работы, поэтому к данной системе не будет приложен исходный код.

 Пусть  - кольцо N x N матриц с элементами из кольца  целых чисел по модулю числа p. Рассмотрим множество последовательностей матриц из   .

F = { , …},  ∈ , таких, что все  , кроме конечного их числа, равны нулевой матрице. [X] обозначает множество таких последовательностей.

Если F,G ∈ [X], G = { , , , …},  ∈ , тогда определим:

F + G = {  + ,  + ,  +  … }

F x G = { x ,    +   ,  B2  +    + , … } = {}, где = , k = 0, 1, 2…

Можно доказать, что при таких определениях операций сложения и умножения множество: [X]  становится кольцом, а элементы этого кольца - матричными полиномами. Для дальнейшего изложения воспользуемся следующими обозначениями:

1.  s ← R означает, что s из R выбирается по равномерному распределению

2.  ƛ - параметр криптостойкости.

3.  ω, ẟ, ψ - некоторые заранее установленные константы.

Этапы шифрования и некоторые подробности нашей реализации:

1) Генерация ключей (KeyGen)

1.  Генерируется приведенный полином K(X) ∈ [X], такой что deg (K(X)) <= ω x ƛ, а его старшие коэффициенты  , i = 0,..., deg(K(X)) - 1. Генерируется вектор

k ∈ ,  ← , такой, что хотя бы одна координата вектора должна быть обратимой в . Итого на выходе алгоритма секретный ключ sk {K(X), k }

2.  Генерируется матричный полином R’(X) ∈ [X] такой,  что  deg(R’(X))<=  ẟ x ƛ, ← , i = 0,..., deg(R’(X)) - 1.

Получим ключ вычисления evk = {R’(X) x K(X)}

 2)  Шифрование (Encrypt)

1. Открытому тексту m  ∈  сопоставляется случайная матрица      M ∈  такая,  что M x k = m x k и M x K(X) = K(X) x M т.е. она имеет собственный вектор k при собственном значении m и коммутирует с матричным полиномом K(X). Для выполнения условия коммутативности нами было принято решение, ограничить все используемые матрицы пространством коммутативных матриц. В противном случае потребовалось бы решать систему линейных уравнений, состоящую из матриц, что при больших значениях констант ω, ẟ, ψ привело бы к большой просадке производительности.
2. Генерируется R(X) ∈  [X], где deg R(X) <= ψ x ƛ, выбирается так, что deg(R(X)) < deg(R’(X)) - deg(K(X)),   ← ,                    i = 0,..., deg(R(X)).
3. Вычисляется шифротекст C(X) = R(X) x K(X) + M

3) Дешифрование (Decrypt)

1. Вычисляется M = C(X) mod K(X)
2. Для обратимой координаты ki вычисляется m = -1x (M x k), где k - собственный вектор матрицы M.

4) Операции над шифротекстом (Eval)

Сопоставление полиному f (, … ) над , ... ,  ∈  полинома f﬩(, … ) над соответствущими шифротекстами , …  осуществляется простой заменой операции над  на сложение или умножение полиномов в [X]. Для предотвращения роста степени матричных полиномов после их умножения осуществляется приведение по модулю evk.

Для шифротекстов, выданных алгоритмом Enc,                                        с ← R (X) x K (X) + M алгоритм расшифрования выдает                                       m = -1((C(X) mod K(X)) x k.                                                            

При сложении + = ( (X) +  (X)) x K(X) +  + , что является правильным шифротекстом суммы (+ m2) mod p.

Поскольку (+ ) x k = (+  ) x k гомоморфное умножение дает  x = (X) x K(X) x  (X) x K(X) + (X) x K(X) x  +  x  (X) x K(X) +  x  = ((X) x K(X) x  (X) + (X) x  +  (X) x ) x K(X) +  x ,  что является также корректным шифротекстом и после расшифровки дает ( x ) mod p, поскольку  ( x ) x k = x (  x k ) = x ( x k )  =  * ( x  k ) =  x  x k.

Плюсы данной гомоморфной системы относительно других гомоморфных систем:

1.  Полная гомоморфность относительно операций сложения и умножения.

2.  “Фильтрация” накопленного математического шума. Наличие фильтрации позволяет не ограничиваться в количестве операций над шифротекстами.

Минусы данной гомоморфной системы относительно других гомоморфных систем:     

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

4. Вывод

Подводя итоги, можно с уверенностью сказать, что гомоморфное шифрование – перспективное и актуальное направление криптографии. Совсем недавно, в 2009 году, Грейг Джентри открыл  дверцу для новых исследований в этой области. Столь недавняя дата говорит сама за себя: его открытие - это важное событие  начала  XXI века.

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

 

 Список литературы:

1. Бабенко Л.К., Буртыка Ф.Б., Макаревич О.Б. Методы полностью гомоморфного шифрования на основе матричных полиномов // Вопросы кибербезопасности, – 2015. – №1. – С. 17–20.
2. Gentry G. A Fully Homomorphic Encryption Scheme, 2009 – P. 71-80.
3. Maimut D.S., Patrascu A., Simion E. Homomorphic encryption schemes and applications for secure digital world // JMEDS – 2012 – №4 – P. 5.