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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

История[править | править код]

В 1978 году, всего спустя год после разработки известного алгоритма с открытым ключом RSA, его авторами Рональдом Ривестом, Леонардом Адлеманом, а также Майклом Дертузосом впервые было сформировано такое понятие, как гомоморфное шифрование[1].

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

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

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

Общий вид гомоморфного шифрования[править | править код]

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

Пусть  — функция шифрования, где  — ключ шифрования, а  — открытый текст.

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

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

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

Любую стандартную систему шифрования можно описать в виде трех операций: генерации ключей (KeyGen), шифрования (Encypt) и расшифрования (Decrypt)[4].

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

  1. Генерация ключей: клиент генерирует открытый ключ (public key) и секретный ключ (secret key) для шифрования открытого текста;
  2. Шифрование: используя секретный ключ , клиент шифрует открытый текст (plain text), создает и вместе с открытым ключом отправляет шифрованный текст (cipher text) на сервер;
  3. Вычисление: сервер получает функцию для проведения вычислений над шифрованным текстом и выполняет их в соответствии с требованиями данной функции, используя ;
  4. Расшифрование: для получения искомого результата значение , полученное в ходе вычислений, расшифровывается клиентом с использованием своего секретного ключа .

Система шифрования является гомоморфной относительно операции умножения, если

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

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

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

Области применения[править | править код]

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

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

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

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

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

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

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

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

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

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

.

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

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

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

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

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

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

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

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

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

Частично гомоморфные системы[править | править код]

Частично гомоморфные криптосистемы — это такие криптосистемы, которые гомоморфны относительно только одной операции (или сложения, или умножения)[7].

Криптосистема RSA[править | править код]

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

Криптосистема Эль-Гамаля[править | править код]

Криптосистема Эль-Гамаля является альтернативой алгоритму RSA и при равном значении ключа обеспечивает ту же криптостойкость. Эль-Гамаль усовершенствовал алгоритм Диффи — Хеллмана и получил алгоритмы для шифрования и для обеспечения аутентификации. Является криптосистемой вероятностного шифрования. Её функция шифрования гомоморфна относительно операции умножения открытых текстов: криптограмма произведения может быть вычислена как произведение (попарное) криптограмм сомножителей. Если и ,то можно получить в виде .

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

В криптосистеме Гольдвассер — Микали если открытым ключом является модуль , тогда функция шифрования бита : для случайного элемента . Тогда эта криптосистема гомоморфна для операции умножения: , где есть сложение по модулю 2.

Криптосистема Пэйе[править | править код]

В криптосистеме Пэйе, если открытый ключ является модулем и случайное число , тогда функция шифрования от сообщения представлена в виде , для случайной величины . Тогда гомоморфное свойство:

.

Криптосистема Бенало[править | править код]

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

.

Другие частично гомоморфные криптосистемы[править | править код]

Полностью гомоморфное шифрование[править | править код]

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

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

Одной из существенных проблем известных полностью гомоморфных криптосистем является их крайне низкая производительность. В настоящее время существует два основных пути её повышения: использование «ограниченного гомоморфизма» (Leveled Fully Homomorphic Encryption)[11] и т. н. «метод упаковки шифртекстов»[12]. Первый подразумевает криптосистему, которая может выполнять операции двух видов (сложения и умножение), но в ограниченном количестве. Суть второго в том, что в один шифртекст записывается сразу несколько открытых текстов, и при этом в процессе одиночной операции такого пакетного шифртекста происходит одновременная обработка всех входящих в него шифртекстов.

Примечания[править | править код]

  1. Ronald L. Rivest, Len Adleman, Michael L. Dertouzos. On Data Banks And Privacy Homomorphisms (англ.). Academic Press (1978). Архивировано 25 мая 2013 года.
  2. Dan Boneh, Eu-Jin Goh, Kobbi Nissim. Evaluating 2-DNF formulas on ciphertexts (англ.). Springer-Verlag (2005). Архивировано 25 мая 2013 года.
  3. Варновский, Н. П. Гомоморфное шифрование / Н. П. Варновский, А.В Шокуров // Труды Ин-та системного программирования РАН. — 2006.
  4. Survey of various homomorphic encryption algorithms and schemes / P.V. Parmar [et al.] // Intern. J. of Computer Applications. — 2014. — Vol. 91, no. 8.
  5. Шенец, Н. Н. Модулярное разделение секрета и системы электронного голосования / Н. Н. Шенец // Вестник БГУ. Сер. 1. — 2011. — № 1.
  6. Габидулин, Э. М. Защита информации в телекоммуникационных сетях / Э. М. Габидулин, Н. И. Пилипчук, О. В. Трушина // Труды МФТИ. — 2013. — Т. 5, № 3.
  7. Описанных примерах обозначение является функцией шифрования от сообщения
  8. Daniele Micciancio. A First Glimpse of Cryptography's Holy Grail (англ.). Association for Computing Machinery (1 March 2010). Архивировано 24 мая 2013 года.
  9. Craig Stuntz. What is Homomorphic Encryption, and Why Should I Care? (англ.) (18 March 2010). Архивировано 24 мая 2013 года.
  10. Ron Rivest. Lecture Notes 15: Voting, Homomorphic Encryption (англ.) (29 October 2002). Архивировано 24 мая 2013 года.
  11. Brakerski Z., Gentry C., Vaikuntanathan V. (Leveled) fully homomorphic encryption without bootstrapping // Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. — 2012. — С. 309—325.
  12. Буртыка Ф.Б. Пакетное симметричное полностью гомоморфное шифрование на основе матричных полиномов. // Труды Института Системного программирования: Том 26. — 2014. — № 5. — С. 99—115.

Литература[править | править код]

Ссылки[править | править код]