Гомоморфное шифрование

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

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

История

Понятие «гомоморфное шифрование» впервые сформировано в 1978 году Рональдом Ривестом, Леонардом Адлеманом и Майклом Дертузосом — авторами алгоритма RSA через год после разработки алгоритма. Они предположили возможность выполнения произвольных операций над зашифрованными данными без их расшифрования.

В то время попытки создания полностью гомоморфной криптосистемы не были успешны. Например, в 1982 году Шафи Гольдвассер и Сильвио Микали предложили систему шифрования, гомоморфную относительно умножения и способную зашифровать всего лишь один бит. Ещё одна криптосистема, гомоморфная относительно умножения, была предложена в 1999 году Паскалем Пэйе.

В 2005 году Дэн Боне, Ю Чжин Го и Коби Ниссим предложили криптосистему, которая основывалась на использовании билинейных спариваний на эллиптических кривых, позволяла выполнять неограниченное количество операций сложения и одну операцию умножения.

Задача создания криптосистемы, гомоморфной относительно и операции сложения, и операции умножения, оставалась нерешённой свыше 30 лет.

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

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

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

Общий вид гомоморфного шифрования

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

Пусть $k$ — ключ для шифрования, $t$ — подлежащий шифрованию открытый текст (сообщение), $E(k,t)$ — выполняющая шифрование функция.

Функция $E$ называется гомоморфной относительно операции «$*$» (сложения или умножения) над открытыми текстами (сообщениями) $t_{1}$ и $t_{2}$, если существует эффективный алгоритм $M$ (требующий полиномиального числа ресурсов и работающий за полиномиальное время), который, получив на вход любую пару шифрованных текстов вида $E(k,t_{1})$ и $E(k,t_{2})$, выдаёт шифрованный текст (шифротекст, криптограмму) $c=M(E(k,t_{1}),E(k,t_{2}))$ такой, что при расшифровании $c$ будет получен открытый текст $t_{1}*t_{2}$.

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

Пусть для данной функции шифрования $E$ и операции «$*_{1}$» над открытыми текстами $t_{1}$ и $t_{2}$ существует операция «$*_{2}$» над шифрованными текстами, такая, что из шифрованного текста $c=E(k,t_{1})*_{2}E(k,t_{2})$ при его расшифровании извлекается открытый текст $t_{1}*_{1}t_{2}$. При этом требуется, чтобы по заданным $c$, $E(k,t_{1})$, $E(k,t_{2})$, но при неизвестном ключе $k$, было бы невозможно эффективно проверить, что шифрованный текст $c$ получен из $E(k,t_{1})$ и $E(k,t_{2})$.

Любую стандартную систему шифрования можно описать, описав три операции: операцию генерация ключей (keyGen), операцию шифрования (encypt) и операцию расшифрования (decrypt).

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

1. генерация ключей — генерирование клиентом пары связанных ключей: открытого ключа (public key) $k_{p}$ для функции шифрования $E()$ открытого текста и секретного ключа (secret key) $k_{s}$ для функции расшифрования $D()$ зашифрованного текста;
2. шифрование — шифрование клиентом открытого текста (plain text) $PT_{in}$ с использованием открытого ключа $k_{p}$, то есть вычисление шифрованного текста (cipher text) $CT_{in}=E(PT_{in})$ и отправка его на сервер;
3. вычисление — получение сервером функции $F()$, использование её для выполнения вычислений над шифрованным текстом $CT_{res}=F(CT_{in})$ и отправка результата клиенту;
4. расшифрование — расшифрование клиентом полученного от сервера значения с использованием секретного ключа $k_{s}$, то есть вычисление $PT_{res}=D(CT_{res})$.

Таким образом, открытые тексты $PT_{in}$ и $PT_{res}$ доступны только клиенту, а сервер работает с шифрованными текстами $CT_{in}$ и $CT_{res}$.

Пусть $E$ — функция шифрования; $D$ — функция расшифрования; $t_{1}$ и $t_{2}$ — открытые тексты; символы «$\otimes$» и «$\oplus$» обозначают операции умножения и сложения над шифрованными текстами, соответствующие операциям умножения и сложения над открытыми текстами.

Система шифрования является гомоморфной относительно операции умножения (обладает мультипликативными гомоморфными свойствами), если ${D(E(t_{1})\otimes E(t_{2}))=t_{1}\cdot t_{2}}.$

Система шифрования является гомоморфной относительно операции сложения (обладает аддитивными гомоморфными свойствами), если ${D(E(t_{1})\oplus E(t_{2}))=t_{1}+t_{2}}.$

Система шифрования является гомоморфной относительно операций умножения и сложения, то есть, полностью гомоморфной (обладает и мультипликативными, и аддитивными гомоморфными свойствами), если ${D(E(m_{1})\otimes E(m_{2}))=m_{1}\cdot m_{2}},$ ${D(E(m_{1})\oplus E(m_{2}))=m_{1}+m_{2}}.$

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

Области применения

Облачные вычисления

