Протокол проверяемых вычислений
 | На эту статью не ссылаются другие статьи Википедии. |
В криптографии протокол проверяемых вычислений (англ. verifiable computing) — это криптографический протокол, позволяющий освободить непроизводительный компьютер от сложных вычислений путём их частичного или полного переноса на один или несколько внешних более производительных компьютеров (англ. Outsource), сохраняя возможность проверки корректности возвращённого результата без дополнительного взаимодействия. Исполнители возвращают результат и доказательство корректности вычислений. В качестве внешней более производительной системы часто применяется система с распределёнными вычислениями. Например, такая, как облачные вычисления.
Протокол был сформулирован и его корректность была доказана Росарио Дженейро (англ. Rosario Gennaro), Грегом Гентри (англ. Craig Gentry) и Брайном Парно (англ. Bryan Parno) в статье[1].
История. Предпосылки появления[править | править код]
В последние годы наметилась тенденция к передаче вычислений от сравнительно малопроизводительных вычислительных устройств к более производительным вычислительным системам. Этому способствовало несколько факторов.
- В течение 2000-х годов научные проекты: SETI@Home, Folding@Home, Число Мерсенна (GIMPS) и др. — использовали свободные вычислительные ресурсы на компьютерах добровольцев. Большой проблемой для этих проектов стали нечестные участники — те, кто модифицировал клиентское программное обеспечение таким образом, чтобы возвращать подобный правильному результат без выполнения необходимых вычислений только для повышение своего рейтинга в системе. Борьба с таким мошенничеством велась с помощью избыточности вычислений: одно и то же задание рассылалось нескольким клиентам, а результаты после возвращения сверялись.
- Удешевление услуг сервисов облачных вычислений привело к тому, что многие компании отказались от покупки и обслуживания собственной вычислительной системы в пользу покупки рабочего времени у сервисов облачных вычислений. Часто на вычисление передаются критически важные приложения, поэтому важно избежать ошибок при вычислении. Кроме того, сервис облачных вычислений имеет обязательства корректно вычислять даже не важные задачи, ошибки в которых клиент, скорее всего, не заметит, а клиент должен быть уверен в корректности всех результатов, вычисленных сервисом.
- Распространение мобильных устройств таких, как смартфоны и нетбуки, где малопроизводительное устройство часто имеет потребность работать с такими сложными с вычислительной точки зрения приложениями, как криптография или работа с фотографиями, а также в корректности их результата.
Важным требованием к реализации протокола проверяемых вычислений во всех выше перечисленных случаях является то, что проверка корректности результата клиентом должна использовать намного меньше ресурсов по сравнению с самим вычислением задачи.[1]
Предыдущие решения[править | править код]
Проверка повторением (англ. Verification by replication)[править | править код]
Предлагается схема, в которой клиенту или случайно выбранному другому участнику системы необходимо пересчитать результат некоторой работы, выполненной другим участником. На всех участников вычислений заводится рейтинг. Рейтинг участника увеличивается, если он возвращает правильный результат, и уменьшается, если некорректный. Кроме того, участник нашедший ошибку у другого участника награждается. Такая схема невыгодна для клиентов с малым количеством вычислительных ресурсов, и требует хотя бы какой-то части надежных или хотя бы не сговорившихся участников.
- Использование криптопроцессоров
Использование отдельных защищённых сопроцессоров для вычислений требует их высокой стойкости от несанкционированного доступа (англ. Tamper resistance), что делает такие процессоры очень дорогими. Повсеместное использование Trusted Platform Module для защиты программного обеспечения из-за их низкой относительно защищённых сопроцессоров стоимости привело к тому, что у них практически нет защиты от несанкционированного доступа[1].
Использование интерактивного доказательства[править | править код]
Интерактивное доказательство сводится к концепции вероятностно проверяемого доказательства. PCP-теорема утверждает, что любое доказательство можно переделать за полиномиальное время в такое, которое можно вероятностно проверить, прочитав лишь константное число битов этого доказательства, при этом алгоритм проверки доказательства использует лишь логарифмическое число случайных битов. Таким образом, участнику необходимо подготовить доказательство, а клиент может проверить только некоторые места (в частности постоянное количество бит доказательства). Однако эта проверка может быть очень сложной для клиента с вычислительной точки зрения[1].
Формальное описание протокола проверяемых вычислений[править | править код]
Дженейро, Гентри и Парно определили протокол проверяемых вычислений как протокол между двумя участниками: клиентом и исполнителем — для вычисления функции F: {0,1}n → {0,1}m. Эта схема состоит из трех шагов:
- Предварительная обработка
На этом шаге клиент вычисляет некоторую вспомогательную информацию о функции F. Часть этой информации является публичной и отсылается исполнителям, другая часть является секретной и остаётся на клиенте.
Эта стадия может занимать время, сравнимое с временем непосредственного вычисления функции F. Но это время несущественно при большом количестве вычислений, так как эта стадия выполняется только один раз.
- Подготовка входных данных
На этом шаге клиент вычисляет некоторую вспомогательную информацию о входных данных. Часть этой информации является публичной и отсылается исполнителям, другая часть является секретной и остаётся на клиенте.
- Вычисление результата и его проверка
Пользуясь присланной клиентом публичной информацией о функции и входных данных, он вычисляет закодированный результат и возвращает его клиенту. Получив закодированный результат, клиент использует сохранённую секретную информацию для раскодирования результата, и получает либо действительный результат применения функции, либо специальное значение, показывающее некорректность произведённых исполнителем вычислений.
Этот протокол минимизирует взаимодействие клиента и исполнителя до двух сообщений.
Пример реализации протокола[править | править код]
В статье[1] дан пример схемы основанной на протоколе конфиденциального вычисления[3]. Эндрю Яо (англ. Andrew Yao) и гомоморфном шифровании.
VC = (KeyGen, ProbGen, Compute, Verify) состоит из четырёх шагов:
- KeyGen(F, λ) → (PK, SK): Генератор случайных ключей по параметру λ генерирует открытый и закрытый ключи. Открытый ключ кодирует функцию F и отправляется исполнителю.
- ProbGenSK(x) → (σx, τx): Входные данные шифруются в две величины: открытую σx и закрытую τx с помощью SK. Открытое значение σx отсылается исполнителю для вычисления F(x), а закрытая остается у клиента.
- ComputePK(σx) → σy: Исполнитель вычисляет σy — шифрованное значение функции y = F(x), используя открытый ключ PK и шифрованное входное данное σx.
- VerifySK(τx, σy) → y ∪ ⊥: Алгоритм проверки конвертирует шифрованный результат исполнителя encoded σy в действительный результат F, используя оба закрытых ключа: SK и τx. Это соответствует y = F(x), если σy представляет правильный результат F от x, или результат ⊥.
Примечания[править | править код]
- ↑ 1 2 3 4 5 Gennaro, Rosario; Gentry, Craig; Parno, Bryan (31 August 2010). Non-Interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers (PDF). CRYPTO 2010. Архивировано из оригинала (PDF) 4 марта 2016. Дата обращения: 11 декабря 2013.
- ↑ Incentivizing Outsourced Computation (PDF). NetEcon '08: Proc. Third Int'l Workshop Economics of Networked Systems, 2008. 25 August 2008. Архивировано из оригинала (PDF) 31 января 2014. Дата обращения: 11 декабря 2013.
- ↑ A Proof of Yao’s Protocol for Secure Two-Party Computation (PDF). 26 June 2006. Архивировано из оригинала (PDF) 26 ноября 2013. Дата обращения: 11 декабря 2013.