WikiDer > Проверяемые вычисления

Verifiable computing

Проверяемые вычисления (или же проверенное вычисление или же проверенные вычисления) позволяет компьютер к разгрузить то вычисление одной функции, другой, возможно, ненадежной клиенты, сохраняя при этом поддающиеся проверке результаты. Остальные клиенты оценивают функцию и возвращают результат с доказательством того, что вычисление функции было выполнено правильно. Появление этого понятия произошло в результате все более распространенного явления "аутсорсинг"вычисления для ненадежных пользователей в таких проектах, как SETI @ home а также к растущему желанию слабых клиентов передать вычислительные задачи на аутсорсинг более мощной вычислительной службе, такой как в облачные вычисления. Эта концепция восходит к работе Бабая и др.,[1] и изучалась под различными терминами, включая «проверку вычислений» (Бабай и др.), «делегирование вычислений»,[2] "сертифицированный расчет",[3] и проверяемые вычисления. Период, термин проверяемые вычисления сам был оформлен Розарио Дженнаро, Крейг Джентри, и Брайан Парно,[4] и перекликается с «сертифицированными вычислениями» Микали.[3]

Мотивация и обзор

Растущее желание передать вычислительные задачи на аутсорсинг от относительно слабого вычислительного устройства (клиента) к более мощным вычислительным службам (worker), а также проблема недобросовестных работников, которые модифицируют программное обеспечение своего клиента, чтобы возвращать правдоподобные результаты, не выполняя фактическую работу.[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}п → {0,1}м. Эта схема состоит из трех основных фаз:

  1. Предварительная обработка. Этот этап выполняется клиентом один раз, чтобы вычислить некоторую вспомогательную информацию, связанную с F. Часть этой информации является общедоступной для совместного использования с работником, а остальная часть является частной и хранится у клиента.
  2. Подготовка ввода. На этом этапе клиент вычисляет некоторую вспомогательную информацию о входе функции. Часть этой информации является общедоступной, а остальная часть конфиденциальна и хранится у клиента. Открытая информация отправляется работнику для вычисления F на входных данных.
  3. Расчет и проверка выходных данных. На этом этапе работник использует общедоступную информацию, связанную с функцией F, и входными данными, которые вычисляются на предыдущих двух этапах, для вычисления закодированный выход функции F на заданном входе. Затем этот результат возвращается клиенту для проверки его правильности путем вычисления фактического значения вывода с помощью расшифровка результат, возвращаемый работником с использованием частной информации, вычисленной на предыдущих этапах.

Определенное понятие проверяемой схемы вычислений минимизирует взаимодействие между клиентом и работником точно в два сообщения, причем одно сообщение отправляется от каждой стороны к другой стороне на разных этапах протокола.[4]

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

Дженнаро и др.[4] определила проверяемую схему вычислений для любой функции F с помощью Искаженная схема Яо[16][17] в сочетании с полностью гомоморфная система шифрования.

Эта проверяемая схема вычислений ВК определяется следующим образом:[4]

ВК = (KeyGen, ProbGen, вычислить, проверить) состоит из четырех следующих алгоритмов:

  1. KeyGen (F, λ) → (ПК, СК): Рандомизированный алгоритм генерации ключей генерирует два ключа, открытый и закрытый, на основе параметр безопасности λ. В открытый ключ кодирует целевую функцию F и отправляется исполнителю для вычисления F. С другой стороны, Секретный ключ клиент сохраняет конфиденциальность.
  2. ProbGenSK (x) → (σx, τx): Алгоритм генерации проблемы кодирует вход функции x в два значения, публичное и частное, с использованием секретного ключа SK. Открытое значение σx предоставляется работнику для вычисления F (x), в то время как секретное значение τx остается закрытым для клиента.
  3. Вычислить (PK, σx) → σy: Рабочий вычисляет закодированное значение σy выхода функции y = F (x), используя открытый ключ клиента PK и закодированный вход σx.
  4. Проверять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 Остин исследователи.[18] Авторы начинают с системы аргументов, основанной на вероятностно проверяемые доказательства и снизить его затраты в 10 раз20. Они также реализовали свои методы в Перец система. Авторы отмечают, что «на данный момент мы пришли к выводу, что как инструмент для построения безопасных систем, PCP и системы аргументации не пропали без вести».

Была изучена общая область, которая теперь включает в себя ряд реализаций различных групп.[19]