Гомоморфное шифрование открывает новые возможности по сохранению целостности, доступности и конфиденциальности данных при их обработке в облачных системах. В облачных вычислениях, где производительность является главным приоритетом, следует применять разные алгоритмы, каждый из которых лучше всего справляется с поставленной задачей. Например, для операций умножения зашифрованных данных целесообразно использовать алгоритм RSA или алгоритм Эль-Гамаля, а для сложения — алгоритм Пэйе. В случае применения полностью гомоморфной системы шифрования следует ограничивать количество операций, которые можно производить над данными, так как в результате производимых вычислений накапливается некоторая ошибка $r$. Если значение ошибки $r$ превысит значение секретного параметра $p$, возможна ситуация, при которой не удастся правильно расшифровать данные.

Электронное голосование

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

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

Рассмотрим пример того, как данный подход может быть реализован.

Пусть имеется набор из $n$ кандидатов, из которых формируется включаемый в бюллетень список. Инициатор голосования обладает криптосистемой, гомоморфной относительно операции сложения, распространяет среди участников тайного голосования открытый ключ системы гомоморфного шифрования $pk$ и бюллетень как вектор ${(p_{1},p_{2},\dots ,p_{i},\dots ,p_{n})},$ где $p_{i}$ — фамилия $i$-го кандидата. Каждый из избирателей составляет вектор предпочтений ${(v_{1},v_{2},\dots ,v_{i},\dots ,v_{n})},$ где ${v\in \{0,1\}}.$ После этого с помощью открытого ключа $pk$ каждый из избирателей поэлементно шифрует вектор и отправляет инициатору голосования. Для подведения итогов голосования тот производит вычисления над соответствующими элементами полученных векторов предпочтений и производит расшифрование с помощью секретного ключа $sk$. Так как криптосистема гомоморфна относительно операции сложения, индексы наибольших элементов результирующего вектора и будут индексами победивших кандидатов.

Защищённый поиск информации

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

Пусть ${v_{1},v_{2},\dots ,v_{i},\dots ,v_{n}}$ — индекс записи, которую нужно извлечь; ${v_{i}\in \{0,1\}}$; ${c_{1},c_{2},\dots ,c_{i},\dots ,c_{2^{n}}}$ — все проиндексированные записи из базы данных.

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

$F(v_{1},v_{2},\dots ,v_{i},\dots ,v_{n};c_{1},c_{2},\dots ,c_{i},\dots ,c_{2^{n}})=$

$=c_{1}\cdot ((v_{1}\oplus 1)\otimes (v_{2}\oplus 1)\otimes \dots \otimes (v_{n}\oplus 1))+$

$+c_{2}\cdot ((v_{1}\oplus 1)\otimes (v_{2}\oplus 1)\otimes \dots \otimes (v_{n-1}\oplus 1)\otimes v_{n})+$

$+c_{3}\cdot ((v_{1}\oplus 1)\otimes (v_{2}\oplus 1)\otimes \dots \otimes v_{n-1}\otimes (v_{n}\oplus 1))+$

$+\dots +$

$+c_{2^{n}}\cdot (v_{1}\otimes v_{2}\otimes \dots \otimes v_{n}).$

Если все $c_{i}$ зашифрованы с помощью гомоморфной криптосистемы, $F$ можно вычислить гомоморфно над шифрованными текстами. Для этого клиенту достаточно побитово зашифровать индекс ${v_{1},v_{2},\dots ,v_{i},\dots ,v_{n}}$ нужной ему записи и отправить на сервер. Результат гомоморфного вычисления функции $F$ над шифрованными текстами будет искомым шифрованным значением записи $c_{i}$, запрашиваемой клиентом. Очевидно, что криптосистема должна обладать как мультипликативными, так и аддитивными гомоморфными свойствами.

Защита беспроводных децентрализованных сетей связи

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

Аутсорсинговые услуги для смарт-карт

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

Системы с обратной связью

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

Обфускация для защиты программных продуктов

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

Частично гомоморфные системы

Частично гомоморфные криптосистемы — это такие криптосистемы, которые гомоморфны относительно только одной операции — либо операции сложения, либо операции умножения. В приведённых ниже примерах выражение $E(t)$ обозначает использование функции шифрования $E$ для шифрования открытого текста (сообщения) $t$.

Криптосистема RSA

Криптосистема RSA является криптографической схемой с открытым ключом, гомоморфной по умножению. Пусть $n$ — модуль RSA, $t$ — открытый текст, $k$ — открытый ключ (для шифрования открытого текста). Функция шифрования имеет вид $E(t)=t^{k}\;{\bmod {\ }}n$. Покажем гомоморфизм по умножению: $E(t_{1})*E(t_{2})=t_{1}^{k}*t_{2}^{k}\;{\bmod {\ }}n=(t_{1}t_{2})^{k}\;{\bmod {\ }}n=E(t_{1}t_{2}).$

Криптосистема Эль-Гамаля

