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

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

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

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

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

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

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

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

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

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

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

Функция называется гомоморфной относительно операции «» (сложения или умножения) над открытыми текстами (сообщениями) и , если существует эффективный алгоритм (требующий полиномиального числа ресурсов и работающий за полиномиальное время), который, получив на вход любую пару шифрованных текстов вида и , выдаёт шифрованный текст (шифротекст, криптограмму) такой, что при расшифровании будет получен открытый текст Варновский, Н. П. Гомоморфное шифрование / Н. П. Варновский, А. В. Шокуров // Труды института системного программирования РАН. — 2006..

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

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

Любую стандартную систему шифрования можно описать через три операции: операцию генерация ключей (), операцию шифрования () и операцию расшифрования ()Survey of various homomorphic encryption algorithms and schemes / P.V. Parmar [et al.] // Intern. J. of Computer Applications. — 2014. — Vol. 91, no. 8..

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

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

Таким образом, открытые тексты и доступны только клиенту, а сервер работает с шифрованными текстами и .

Пусть  — функция шифрования;  — функция расшифрования; и  — открытые тексты; символы «» и «» обозначают операции умножения и сложения над шифрованными текстами, соответствующие операциям умножения и сложения над открытыми текстами.

Система шифрования является гомоморфной относительно операции умножения (обладает мультипликативными гомоморфными свойствами), если

Система шифрования является гомоморфной относительно операции сложения (обладает аддитивными гомоморфными свойствами), если

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

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

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

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

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

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

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

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

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

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

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

Пусть  — индекс записи, которую нужно извлечь; ;  — все проиндексированные записи из базы данных.

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

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

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

Беспроводные децентрализованные самоорганизующиеся сети (MANET) — это сети, состоящие из мобильных устройств. Каждое такое устройство может независимо передвигаться в любых направлениях и, как следствие, часто разрывать и устанавливать соединения с соседними устройствами. Одной из основных проблем при построении MANET является обеспечение безопасности передаваемых данных. Для решения этой проблемы может применяться гомоморфное шифрование, которое встраивается в протоколы маршрутизации для повышения безопасности. В этом случае операции над шифрованными текстами могут безопасно выполняться промежуточными узлами. В частности, для нахождения оптимального пути между двумя узлами необходимо осуществлять линейные операции над зашифрованными данными без их расшифрования. Наличие гомоморфного шифрования не позволяет злоумышленнику найти связь между сообщениями, входящими в узел, и сообщениями, выходящими из узла. Поэтому невозможно отследить путь передачи сообщения с помощью анализа трафикаГабидулин, Э. М. Защита информации в телекоммуникационных сетях / Э. М. Габидулин, Н. И. Пилипчук, О. В. Трушина // Труды МФТИ. — 2013. — Т. 5, № 3..

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