Рекомендации

  1. ^ Бабай, Ласло; Фортноу, Лэнс; Левин, Леонид А .; Сегеди, Марио (1 января 1991). Проверка вычислений в полилогарифмическом времени. Материалы двадцать третьего ежегодного симпозиума ACM по теории вычислений. СТОК '91. Нью-Йорк, Нью-Йорк, США: ACM. С. 21–32. CiteSeerX 10.1.1.42.5832. Дои:10.1145/103418.103428. ISBN 978-0897913973.
  2. ^ Гольдвассер, Шафи; Калаи, Яэль Тауман; Ротблюм, Гай Н. (01.01.2008). Делегирование вычислений: интерактивные доказательства для маглов. Материалы сорокового ежегодного симпозиума ACM по теории вычислений. STOC '08. Нью-Йорк, Нью-Йорк, США: ACM. С. 113–122. Дои:10.1145/1374376.1374396. ISBN 9781605580470.
  3. ^ а б Микали, С. (1 января 2000 г.). «Вычислительно обоснованные доказательства». SIAM Журнал по вычислениям. 30 (4): 1253–1298. CiteSeerX 10.1.1.207.8277. Дои:10.1137 / S0097539795284959. ISSN 0097-5397.
  4. ^ а б c d е ж грамм Дженнаро, Росарио; Джентри, Крейг; Парно, Брайан (31 августа 2010 г.). Неинтерактивные проверяемые вычисления: передача вычислений ненадежным сотрудникам. КРИПТО 2010. Дои:10.1007/978-3-642-14623-7_25.
  5. ^ Мольнар, Д. (2000). «Проблема SETI @ Home». ACM Crossroads. 7 (1).
  6. ^ Smith, S .; Вайнгарт, С. (1999). «Создание высокопроизводительного программируемого защищенного сопроцессора». Компьютерная сеть. 31 (8): 831–960. CiteSeerX 10.1.1.22.8659. Дои:10.1016 / S1389-1286 (98) 00019-X.
  7. ^ Йи, Б. (1994). Использование безопасных сопроцессоров (Кандидатская диссертация). Университет Карнеги Меллон.
  8. ^ Trusted Computing Group (июль 2007 г.). Основная спецификация модуля доверенной платформы. 1.2, редакция 103.
  9. ^ Л. Бабай (1985). «Теория торговых групп на случайность». В Материалы симпозиума ACM по теории вычислений (STOC), Нью-Йорк, Нью-Йорк, США, стр. 421–429.
  10. ^ С. Гольдвассер, С. Микали и К. Ракофф (1989). «Сложность знаний интерактивных систем доказательства». SIAM Журнал по вычислениям, 18(1), стр. 186–208.
  11. ^ С. Арора и С. Сафра (1998). «Вероятностно проверяемые доказательства: новая характеристика NP». Журнал ACM, 45, стр.501-555
  12. ^ О. Гольдрайх (1998). Современная криптография, вероятностные доказательства и псевдослучайность. Серия алгоритмов и комбинаторики, 17, Springer
  13. ^ а б Дж. Килиан (1992). «Заметка об эффективных доказательствах и аргументах с нулевым разглашением (расширенная аннотация)». В Материалы симпозиума ACM по теории вычислений (STOC)
  14. ^ а б Дж. Килиан (1995). «Улучшенные дельные аргументы (предварительная версия)». В Труды Crypto, Лондон, Великобритания, стр. 311–324. Springer-Verlag
  15. ^ а б С. Микали (1994). «Доказательства CS (расширенная аннотация)». В Материалы симпозиума IEEE по основам компьютерных наук, стр. 436-453.
  16. ^ А. Яо (1982). «Протоколы для безопасных вычислений». В Материалы симпозиума IEEE по основам информатики, стр. 160-164
  17. ^ А. Яо (1986). «Как создавать и обмениваться секретами». В Материалы симпозиума IEEE по основам информатики, стр. 162-167
  18. ^ Сетти, Шринатх; Макферсон, Ричард; Блумберг, Эндрю Дж .; Уолфиш, Майкл (февраль 2012 г.). Практическое применение систем аргументов для аутсорсинговых вычислений (иногда). Симпозиум по безопасности сетей и распределенных систем (NDSS) 2012.
  19. ^ Уолфиш, Майкл; Блумберг, Эндрю Дж. (01.01.2015). «Проверка вычислений без их повторного выполнения». Commun. ACM. 58 (2): 74–84. Дои:10.1145/2641562. ISSN 0001-0782.