Проверяемость вычисления (или проверяется вычисление или проверено вычисления ) позволяет компьютеру , чтобы разгрузить на вычисление некоторой функции, для других , возможно , ненадежных клиентов , сохраняя при этом проверяемые результаты. Остальные клиенты оценивают функцию и возвращают результат с доказательством того, что вычисление функции было выполнено правильно. Появление этого понятия произошло в результате все более распространенного явления " аутсорсинга " вычислений ненадежным пользователям в таких проектах, как SETI @ home.а также растущему желанию слабых клиентов передать вычислительные задачи более мощной вычислительной службе, такой как облачные вычисления . Эта концепция восходит к работе Бабая и др. [1] и изучалась под различными терминами, включая «проверку вычислений» (Бабай и др.), «Делегирование вычислений», [2] «сертифицированные вычисления», [3 ] и проверяемые вычисления. Сам термин « проверяемые вычисления » был формализован Розарио Дженнаро, Крейгом Джентри и Брайаном Парно [4] и перекликается с «сертифицированными вычислениями» Микали. [3]
Мотивация и обзор
Растущее желание аутсорсинга вычислительных задач с относительно слабого вычислительного устройства (клиента) к более мощным вычислительным услугам (рабочие), и проблема недобросовестных работников, модифицировать программное обеспечение своих клиентов возвращать правдоподобные результаты без выполнения фактической работы [5] мотивировано формализация понятия проверяемых вычислений. [4]
Поддающиеся проверке вычисления связаны не только с получением результата функции, переданной на аутсорсинг, на входе клиента и доказательством ее правильности, но также с тем, чтобы клиент мог проверить доказательство с гораздо меньшими вычислительными затратами, чем вычисление функции с нуля.
Значительное внимание было уделено проверке вычислений функций, выполняемых ненадежными работниками, включая использование защищенных сопроцессоров , [6] [7] доверенных платформенных модулей (TPM), [8] интерактивных доказательств , [9] [10] вероятностно проверяемых доказательств. , [11] [12] эффективные аргументы, [13] [14] и CS доказательства Микали. [15] Эти проверки являются либо интерактивными, которые требуют взаимодействия клиента с работником для проверки доказательства правильности, [13] [14], либо представляют собой неинтерактивные протоколы, которые могут быть проверены в модели случайного оракула . [15]
Проверка репликацией
Самый крупный проверенный расчет ( SETI @ home ) использует проверку путем репликации.
В процессе проверки SETI @ home задействованы одна клиентская машина и несколько рабочих машин. Клиентский компьютер отправляет идентичные рабочие блоки на несколько компьютеров (как минимум на 2).
Когда недостаточно результатов возвращается в разумный промежуток времени - из-за случайного выключения компьютеров, сбоев связи и т. Д. - или результаты не совпадают - из-за ошибок вычислений, мошенничества путем отправки ложных данных без фактического выполнения работы и т. Д. . - тогда клиентская машина отправляет больше идентичных рабочих единиц другим рабочим машинам. После согласования минимального кворума (часто 2) результатов клиент считает, что эти результаты (и другие идентичные результаты для этого рабочего блока) верны. Клиент предоставляет кредит всем машинам, которые вернули правильные результаты.
Поддающееся проверке вычисление
Дженнаро и др. [4] определили понятие проверяемой схемы вычислений как протокол между двумя сторонами с полиномиальным временем для сотрудничества при вычислении функции F: {0,1} n → {0,1} m . Эта схема состоит из трех основных этапов:
- Предварительная обработка . Этот этап выполняется клиентом один раз, чтобы вычислить некоторую вспомогательную информацию, связанную с F. Часть этой информации является общедоступной для совместного использования с работником, а остальная часть является частной и хранится у клиента.
- Подготовка ввода . На этом этапе клиент вычисляет некоторую вспомогательную информацию о входе функции. Часть этой информации является общедоступной, а остальная часть конфиденциальна и хранится у клиента. Общедоступная информация отправляется работнику для вычисления F на входных данных.
- Расчет и проверка выходных данных . На этом этапе работник использует общедоступную информацию, связанную с функцией F и вводом, которые вычисляются на предыдущих двух этапах, для вычисления закодированного вывода функции F на предоставленном вводе. Затем этот результат возвращается клиенту для проверки его правильности путем вычисления фактического значения вывода путем декодирования результата, возвращенного работником, с использованием частной информации, вычисленной на предыдущих этапах.
Определенное понятие проверяемой схемы вычислений сводит к минимуму взаимодействие между клиентом и работником ровно до двух сообщений, где одно сообщение отправляется от каждой стороны к другой стороне на разных этапах протокола. [4]
Пример схемы, основанной на полностью гомоморфном шифровании
Дженнаро и др. [4] определила проверяемую схему вычислений для любой функции F с использованием искаженной схемы Яо [16] [17] в сочетании с полностью гомоморфной системой шифрования .
Эта проверяемая схема вычислений VC определяется следующим образом: [4]
VC = (KeyGen, ProbGen, Compute, Verify) состоит из четырех следующих алгоритмов:
- KeyGen (F, λ) → (PK, SK) : алгоритм генерации рандомизированного ключа генерирует два ключа, открытый и частный, на основе параметра безопасности λ. Открытый ключ кодирует целевую функцию F и передается работнику , чтобы вычислить F. С другой стороны, секретный ключ является приватным клиентом.
- ProbGenSK (x) → (σx, τx) : алгоритм генерации задачи кодирует вход функции x в два значения, публичное и частное, с использованием секретного ключа SK. Открытое значение σx предоставляется работнику для вычисления F (x), в то время как секретное значение τx остается закрытым для клиента.
- Вычислить (PK, σx) → σy : работник вычисляет закодированное значение σy выходных данных функции y = F (x), используя открытый ключ PK клиента и закодированные входные данные σx.
- Проверить SK (τx, σy) → y ∪ ⊥ : алгоритм проверки преобразует закодированный вывод σy рабочего в фактический вывод функции F, используя как секретный ключ SK, так и секретное «декодирование» τx. Он выводит y = F (x), если σy представляет действительный вывод F на x, или выводит ⊥ в противном случае.
Протокол проверяемой схемы вычислений, определенный Дженнаро и др. [4] работает следующим образом:
Функция F должна быть представлена как логическая схема, на которой будет применяться алгоритм генерации ключа . Алгоритм генерации ключей запускает процедуру искажения Яо по этой логической схеме для вычисления открытого и секретного ключей. Открытый ключ (PK) состоит из всех зашифрованных текстов, которые представляют искаженную схему, а секретный ключ (SK) состоит из всех случайных меток проводов. Сгенерированный секретный ключ затем используется в алгоритме генерации проблемы. Этот алгоритм сначала генерирует новую пару открытого и секретного ключей для гомоморфной схемы шифрования , а затем использует эти ключи с гомоморфной схемой для шифрования правильных входных проводов, представленных как секретный ключ искаженной схемы. Созданные зашифрованные тексты представляют собой общедоступную кодировку ввода (σx), которая передается работнику, в то время как секретный ключ (τx) остается закрытым для клиента. После этого рабочий применяет вычислительные шаги протокола Яо к зашифрованным текстам, сгенерированным алгоритмом генерации проблемы. Это делается путем рекурсивного дешифрования шифровальных текстов ворот до получения окончательных значений выходного провода (σy). Гомоморфные свойства схемы шифрования позволяют рабочему получить шифрование правильного выходного провода. Наконец, рабочий возвращает шифрованные тексты вывода клиенту, который расшифровывает их для вычисления фактического вывода y = F (x) или ⊥.
Определение проверяемой схемы вычислений гласит, что схема должна быть как правильной, так и безопасной. Корректность схемы достигается, если алгоритм генерации проблемы создает значения, которые позволяют честному работнику вычислять закодированные выходные значения, которые будут успешно проверяться и соответствовать оценке F на этих входных данных. С другой стороны, проверяемая схема вычислений является безопасной, если злоумышленник не может убедить алгоритм проверки принять неверный вывод для данной функции F и ввода x.
Практические проверенные вычисления
Хотя было показано, что проверяемые вычисления теоретически возможны (с использованием полностью гомоморфного шифрования или с помощью вероятностно проверяемых доказательств ), большинство известных конструкций очень дороги на практике. Недавно некоторые исследователи попытались сделать проверяемые вычисления практичными. Одним из таких достижений является работа исследователей UT Austin . [18] Авторы начинают с системы аргументов, основанной на вероятностно проверяемых доказательствах, и снижают ее стоимость в 10 20 раз . Они также реализовали свои методы в системе Pepper . Авторы отмечают, что «на данный момент мы пришли к выводу, что как инструмент для построения безопасных систем, PCP и системы аргументации не пропали без вести».
Была изучена общая область, которая теперь включает ряд реализаций различных групп. [19]
Рекомендации
- ^ Бабай, Ласло; Фортноу, Лэнс; Левин, Леонид А .; Сегеди, Марио (1 января 1991). Проверка вычислений в полилогарифмическом времени . Материалы двадцать третьего ежегодного симпозиума ACM по теории вычислений . СТОК '91. Нью-Йорк, Нью-Йорк, США: ACM. С. 21–32. CiteSeerX 10.1.1.42.5832 . DOI : 10.1145 / 103418.103428 . ISBN 978-0897913973.
- ^ Гольдвассер, Шафи ; Калаи, Яэль Тауман ; Ротблюм, Гай Н. (1 января 2008 г.). Делегирование вычислений: интерактивные доказательства для маглов . Материалы сорокового ежегодного симпозиума ACM по теории вычислений . STOC '08. Нью-Йорк, Нью-Йорк, США: ACM. С. 113–122. DOI : 10.1145 / 1374376.1374396 . ISBN 9781605580470.
- ^ а б Микали, С. (01.01.2000). «Вычислительно обоснованные доказательства». SIAM Journal on Computing . 30 (4): 1253–1298. CiteSeerX 10.1.1.207.8277 . DOI : 10,1137 / S0097539795284959 . ISSN 0097-5397 .
- ^ Б с д е е г Дженнаро, Росарио; Джентри, Крейг; Парно, Брайан (31 августа 2010 г.). Неинтерактивные проверяемые вычисления: передача вычислений ненадежным сотрудникам . КРИПТО 2010 . DOI : 10.1007 / 978-3-642-14623-7_25 .
- ^ Мольнар, Д. (2000). «Проблема SETI @ Home». ACM Crossroads . 7 (1).
- ^ Smith, S .; Вайнгарт, С. (1999). «Создание высокопроизводительного программируемого защищенного сопроцессора». Компьютерные сети . 31 (8): 831–960. CiteSeerX 10.1.1.22.8659 . DOI : 10.1016 / S1389-1286 (98) 00019-X .
- ^ Йи, Б. (1994). Использование безопасных сопроцессоров (кандидатская диссертация). Университет Карнеги Меллон.
- ^ Trusted Computing Group (июль 2007 г.). Основная спецификация модуля доверенной платформы . 1.2, редакция 103.
- ↑ Л. Бабай (1985). «Теория торговых групп на случайность». В Proceedings of the ACM Symposium on Theory of Computing (STOC) , New York, NY, US, pp. 421–429.
- ^ С. Гольдвасера, С. Микали и С. Rackoff (1989). «Сложность знаний интерактивных систем доказательства». SIAM Journal on Computing , 18 (1), pp. 186–208.
- ^ С. Арора и С. Сафра (1998). «Вероятностно проверяемые доказательства: новая характеристика NP». Журнал ACM , 45 , стр. 501-555.
- ^ О. Голдрайх (1998). Современная криптография, вероятностные доказательства и псевдослучайность. Серия алгоритмов и комбинаторики, 17 , Springer
- ^ а б Дж. Килиан (1992). «Заметка об эффективных доказательствах и аргументах с нулевым разглашением (расширенная аннотация)». В материалах симпозиума ACM по теории вычислений (STOC)
- ^ а б Дж. Килиан (1995). «Улучшенные дельные аргументы (предварительная версия)». In Proceedings of Crypto , Лондон, Великобритания, стр. 311–324. Springer-Verlag
- ^ а б С. Микали (1994). «Доказательства CS (расширенная аннотация)». В материалах симпозиума IEEE по основам информатики , стр. 436-453.
- Перейти ↑ A. Yao (1982). «Протоколы для безопасных вычислений». В материалах симпозиума IEEE по основам информатики , стр. 160-164.
- ^ А. Яо (1986). «Как создавать и обмениваться секретами». В материалах симпозиума IEEE по основам информатики , стр. 162–167.
- ^ Сетти, Шринатх; Макферсон, Ричард; Блумберг, Эндрю Дж .; Уолфиш, Майкл (февраль 2012 г.). Практическое применение систем аргументов для аутсорсинговых вычислений (иногда) . Симпозиум по безопасности сетей и распределенных систем (NDSS) 2012.
- ^ Уолфиш, Майкл; Блумберг, Эндрю Дж. (01.01.2015). «Проверка вычислений без их повторного выполнения» . Commun. ACM . 58 (2): 74–84. DOI : 10.1145 / 2641562 . ISSN 0001-0782 .