Полностью гомоморфное шифрование

Полностью гомоморфное шифрование — шифрование, позволяющее для данного шифротекста π₁,…,π_t каждому человеку (не только держателю ключа) получить шифротекст любой желаемой функции f(π₁,…,π_t) до тех пор, пока данная функция может быть эффективно вычислена.

Впервые идея полностью гомоморфного шифрования была предложена в 1978 году изобретателями криптографического алгоритма с открытым ключом RSA Рональдом Ривестом и Ади Шамиром совместно с Майклом Дертузосом.^[1] Однако на начальных этапах попытки создания криптосистемы с таким шифрованием были неудачны. Многие годы было непонятно, возможно ли вообще полностью гомоморфное шифрование, хотя попытки создания такой системы предпринимались неоднократно. Так, например, криптосистема, предложенная в 1982 году Шафи Гольдвассер и Сильвио Микали, имела достаточно высокий уровень криптостойкости, но была лишь частично гомоморфной (гомоморфной только по сложению) и могла зашифровать только один бит.^[2] Еще одна аддитивно гомоморфная система шифрования была предложена в 1999 году Паскалем Пэйе.^[3] Прорыв в развитии полностью гомоморфного шифрования приходится на 2009 год, когда Крейг Гентри впервые предложил вариант полностью гомоморфной криптосистемы, основанной на криптографии на решетках.^[4] С тех пор появилось большое количество работ, в которых предлагается модификация криптосистемы Гентри с целью улучшения ее производительности.

Полностью гомоморфное шифрование — криптографический примитив, представляющий собой функцию шифрования, удовлетворяющую дополнительному требованию гомоморфности относительно каких-либо операций над открытыми текстами. Функция шифрования ${\displaystyle E(k,m)}$, где m — открытый текст, k — ключ шифрования, гомоморфна относительно операции ${\displaystyle *}$ над открытыми текстами, если существует эффективный алгоритм ${\displaystyle M}$, который, получив на вход любую пару криптограмм вида ${\displaystyle E(k,m_{1}),E(k,m_{2})}$, выдает криптограмму ${\displaystyle c}$ такую, что при дешифровании ${\displaystyle c}$ будет получен открытый текст ${\displaystyle m_{1}*m_{2}}$ ^[5]. Аналогично определяется гомоморфизм относительно операции ${\displaystyle +}$.

