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

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

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

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

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

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

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

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

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

Первой реализацией полностью гомоморфного шифрования была схема Гентри-Халеви реализованная на основе вышеуказанной схемы Гентри.[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]

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

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]

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

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

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

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