Криптосистема Эль-Гамаля является альтернативой криптосистемы RSA и при равном значении ключа обеспечивает ту же криптостойкость. Эль-Гамаль усовершенствовал алгоритм Диффи — Хеллмана и получил алгоритмы для шифрования и для обеспечения аутентификации. Криптосистема является криптосистемой вероятностного шифрования. Её функция шифрования гомоморфна относительно операции умножения открытых текстов: криптограмма произведения может быть вычислена как произведение (попарное) криптограмм сомножителей. Пусть $E$ — функция шифрования; $t_{1}$ и $t_{2}$ — открытые тексты. Если $E(y,g,\{r_{1}\},t_{1})=(y^{r_{1}}t_{1},g^{r_{1}})$ и $E(y,g,\{r_{2}\},t_{2})=(y^{r_{2}}t_{2},g^{r_{2}}),$ то $E(y,g,\{r_{1},r_{2}\},t_{1}t_{2})$ можно получить в виде $(y^{r_{1}}y^{r_{2}}t_{1}t_{2},g^{r_{1}}g^{r_{2}})$.

Криптосистема Гольдвассер — Микали

В криптосистеме Гольдвассер — Микали, если открытым ключом является модуль $m$, то функция шифрования $E$ бита $b$ есть $E(b)=x^{b}r^{2}\;{\bmod {\ }}m$ для случайного элемента $r\in \{0,\dots ,m-1\}$. Тогда эта криптосистема гомоморфна для операции умножения: $E(b_{1})\cdot E(b_{2})=x^{b_{1}}r_{1}^{2}x^{b_{2}}r_{2}^{2}=x^{b_{1}+b_{2}}(r_{1}r_{2})^{2}=E(b_{1}\oplus b_{2}),$ где символом «$\oplus$» обозначена операция сложение по модулю 2.

Криптосистема Пэйе

В криптосистеме Пэйе, если открытый ключ является модулем $m$ и $g$ — случайное число, то функция шифрования $E$ сообщения (открытого текста) $t$ представлена в виде $E(t)=g^{t}r^{m}\;{\bmod {\;}}m^{2}$ для случайной величины $r\in \{0,\ldots ,m-1\}$. Тогда гомоморфность по сложению доказывается следующим образом:

$E(t_{1})\cdot E(t_{2})=(g^{t_{1}}r_{1}^{m})\cdot (g^{t_{2}}r_{2}^{m})\;{\bmod {\;}}m^{2}=g^{t_{1}+t_{2}}(r_{1}r_{2})^{m}\;{\bmod {\;}}m^{2}=E(t_{1}+t_{2}).$

Криптосистема Бенало

В криптосистеме Бенало, если открытый ключ является модулем $m$, тогда функция шифрования открытого текста $t$ представлена в виде $E(t)=g^{t}r^{c}\;{\bmod {\;}}m$ для случайного $r\in \{0,\ldots ,m-1\}$. Тогда гомоморфность по сложению доказывается следующим образом:

$E(t_{1})\cdot E(t_{2})=(g^{t_{1}}r_{1}^{c})\cdot (g^{t_{2}}r_{2}^{c})\;{\bmod {\;}}m=g^{t_{1}+t_{2}}(r_{1}r_{2})^{c}\;{\bmod {\;}}m=E(t_{1}+t_{2}).$

Другие частично гомоморфные криптосистемы

• Криптосистема Окамото — Утиямы
• Криптосистема Накаша — Штерна
• Криптосистема Дамгорда — Юрика
• Криптосистема Боне — Го — Ниссима

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

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

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

Проблемы с производительностью и их решение

Одной из существенных проблем известных полностью гомоморфных криптосистем является их крайне низкая производительность. В настоящее время существует два основных пути повышения производительности: использование «ограниченного гомоморфизма» (англ. leveled fully homomorphic encryption) и использование так называемого «метода упаковки шифротекстов». Первый подразумевает криптосистему, которая может выполнять операции сложения и умножения, но в ограниченном количестве. Суть второго в том, что в один шифротекст записывается сразу несколько открытых текстов, и при этом в процессе одиночной операции такого пакетного шифротекста происходит одновременная обработка всех входящих в него шифротекстов.

См. также

• Алгоритм слепого индексирования

Литература

• Гомоморфное шифрование Н. П. Варновский, А. В. Шокуров //Труды института системного программирования. Том 12. (Под ред. В. П. Иванникова) — М.: ИСП РАН. — 2006. С. 27-36.
• Мао В. Современная криптография: Теория и практика / пер. Д. А. Клюшина — М.: Вильямс, 2005. — 768 с. — ISBN 978-5-8459-0847-6.
• Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. 11.5.2 The ElGamal signature scheme // Handbook of applied cryptography.
• D. S. Maimut, A. Patrascu, E. Simion Homomorphic encryption schemes and applications for secure digital world // JMEDS. — 2012. — № 4.
• M. van Dijk, C. Gentry, S. Halevi, and V. Vaikuntanathan Fully homomorphic encryption over the integers // In Proc. of Eurocrypt, volume 6110 of LNCS. — 2010. — 28 p.
• А. О. Жиров, О. В. Жирова, С. Ф. Кренделев Безопасные облачные вычисления с помощью гомоморфной криптографии.
• А. И. Трубей Гомоморфное шифрование: безопасность облачных вычислений и другие приложения (обзор).

Ссылки

• Философия криптографии: возможности гомоморфизма // Cnews. 30 июня 2009 года.