В то время, как частично гомоморфные криптосистемы гомоморфны лишь относительно одной операции над открытым текстом (либо сложения, либо умножения), полностью гомоморфные системы поддерживают гомоморфизм относительно обеих операций (как сложения, так и умножения) ^[6]. То есть для них выполнены следующие условия: ${\displaystyle \left\{{\begin{matrix}Dec(Enc(m_{1})\otimes Enc(m_{2}))=m_{1}*m_{2}\\Dec(Enc(m_{1})\oplus Enc(m_{2}))=m_{1}+m_{2}\end{matrix}}\right.}$

Более того, гомоморфности по операциям сложения и умножения достаточно, чтобы система была полностью гомоморфной.^[6]

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

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

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

Для «шумной» схемы Гентри процедура модификации схемы в «гибкую» эффективно «обновляет» шифротекст, применяя к нему гомоморфную процедуру дешифрирования, таким образом получая новый текст, который шифрует те же данные, что и раньше, но с меньшим уровнем шума. Периодически при достижении высокого уровня шума «обновляя» шифротекст, возможно производить над ним произвольное число операций без помех. Защищенность своей схемы Гентри обосновал двумя проблемами: проблемой сложности худшего случая криптографии на идеальных решетках^[англ.] и задачей о сумме подмножеств.

В докторской работе Гентри^[7] имеется более детально описание.

Несмотря на свою производительность, шифротексты в схеме Гентри остаются компактными, так как их длины не зависят от сложности функции, которая рассчитывается для зашифрованных данных. Но схема непрактична из-за резкого роста размера шифротекста и затрат на вычисление в зависимости от уровня защиты. Дамьен Шехли и Рон Штейнфелд представили ряд оптимизаций и улучшений,^[8] и впоследствии Найджел Смарт^[англ.] с Фредериком Веркаутереном,^[9][10] и Крейг Гентри^[англ.] c Шайем Халеви^[англ.],^[11][12] представили первые рабочие реализации полностью гомоморфной схемы шифрования Гентри.

В 2010 году Мартин ван Дейк, Крейг Гентри^[англ.], Шай Халеви^[англ.] и Видон Вайкунтанахан представили вторую полностью гомоморфную систему^[13]. Она использовала много принципов криптосистемы Гентри, но не требовала идеальных решёток^[англ.]. Вместо этого они показали: можно заменить гомоморфный компонент на идеальных решётках на простую гомоморфную схему, которая использовала бы целые числа. Эта схема является концептуально проще схемы Гентри, но обладает схожими параметрами в плане гомоморфности и эффективности.

Гомоморфный компонент в работе Дейка схож со схемой шифрования, представленной Левьелом и Наккахой в 2008^[14], а также похож на тот, что был представлен Брамом Кохеном в 1998^[15]. Но метод Кохена не является гомоморфным относительно операции сложения. Схема Левьелы-Наккахи поддерживает только операцию сложения и может быть модифицирована для поддержки малого числа операций перемножения. Многие улучшения и оптимизации схем были представлены в ряде работ Джен-Себастиан Корона, Танкрида Лепойнта, Аврадипа Мандалы, Дэвида Наккхи^[англ.] и Мехди Тибухи^{[16][17][18][19]}.

Несколько новых техник были разработаны начиная с 2011—2012 года Цвиком Бракерски, Крейгом Гентри^[англ.], Видоном Вайкунтанаханом и другими. Эти разработки привели к ряду более эффективных полностью гомоморфных криптосистем. В их числе:

• Криптосистема Бракерски-Гентри-Вайкунтанахана (BGV),^[20] построенная на технике Бракерски-Вайкунтанахана.^[21]
• Криптосистема Бракерски.^[22]
• Криптосистема на NTRU созданная Лопез-Альтом,Тромером и Вайкунтанаханом (LTV).^[23]
• Криптосистема Гентри-Сахай-Вотерс (GSW).^[24]

Защищенность большинства схем основана на сложности решения проблемы обучения с ошибками. Только у LVT схемы защита реализована на варианте вычислительной NTRU задачи. У всех этих систем в отличие от ранних схем более медленное нарастание шума в процессе гомоморфных вычислений. В результате дополнительной оптимизации, сделанной Крейгом Гентри^[англ.], Шаем Хавели^[англ.] и Найджелом Смартом^[англ.] , была получена криптосистема с практически оптимальной асимптотической сложностью: сложность вычисления ${\displaystyle T}$ операций над зашифрованными данными с параметром защиты ${\displaystyle k}$ имеет сложность вычисления лишь ${\displaystyle T\cdot polylog(k)}$.^[25][26][27] Эти оптимизации построены на технике Смарта-Веркаутерена, которая позволяет сжимать набор текстовых переменных в один шифротекст и работать над данными переменными одним потоком.^[10] Многие достижения из второго поколения полностью гомоморфных систем также были использованы в криптосистеме на целых числах.^[18][19]

Цвика Бракерски и Видон Вайкунтанахан заметили, что для ряда схем криптосистема GSW показывает слабый рост уровня шума, и, следовательно, большую эффективность, и большую защищенность.^[28] Якоб Алперин-Шерифф и Крис Пейкерт позднее описали эффективную технику преобразования шифротекста в гибкий, которая как раз и использует такой тип схем.^[29] Но этот тип преобразования не совместим с методами сжатия шифротекста, и, таким образом, оптимизации Гентри-Сахай-Вотерс не могут быть применены к ней^[25].

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

Первой реализацией полностью гомоморфного шифрования была схема Гентри-Халеви, реализованная на основе вышеуказанной схемы Гентри.^[12] На простую битовую операцию ей требовалось 30 минут. После появления второго поколения криптосистем, эта реализация устарела.

В литературе имеется много реализаций почти гомоморфных систем второго поколения. Реализованная Гентри, Хавели и Смартом (GHS)^[27] вариация BGV криптосистемы^[20] показала результат в 36 часов при расчете сложной схемы, реализующей AES шифрование. Используя техники сжатия шифротекста, эта реализация могла пересчитать эту же схему на 54 разных входах за те же 36 часов, таким образом получив результат в 40 минут на один вход. Расчет AES схемы был выбран как ориентир для нескольких последующих работ,^[18][30][31] где удалось заметно снизить время расчета до 4 часов при затрате 7-ми секунд на один вход.

Две реализации второго поколения криптосистем доступны для общественного пользования:

• Библиотека HElib^[32], сделанная Шаем Хавели^[англ.] и Виктор Шоуп, которая реализует криптосистему BGV с GHS оптимизацией
• Библиотека FHEW^[33], сделанная Лео Дуглас и Даниэль Миккианакио, которая является реализацией комбинации криптосистемы обучения с ошибками Регева и техники создания гибкой схемы Алперин-Шериффа и Пейкерта .^[29]

Обе библиотеки являются реализациями полностью гомоморфного шифрования. HElib показывает результат в 5-10 минут для преобразования сжатого шифротекста с порядка 1000 знаков в гибкий.^[34] FHEW преобразует несжатый шифротекст в гибкий за порядка 1/2 секунды на один бит.^[35] В конце 2014 обновленная реализация HElib показала результат в 4 минуты для расчета AES схемы для 120 входных потоков, достигнув тем самым удельной скорости в 2 секунды на один поток.^[32]

Схема полностью гомоморфного шифрования, которую предложил Гентри, может быть рассмотрена на примере вычислений в ${\displaystyle \mathbb {Z} _{2}}$.^[36]

Процесс шифрования данных можно представить следующим образом:

1. Выбирается произвольное нечетное число ${\displaystyle p=2k+1}$, являющееся секретным параметром. Пусть ${\displaystyle m\in \left\{0,1\right\}}$.

2. Составляется число ${\displaystyle z\in \mathbb {Z} _{2}}$ такое, что ${\displaystyle z=2r+m}$, где ${\displaystyle r}$ — произвольное число. Это значит, что ${\displaystyle z=m\ mod\ 2}$.

3. В процессе шифрования всякому ${\displaystyle m}$ ставится в соответствие число ${\displaystyle c=z+pq}$, где ${\displaystyle q}$ выбирается произвольно. Таким образом, ${\displaystyle c=2r+m+(2k+1)*q}$. Легко видеть, что ${\displaystyle c\ mod\ 2=(m+q)\ mod\ 2}$, значит, злоумышленник сможет определить только четность выхода шифрования.

Пусть известны зашифрованное число ${\displaystyle c}$ и секрет ${\displaystyle p}$, тогда процесс расшифрования данных должен содержать следующие действия:

1.Расшифрование с использованием секретного параметра ${\displaystyle p}$: ${\displaystyle r=c\ mod\ p=(z+pq)\ mod\ p=z\ mod\ p+(pq)\ mod\ p}$, где ${\displaystyle r=c\ mod\ p}$ называется шумом и ${\displaystyle z\in \left(-{p \over 2},{p \over 2}\right)}$.

2.Получение исходного зашифрованного бита: ${\displaystyle m=r\ mod\ 2}$

Пусть есть два бита ${\displaystyle m_{1},m_{2}\in \mathbb {Z} _{2}}$, и им в соответствие поставлена пара чисел ${\displaystyle z_{1}=2r_{1}+m_{1}}$ и ${\displaystyle z_{2}=2r_{2}+m_{2}}$. Пусть взят секретный параметр ${\displaystyle p=2k+1}$ и произведено шифрование данных: ${\displaystyle c_{1}=z_{1}+pq_{1}}$ и ${\displaystyle c_{2}=z_{2}+pq_{2}}$.

Вычисляется сумма этих чисел:

${\displaystyle c_{1}+c_{2}=z_{1}+pq_{1}+z_{2}+pq_{2}=z_{1}+z_{2}+p(q_{1}+q_{2})=2r_{1}+m_{1}+2r_{2}+m_{2}+(2k+1)(q_{1}+q_{2})}$

Для суммы этих чисел расшифрованным сообщением будет сумма исходных бит ${\displaystyle m_{1},m_{2}:((c_{1}+c_{2})\ mod\ p)\ mod\ 2=(2(r_{1}+r_{2})+m_{1}+m_{2})\ mod\ 2=m_{1}+m_{2}}$.

Но, не зная ${\displaystyle p}$, расшифровать данные не представляется возможным: ${\displaystyle ((c_{1}+c_{2})\ mod\ p)\ mod\ 2=m_{1}+m_{2}+q_{1}+q_{2}}$.

Аналогично проверяется операция умножения:

${\displaystyle c_{1}c_{2}=(z_{1}+pq_{1})(z_{2}+pq_{2})=z_{1}z_{2}+p(z_{1}q_{2}+z_{2}q_{1})+p^{2}q_{1}q_{2}=(2r_{1}+m_{1})(2r_{2}+m_{2})+}$

${\displaystyle +(2k+1)((2r_{1}+m_{1})q_{2}+(2r_{2}+m_{2})q_{1})=4r_{1}r_{2}+2(r_{1}m_{2}+r_{2}m_{1})+m_{1}m_{2}+}$

${\displaystyle 2k(2r_{1}q_{2}+m_{1}q_{2}+2r_{2}q_{1}+m_{2}q_{1})+2r_{1}q_{2}+m_{1}q_{2}+2r_{2}q_{1}+m_{2}q_{1}}$

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

${\displaystyle ((c_{1}c_{2})\ mod\ p)\ mod\ 2=(4r_{1}r_{2}+2(r_{1}m_{2}+r_{2}m_{1})+m_{1}m_{2})\ mod\ 2=m_{1}m_{2}}$.

Использование данной полностью гомоморфной схемы шифрования в практических целях на данный момент не представляется возможным, так как в результате производимых вычислений накапливаемая ошибка ${\displaystyle r}$ быстро достигает достаточно больших значений^[36]. Возможна даже ситуация, при которой правильно расшифровать данные не удастся вовсе. Это произойдет в случае, если значение ошибки ${\displaystyle r}$ превысит значение ${\displaystyle p}$. В попытках избежать столкновения с такой проблемой Гентри был разработан механизм самокоррекции шифротекстов (англ. bootstrapping), который в силу своей непрактичности из-за слишком быстрого роста объема шифротекста не нашел широкого применения. Решить данную проблему возможно, но для достижения поставленной задачи необходимо разработать более сложные алгоритмы вычислений либо ограничить количество операций над данными.^[36]

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

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

Также по данным международной исследовательской компании IDC, занимающейся изучением мирового рынка информационных технологий и телекоммуникаций, многие компании с недоверием относятся к облачным технологиям, связывая с ними, в первую очередь, большие проблемы по части безопасности хранимых данных. А независимая исследовательская компания Portio Research опубликовала данные, согласно которым 68% руководителей различных европейских IT - компаний не доверяют подобным сервисам. Так, например, руководитель компании G Data Security Labs Ральф Бенцмюллер высказался об облачных сервисах следующим образом: «Если вы не хотите, чтобы ваши данные стали достоянием общественности, не храните их в облачных хранилищах». Поэтому вопрос создания защищенного облачного хранилища с использованием полностью гомоморфной схемы шифрования данных в настоящее время стоит довольно остро^[37].

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