Понимание вычислений, сохраняющих конфиденциальность
10 января 2024 г.:::информация Этот документ доступен на arxiv по лицензии CC 4.0.
Авторы:
(1) Тарик Бонтекое, Гронингенский университет;
(2) Димка Карастоянова, Гронингенский университет;
(3) Фатих Туркмен, Гронингенский университет.
:::
Таблица ссылок
Доказательства с нулевым разглашением и проверяемые вычисления
Вычисления, обеспечивающие конфиденциальность
Требования: точка зрения приложения
Проверяемые вычисления с сохранением конфиденциальности
Открытые проблемы и будущие направления
4. Вычисления, сохраняющие конфиденциальность
Существуют различные PET, которые можно использовать для создания решений для вычислений, сохраняющих конфиденциальность. Два из них специально подходят для наших условий: MPC и HE. Оба являются хорошо зарекомендовавшими себя PET, обеспечивающими гибкость и надежные гарантии конфиденциальности, что делает их отличными строительными блоками для проверяемых вычислений, сохраняющих конфиденциальность. Ниже мы обсудим оба компонента и дадим интуитивно понятный ответ на RQ1.
4.1. Безопасные многосторонние вычисления
MPC — это набор методов, которые позволяют выполнять совместные вычисления над распределенными данными, сохраняя при этом конфиденциальность всех входных данных и не раскрывая ничего, кроме результатов вычислений. Как правило, в вычислении MPC участвуют n сторон, и любая участвующая сторона вносит свой вклад в сотрудничество, внося свои соответствующие частные вклады. Все n сторон выполняют интерактивный протокол для вычисления выходных данных совместной функции на основе своих частных входных данных.
Поэтому протокол MPC должен быть устойчив к тому факту, что некоторые участвующие стороны могут быть повреждены противником. Как обсуждалось в разделе 2.2, существуют разные модели безопасности. Однако любой безопасный протокол MPC должен, по крайней мере, удовлетворять следующим (неформальным) требованиям [14], учитывая ограничения используемой состязательной модели:
• Конфиденциальность ввода: ни одна сторона не должна узнавать ничего, кроме назначенного ей выхода функции. В частности, ни одна сторона не должна узнавать что-либо о вкладах других сторон, кроме того, что можно получить из назначенных ей результатов.
• Корректность: каждая сторона, получающая (частичный) выходной сигнал, получает значение, правильное с точки зрения спецификации протокола и входных данных.
• Независимость исходных данных. Коррумпированные стороны должны выбирать свои исходные данные независимо от частных вкладов честных сторон.
Существует несколько способов создания протокола или структуры MPC. Ниже мы представляем две наиболее распространенные конструкции: совместное использование секрета и искаженные схемы.
Передача секретов. При совместном использовании секретов личные данные распределяются между несколькими сторонами. Информация разделена таким образом, что только заранее определенные группы сторон могут восстановить полную информацию, в то время как другие (под)наборы не могут вывести даже частичную информацию. Большинство схем совместного использования секрета делят секрет между n сторонами таким образом, что только подмножества с t или более сторонами могут восстановить его. Такая схема называется схемой t-из-n-порогов.
Наконец, отметим, что доли из LSSS можно эффективно умножать, используя так называемые тройки умножения Бивера [30]. Эти триплеты не зависят от ввода/функции и, таким образом, могут быть сгенерированы на так называемой автономной фазе предварительной обработки. Используя этот подход, оставшиеся вычисления могут быть выполнены в очень эффективном режиме онлайн.
Во многих популярных современных схемах обмена секретами используются линейные доли в сочетании с тройками Beaver или передачей без внимания. Примерами схем, использующих обмен секретами, являются: обмен секретами Шамира (SSS) [31] или, на онлайн-фазе, SPDZ [32] и MASCOT [33]. Актуальный обзор существующих схем с реализациями можно найти в библиотеке MP-SPDZ [34].
Искаженные схемы. Искаженные схемы (GC) Яо [35] — это способ дать возможность двум недоверчивым сторонам безопасно оценить функцию на своих частных входных данных. Для этого требуется, чтобы базовая функция была выражена в виде логической схемы, состоящей из вентилей 1-выход-2-входа.
Одна сторона, искажитель, генерирует искаженную версию всей схемы, искажая отдельные элементы. В исходной реализации вентиль искажается путем присвоения уникальной случайной метки возможным значениям (истина, ложь) каждого входного провода и двойного шифрования четырех возможных выходных значений под соответствующими входными метками. Устройство искажения случайным образом переставляет зашифрованные выходные данные и передает их оценщику вместе со случайными метками, соответствующими частным входам устройства искажения. Затем оценщик участвует в протоколе забывчивой передачи (OT) [36] для получения меток, соответствующих его частным входным данным, не раскрывая их.
Получив обе входные метки, оценщик может правильно расшифровать ровно один из искаженных выходных данных, тем самым получив истинный выходной бит(ы). Когда выход вентиля используется в качестве входных данных для другого вентиля, истинным выходом будет не бит, а новая случайная метка, которая используется при расшифровке этого другого вентиля. Альтернативной конструкцией GC Яо является структура BMR [37]. Реализации обеих и других платформ можно найти, например, в MP-SPDZ [34], ABY [38] или ABY 3 [39].
Вопрос 1a: Зачем нам проверять MPC? Большинство платформ MPC применяются в полностью децентрализованной среде, где все стороны общаются друг с другом напрямую. Многие схемы MPC гарантируют конфиденциальность для конкретной модели угроз при условии наличия определенного количества честных сторон, от строгого большинства до одной. Поэтому можно сказать, что корректность — во многом решаемая проблема.
Однако ничто из вышеперечисленного не учитывает вариант использования, в котором стороны, не участвовавшие в вычислениях, хотят проверить результаты. В этой ситуации результаты могут быть неверными, если все вычислительные стороны вступают в сговор. Таким образом, схемы не поддаются публичной проверке или публичному аудиту [40], что делает результаты ненадежными для внешних сторон.
Еще одна проблема, связанная с (публичной) проверяемостью, которую часто упускают из виду, — это проверка подлинности данных. Правильность результатов часто гарантируется только при условии, что входные данные предоставлены честно. Это особенно важно, когда входные данные сторон должны быть одинаковыми в ходе нескольких вычислений, например, для воспроизводимости, или когда входные данные должны быть аутентифицированы, например, подписаны экспертным органом. На практике как внешние, так и вычислительные стороны, желающие получить достоверно правильные результаты, потребуют проверки подлинности вычислений и данных.
4.2. Гомоморфное шифрование
HE — это термин, используемый для обозначения набора (асимметричных) схем шифрования, которые позволяют пользователям выполнять операции с зашифрованными данными без предварительного их расшифрования. Более формально, следуя [41], схема HE описывается четырьмя (вероятностными) алгоритмами с полиномиальным временем (KeyGen, Enc, Dec, Eval):
• KeyGen(1κ) → (sk, pk, evk) — алгоритм генерации ключей. Он принимает унарное представление параметра безопасности κ в качестве входных данных и выводит секретный ключ дешифрования sk, общедоступный ключ шифрования pk и общедоступный ключ оценки evk.
Хотя существуют разные способы представления функции f в схемах HE, большинство конструкций предпочитают перевод в арифметическую схему Cf вместо M. Примечательно, что не все схемы гомоморфного шифрования можно использовать для вычисления произвольных арифметических схем. Поэтому мы выделяем, следуя [42], несколько типов гомоморфных схем в порядке возрастания вычислительных возможностей.
Частично гомоморфное шифрование. PHE — это тип гомоморфного шифрования, который является гомоморфным только аддитивно или только мультипликативно, что означает, что оно может обрабатывать только арифметические схемы, состоящие исключительно из элементов сложения и соответственно умножения. В целом частично гомоморфные схемы имеют наименьшие вычислительные затраты и стабильный размер зашифрованного текста.
Несколько гомоморфное шифрование. Конструкции SWHE могут обрабатывать арифметические схемы, состоящие как из элементов сложения, так и из элементов умножения. Однако схемы, которые можно оценить, могут быть ограничены в количестве операций (любого типа), например схема, которая может оценивать только схемы с максимальной глубиной умножения 2. Более того, для SWHE не существует требования, предотвращающего экспоненциальное увеличение размера зашифрованного текста..
Уровневое гомоморфное шифрование. LHE напоминает SWHE тем, что может оценивать схемы, глубина которых ограничена d. Однако, поскольку d предоставляется в качестве входных данных для KeyGen, параметры схемы могут быть функцией d. Кроме того, длина вывода зашифрованного текста алгоритма Eval может не зависеть от глубины d, а это означает, что зашифрованные тексты не разрушаются экспоненциально. Обратите внимание, что размеры ключей могут по-прежнему зависеть от глубины d и могут стать непрактично большими.
Полностью гомоморфное шифрование. Схемы FHE могут обрабатывать произвольные арифметические схемы, при этом параметры схем не зависят от каких-либо свойств схемы. Эта общность часто достигается за счет дорогостоящих алгоритмов начальной загрузки после определенного количества умножений [43].
RQ1b: Зачем нам проверять HE? HE часто используется в условиях, когда один (облачный) сервер или центральный объект выполняет большую часть вычислений, например, в сценарии аутсорсинга. Часто наблюдаемый сценарий заключается в том, что все владельцы данных используют распределенный или пороговый протокол генерации ключей для получения пары открытого и закрытого ключей, где закрытый ключ является общим для всех владельцев данных [44], [45]. Для выполнения вычислений все владельцы данных шифруют свои данные одним и тем же открытым ключом и позволяют центральному серверу выполнять фактические вычисления над полученными зашифрованными текстами. Из-за высоких вычислительных затрат на операции с гомоморфно зашифрованными данными часто предпочитают иметь один центральный вычислительный сервер с достаточными вычислительными ресурсами.
В большинстве случаев предполагается, что все стороны ведут себя получестно. Однако это предположение нереалистично в большинстве реальных сценариев и поднимает серьезные проблемы с целостностью и проверяемостью. Проблемы с целостностью возникают из-за возможности атак с восстановлением ключей [46], [47], [48], тогда как проблемы с проверяемостью возникают из-за того, что сервер может отклониться от запрошенных вычислений.
Другой вопрос, касающийся проверяемости, заключается в том, могут ли внешние стороны проверить результаты вычислений, использующих HE. Эти гарантии могут быть гарантированы в тех случаях, когда требуется внешний аудит или когда результаты представляют интерес для более широкого сообщества. Таким образом, поддающиеся проверке решения должны обеспечивать гарантии даже в том случае, если все владельцы данных и центральный вычислительный сервер (серверы) находятся в сговоре. Помимо этого, внешние стороны могут также потребовать гарантий целостности и подлинности входных данных, что, как правило, не учитывается в существующих работах.
Оригинал