Делегирование памяти

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 17:02, 19 декабря 2015.
Memory Delegation
Memory Delegation.png
Авторы Kai-Min Chung[прим. 1][@: 1]
Yael Tauman Kalai[@: 2]
Feng-Hao Liu[@: 3]
Ran Raz[@: 4]
Опубликован 2015 г.
Сайт Cryptology ePrint Archive
Перевели Dmitry Vakurov
Год перевода 2015 г.
Скачать оригинал

__NUMBEREDHEADINGS__

Аннотация. Мы рассмотрим проблему делегирования вычислений, в которых отправитель даже не знает, что передается на вход функции, и работает в срок, значительно меньший, чем длина входного сигнала.
Например, рассмотрим задачу делегирования памяти, при которой отправитель хочет направить всю свою память в облако. Отправителю может понадобиться, чтобы облако выполнило некоторые вычисления с содержимым этой памяти, и доказать что расчеты были выполнены верно. В качестве другого примера рассмотрим задачу потокового делегирования, в которой идет поток данных, и отправителя, который не может хранить эти данные, а передает эту задачу в облако. Позже отправитель может попросить облако вычислить статистику по этим потоковым данных и доказать правильность вычислений. Отметим, что в обеих задачах отправитель должен хранить короткий сертификат о передаваемых данных, чтобы позже проверить корректность расчетов. Кроме того, в случае потокового делегирования этот сертификат должен быть вычислен потоковым способом.
Мы построим схемы для обеих этих задач и представим неинтерактивный метод, основанный на стандартной схеме делегирования[1]. Эти схемы позволяют делегирование любой функции, вычислимой с помощью -однородного контура низкой глубины (сложность вычисления линейно зависит от глубины). Для задачи делегирования памяти мы полагаемся на существование полилогарифмической частной схемы извлечения информации, а в случае потокового делегирования - на полностью гомоморфическую схему декодирования.
Также мы представим метод решения поставленных задач, основанный на схемах, позволяющих делегирование любой функции из [2]. Однако, они интерактивные (например, состоят из четырех сообщений) или неинтерактивные в случайной модели Oracle.

Ведение

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

Эта идея аутсорсинговых вычислений получает много внимания в последнее время, отчасти из-за растущего интереса к облачным сервисам (возможно ненадежным), которые представляют множественные вычислительные ресурсы. Существует несколько причин, по которым отправитель может не доверять облаку, и поэтому желательно получать доказательства корректности вычислений. Например, облако может иметь побуждение возвращать неправильные ответы. Такое побуждение может быть финансового характера, в случае, если вычисления требуют слишком много времени. Ведь облако может вернуть некорректный ответ, затратив на это меньше времени и, соответственно, средств. А клиент, вероятно, не догадается в подлоге расчетов. Более того, бывают случаи, когда выполнение приложения облаком настолько необходимо, что отправитель желает полностью исключить случайные ошибки в вычислениях.

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

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

В этой работе мы хотим, чтобы отправитель работал за время даже меньшее, чем размер входных данных . Более того, мы даже не допускаем, чтобы отправитель читал входные данные! Однако, это требование может показаться необоснованным и неосуществимым. Поэтому, давайте рассмотрим два примера.

Делегирование памяти. Предположим, что Алиса хочет хранить содержимое своей памяти в облаке. Объем памяти при этом может быть очень большим (например, все когда-либо посланные Алисой e-mail сообщения). Кроме того, предположим, что она не доверяет облаку. Тогда каждый раз как она обращается к облаку для проведения каких-нибудь вычислений (например, сколько сообщений она послала Бобу за последний год), она бы хотела получать ответ с доказательством того, что вычисления были сделаны правильно. Обратите внимание, что на вход этих делегированных функций может подаваться все содержимое ее памяти, которое может быть огромным. Таким образом, крайне нежелательно, чтобы объем входных данных сказывался на работоспособности Алисы. Что еще более важно, Алиса вообще больше не должна хранить содержимое этой памяти после делегирования ее в облако.

Итак, в схеме делегирования памяти, отправитель делегирует содержимое своей памяти облако и затем может попросить его произвести некоторые вычисления с данными из этой памяти. При этом ожидается, что ответ будет сопровожден доказательством корректности проведенных вычислений. Для проверки правильности этих доказательств отправитель должен хранить цифровую подпись содержимого своей памяти. При это цифровая подпись должна вычисляться за полиномиальное время от объема памяти. Доказательства должны эффективно проверяться, скажем за время , где - время вычисления функции. Более того, Алиса должна быть в состоянии эффективно обновить содержимое памяти.

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

Задачи делегирования памяти и поточного делегирования очень похожи.В обоих случаях Алиса просит облако хранить огромный объем данных (ее память или потоковые данные). Но между ними существую два основных отличия.

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

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

Наши результаты

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

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

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

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

Мы рассмотрим два протокола делегирования. Первый из них является неинтерактивным (например, состоит из двух сообщений, посылаемых отправителем и исполнителем). Этот протокол основан на неинтерактивной версии протокола делегирования Голдвассера[1][3]). Так же, как и в протоколе Голдвассера, эффективность отправителя линейно зависит от глубины контура, который был делегирован. Второй протокол является интерактивным (например, состоит из четырех сообщений). Основан на схемах, позволяющих эффективное делегирование любой функции из [2].

В дальнейшем, мы приведем формальные определения нашим теоремам. Тем не менее, ввиду недостатка места в этой заметке, мы отсылаем читателя к полной версии данной работы[4], в которой он сможет ознакомиться со всеми формальными опредлениями.

Теорема 1 (делегирование памяти).

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

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

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

Теорема 2 (потоковое делегирование).

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

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

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

Замечание. Отметим, что одно из свойств протокола Голдвассера показывает, что проверяющему не нужно читать все входные данные с целью проверки, а нужно только получить доступ к одной случайной точке в расширении низкой степени входа. (Мы отсылаем читателя к разделу 2.1 для определения расширения низкой степени.) Мы отметим, что доказательствj схемы делегирования памяти[2] для передачи вычислений машине Тьюринга также обладает тем свойством, что проверка может быть сделана лишь доступом к нескольким случайным точкам в расширении низкой степени входа, предполагая, что основной PCP - это бесконтактный PCP[5].

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

Теорема 3 (интерактивное делегирование памяти).

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

  • Схема имеет совершенную полноту и незначительную (многоразовую) ошибку устойчивости.
  • Отправитель и исполнитель эффективны в оффлайн стадии. А именно, и исполнитель, и отправитель работают за время .
  • Исполнитель эффективен в онлайн стадии. Более конкретно, он работает за время в течение каждой операции и , где есть верхняя граница времени выполнения . Отправитель работает за время в течение каждой операции и .
  • Операции и состоят иp обмена четырьмя сообщениями.

Теорема 4 (интерактивное потоковое делегирование).

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

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

Мы отмечаем, что в Случайной Модели Оракула[6] (СМО), схема делегирования Микали неинтерактивна. Это дает неинтерактивную схему делегирования памяти и неинтерактивную схему потокового делегирования для передачи любой функции из В СМО.

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

Предыдущие работы

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

Интерактивные доказательства. Знаменитая теорема [7][8] приводит интерактивные доказательства для любой функции , вычислимой за полиномиальное время с проверяющим (отправителем) тоже работающим за полиномиальное время. Таким образом, протокол может рассматриваться как протокол делегирования для языков . Однако, сложность доказывающего (исполнителя) ограничена только полиномиальным размером (и, конечно же, экспоненциальным временем). Эта теорема была уточнена и уменьшена[9], чтобы в итоге обеспечить сложность проверяющего , а доказывающего - для функции размера , вычислимой за время для входных данных размера . Отметим, что сложность доказывающего по-прежнему вычисляется за полиномиальное время , даже для вычислений с наименее возможным размером, а именно, .

Сложность доказывающего была улучшена в работе Гольдвассера[1] до , которая в свою очередь улучшается до при . В более общем смысле в работе Гольдвассера[1] приводятся интерактивные доказательства для вычисления небольшой глубины . Эти доказательства достигают сложность для доказывающего и для проверяющего. (Это объясняет результат, полученный для пространственно-ограниченных вычислений, потому что алгоритм, который работает за время и потребляет память может быть изменен в алгоритм глубины , работающий за время .) Однако, если мы не ограничиваемся вычислениями с небольшим пространством или глубиной, то мы не можем использовать интерактивные доказательства. На самом деле, любой язык, имеющий интерактивные доказательства, с проверяющим, работающим за время , может быть решен с затратами памяти .

Интерактивные аргументы. Интерактивные аргументы[10] (известные как вычислительно устойивые доказательства[11]) ослабляют условие устойчивости, чтобы они стали вычислимы. А именно, вместо того, чтобы требовать, чтобы никакая стратегия доказывающего вообще не могла убедить проверяющего о свидетельстве ложного заявления, мы вместо этого требуем, чтобы никакая в вычислительном отношении выполнимая стратегия доказывающего не могла убедить проверяющего о свидетельстве ложного заявления. В этой модели[12][11] даны протоколы с постоянным раундом, в которых сложность доказывающего составляет , а проверяющего - (где секретный параметр), предполагая существование семейства хеш-функций, устойчивых к коллизиям[13].

На пути к неинтерактивным решениям. Возможность эффективных неинтерактивных аргументов была предложена в работе[11] Сильвио Микали, который показал возможность неинтерактивных аргументов со временем работы доказывающего , проверяющего - в Случайной Модели Оракула (оракул используется для устранения взаимодействия[14]). Эвристически, можно надеяться, что создание экземпляра случайного оракула с соответствующим семейством хеш-функций позволило бы нам получить неинтерактивное решение задачи делегирования вычислений: сначала отправитель (или доверенная третья сторона) выбирает и публикует случайную хеш-функцию из семейства, а затем доказательства полностью неинтерактивны (только одно сообщение от доказывающего к проверяющему). Однако, известно, что эвристическая Модель Случайного Оракула, вообще говоря, неустойчива[15], даже в контексте Фиата-Шамира[16][17]. Таким образом, несмотря на широкие усилия, существование эффективных неинтерактивных аргументов по-прежнему остается открытой проблемой в теории сложности и криптографии.

Среди недавних успехов можно отметить снижение количества необходимого взаимодействия. Используя преобразование Калая-Раза[3], протокол делегирования Гольдвассера[1] можно переделать в аргумент, состоящий из двух сообщений (мы предполагаем существование схем частного информационного поиска (PIR-схем) одиночного сервера). Однако, как и интерактивные доказательства[1], это решение применимо только к вычислениям небольшой глубины, поскольку сложность проверяющего растет линейно с увеличением глубины.

Совсем недавно, содружество ученых[18] при поддержке группы Чанга[19] представили схему делегирования, состоящую из двух сообщений, для случайной функции. Однако, их конструкции составляют автономную (оффлайн) фазу, в которой отправитель вычисляет секретное состояние за время , где - время вычисления функции, а - Секретный параметр. В онлайн фазе удалось сократить время работы отправителя до для входа длины , в то время, как исполнитель работает за время . Таким образом, значительные вложения отправителя в автономной (оффлайн) фазе могут быть амортизированы через множество операций в онлайн фазе при передачи вычисления функции на множество входов. Их онлайн фаза не является полностью неинтерактивной, а состоит из двух сообщений. Однако, в большинстве приложений два сообщения будут необходимы в любом случае, поскольку отправителю может потребоваться связь с исполнителем посредством входа .

Заметим, что главный недостаток этих работ[18][19] устойчивость гарантируется только до тех пор, пока состязательный исполнитель не узнал, принял ли отправитель доказательства или отверг.

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

Вероятностно проверяемые доказательства (PCPs) и многократные программы интерактивного доказательства (MIPs). Теорема [21] и ее уменьшенная версия за авторством Бабаи[22] приводит вероятностно проверяемые доказательства (PCPs) и многократные программы интерактивного доказательства (MIPs) за вычислительное время , тогда как, доказывающий работает за время , проверяющий за время точно так, как мы хотим. Однако, использование этих схем для делегации требует специализированных моделей связи, а именно двух не контактирующих между собой доказывающих. Или можно использовать механизм, при котором доказывающий предоставляет проверяющему случайные доступ к длинному (длина порядка вероятностно проверяемому доказательству (PCP), которое не может изменяться доказывающим в момент проверки.

Потоковые интерактивные доказательства. Недавно, Кормод в своей работе[23] рассмотрел потоковые интерактивные доказательства, которые являются укреплением интерактивных доказательств, в которых вход дается проверяющему потоковым способом, и проверяющий ограничивается наличием суб-линейного (в идеале - полилогарифмического) пространства. Он наблюдал, что и в протоколе делегирования Гольдвассера[1], и в универсальных аргументах[13] возможно эффективное изменение схем потоковых интерактивных доказательств и аргументов.

Потоковые интерактивные доказательства тесно связаны с потоковым делегированием. Главное различие заключается в том, что потоковые интерактивные доказательства соответствут единомоментному потоковому делегированию, в то время, как в нашей модели потокового делегирования, отправителю позволено делегировать исполнителю столько вычислений, сколько ему хочется. Действительно, протокол делегирования Гольдвассера[1] также является отправной точкой в нашей конструкции схемы потокового делегирования, но основные усилия мы приложили на то, чтобы наша схема предоставляла возможность повторного использования.

Предварительные итоги

Расширение низкой степени

Пусть есть расширение поля , а - расширение поля (и, в частности, расширение поля ), где [прим. 4]. Мы всегда предполагаем, что операции над полем могут выполняться за полилогарифмическое время от размера поля. Зафиксируем целое число . В дальнейшем мы определим расширение низкой степени для -элементного вектора по отношению к , где .

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

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

где каждое отображение есть m-вариативный многочлен, зависящий только от параметров и m (и не зависит от w). Размер этого многочлена составляет , а степень равняется для каждой переменной.

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

Утверждение 1. Существует машина Тьюринга, принимающая на вход:

  • поле , которое является расширением поля ;[прим. 5]
  • поле , которое является расширением поля ;
  • целое число .

'Машина работает за время . На выходе она предоставляет уникальные 2m-вариативные многочлены степени для каждой переменной (представлены в виде арифметической схемы степени для каждой переменной), такие, что для каждого вектора , где , и для каждой координаты ,

где функция соответствует вектору , как определено в (1), а функция - это его расширение низкой степени (например, уникальное расширение степени не более, чем для каждой переменной).

Более того, можно оценить за время . А именно, существует машина Тьюринга, которая работает за время и принимает на вход параметры (как выше) и пару . На выходе же машина предоставляет .

Следствие 1. Существует машина Тьюринга, принимающая на вход:

  • поле , которое является расширением поля ;
  • поле , которое является расширением поля ;
  • целое число ;
  • вектор , где ;
  • координату .

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

Схемы делегирования

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

Теорема 5.[1][3]

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

  1. Исполнитель работает за время , а отправитель - за время .
  2. Протокол обладает совершенной полнотой и устойчивостью (может быть сколь угодно малым). Устойчивость гарантируется против любого обманывающего исполнителя размера .
  3. Протокол состоит из двух сообщений. Его коммуникационная сложность составляет . Более того, первое сообщение, посылаемое отправителем, зависит только от случайного броска монеты, и не зависит от доказываемого заявления.
  4. Если отправитель получает доступ к расширению низкой степени для , а не учитывает ввод себе, то он работает за время , а протокол по-прежнему обладает всеми свойствами, описанными выше, предполагая, что параметры расширения низкой степени удовлетворяют следующим равенствам:

где - достаточно большой полином[прим. 6]. Более того, отправитель запрашивает расширение низкой степени для в единственной точке, которая выбирается случайным образом (по равномерному распределению, исходя из бросков монеты).

Всюду в этой статье мы будем обозначать описанный выше протокол как .

Обязательства дерева Меркла

Определение 1.

Пусть хеш-функция. Обязательства дерева Меркла для строки по отношению к , обозначаемаое , есть -битная строка, вычислимая по следующим правилам: вход разделен на блоков , каждый блок размера . Эти блоки разделены на пары , и хеш-функция применяется к каждой паре из блоков. Затем эти блока снова делятся на пары, и хеш-функция применяется к каждой паре из этих блоков. Разбиение происходит раз и приводит к двоичному дереву хеш-значенией, пока не останется только один блок. Это будет блок .

Обзор наших методов

Далее мы представим обзор на высоком уровне наших схем делегирования памяти и потокового делегирования. В этом расширенном тезисе мы сфокусируемся на наших неинтерактивных конструкциях, основанных на схемах делегирования GKR[1], и предоставим подробный обзор этих методов. Мы отсылаем читателя к полной версии данной работы [4] для формального определения всех конструкций и их анализа.

Делегирование памяти

Отправная точка этой работы - анализ протокола Гольдвассера[1], а именно то, что этот протокол делегирования может быть очень эффективно проверен (за линейное время в зависимости от размера входа), если у отправителя есть доступ оракула к расширению низкой степени входа . Кроме того, как показывается в работе Гольдвассера[1], отправитель должен получить доступ к этому расширению низкой степени в единственной точке , которая зависит только от случайных бросков монеты отправителем.

Это наблюдение немедленно дает начало схеме делегирования памяти с одноразовой устойчивостью: секретное состояние отправителя будет парой . Затем это секретное состояние будет использовано, чтобы проверить вычисление, используя при этом протокол GKR. Как было рассмотрено в работе Гольдвассера[1], это действительно работает, если отправитель управляет протоколом делегирования. Однако устойчивость в значительной мере полагается на факт, что секретное состояние отправителя действительно секретное, и если отправитель использует это состояние несколько раз, то устойчивость больше не гарантируется.

Нас посетила одна интересная мысль после ознакомления с работой Дженнаро[18], а именно нужно использовать схему полностью гомоморфического шифрования (FHE) зашифровать весь обмен данными, чтобы скрыть секретное состояние. Это действительно работает, если исполнитель не знает, принимает ли отправитель или отклоняет его доказательства. Однако, если исполнитель действительно изучает вердикт отправителя, то возможны атаки, направленные на работу протокола и приводящие к тому, что устойчивость протокола делегирования памяти нарушается. Более того, становится сложно гарантировать устойчивость работы протокола, вплоть до того, что она пропадает полностью.

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

В нашем подходе, вместо наличия у отправителя секретного состояния используется дерево обязательств всего как секретное состояние (см. Раздел 2.3 для определения дерева обязательств). А именно, выбирается случайная хеш-функция , из семейства функций, устойчивых к коллизиям, и сохраняется как секретное состояние. Таким образом, исполнитель получает на вход не только непосредственно саму память , но также хеш-функцию , выбранную отправителем. Мы подчеркиваем, что состояние отправителя при таком подходе не секретное. Это, в свою очередь, делает доказательство безопасности передаваемой памяти значительно более простым действием, чем в задаче потокового делегирования (где состояние отправителя является секретным).

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

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

Отметим, что в случае, когда отправитель желает обновить свою память из до , ему необходимо обновить свое секретное состояние из в [прим. 7]. Однако, отправитель не сможет самостоятельно выполнить эту операцию, так как не обладает памятью . Вместо этого отправитель делегирует это вычисление исполнителю путем запрашивания операции , где .

Потоковое делегирование

Наша схема потокового делегирования очень похода на описанную выше схему делегирования памяти. Основное различие - это способ, которым создается и обновляется сертификат, и способ, которым исполнитель показывает значение .

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

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

(это следует из утверждения 1).

Также, как и в схеме делегирования памяти, в конце работы каждого протокола делегирования, отправитель должен проверить значение в случайной точке . В схеме делегирования памяти это осуществляется путем использования разработанного нами протокола , в котором исполнитель выявляет увеличенный путь листа дерева обязательств Меркла для . В задаче потокового делегирования протокол полностью отличается, так как отправитель не может самостоятельно вычислить дерево обязательств Меркла для . К сожалению, в отличие от схемы делегирования памяти, в задаче потокового делегирования возможность создания многоразового и устойчивого протокола выявления является чрезвычайно нетривиальной задачей.

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

Протокол
Отправитель хранит секретное состояние , где и - это случайная точка из . Отправитель хочет изучить значение расширения низкой степени , полученное от исполнителя .

Протокол состоит из следующих шагов:

  • Отправитель отсылает исполнителю прямую , проходящую через точки и . Говоря более конкретно, выбирает две случайные точки и определяет как прямую, удовлетворяющую и .
  • Исполнитель возвращает одномерный полином , который является полиномом расширения низкой степени , ограниченный прямой (например, ).
  • проверяет справедливость выполнения равенства , и, в случае совпадения, принимает значение . В противном случае отвергает.
Фигура 1. Описание протокола

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

Как отметил Дженнаро в своей работе[18], естественным способом защиты секретной точки является использование полностью гомоморфической схемы шифрования совместно с рассмотренным выше протоколом . А именно, генерирует пару ключей для (Gen, Enc, Dec, Eval) и посылает и зашифрованную прямую к исполнителю , который может вычислить полином гомоморфно над шифровнием. В самом деле, путем семантического шифрования , противоборствующий исполнитель не может получить никакой информации из сообщения отправителя, состоящего из . Это действительно делает протокол многоразовым обеспечивая невозможностью узнать решение , как показано в работах Дженнаро[18][19].

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

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

Протокол
Отправитель хранит секретное состояние , где и - это случайная точка из . Отправитель хочет изучить значение расширения низкой степени , полученное от исполнителя .

Протокол состоит из шагов, несколько измененных, по сравнению с предыдущей версией протокола:

  • Отправитель предпринимает следующие действия:
    1. Генерирует пару ключей для полностью гомоморфической схемы шифрования .
    2. Выбирает случайное двумерное аффинное подпространство , содержащее точки и . Говоря более конкретным языком, выбирается две случайные точки , а, в свою очередь, будет случайным двумерным аффинным подпространством, удовлетворяющим и .
    3. Посылает и к .
  • Исполнитель гомоморфично вычисляет полином под (обозначим итоговый шифротекст как ) и отсылает к .
  • дешифрует и проверяет справедливость выполнения равенства , и, в случае совпадения, принимает значение . В противном случае отвергает.
Фигура 2. Описание протокола

Мы доказываем, что никакой эффективный соперничающий исполнитель не может узнать полезную информацию о секретной точке из протокола . Мы отмечаем, что доказательство вышеупомянутого заявления очень нетривиально, и является одной из главных технических трудностей в этой работе. Говоря неформально, сначала мы доказываем устойчивую к утечкам леммe, которая утверждает, что шифротекст и бит решения (который зависит стратегии ) не дает слишком много информации о к . Другими словами, случайное подпространство по прежнему обладает высокой энтропией с точки зрения . Затем мы используем информационно-технический аргумент для доказательства того, что случайная точка в достаточно случайном (с высокой энтропией) подпространстве является статистически близкой к случайной точку из , что предполагает, что не изучает полезную информацию о точке .

Размер поля. Напомним, что по лемме Шварца-Зиппеля, соперничающий исполнитель может обмануть с вероятностью не более, чем , где - это степень расширения . Выразим это через параметры:

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

Идея состоит в том, чтобы уменьшить вероятность обмана до незначительного, просто увеличив размер поля до сверх-полиномиального. Однако, мы не можем увеличить размер поля в протоколе , так как это увеличит временную сложность работы исполнителя. Вместо этого, только для сертификата и протокола мы используем расширенное поле сверх-полиномиального размера , полученное из поля , но запускаем протокол также, как прежде. А именно, секретное состояние - это , где . Протокол работает точно также, как прежде с параметрами .

Дополнительные особенности

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

Вспомните, что в приведенном выше обзоре, мы утверждали, что , просто управляет в дополнение к протоколу , который помогает отправителю проверить протокол [прим. 8]. Есть несколько технических причин, почему фактически это не работает. В дальнейшем мы объясним, что является главной технической проблемой, и дадим высокоуровневою идею того, как ее преодолеть.

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

где . При делегировании вычисления функции и отправитель, и исполнитель запускают . Затем нужно проверить для случайных точек . Однако, здесь параметры расширения низкой степени зависят от глубины схемы вычисления . А именно, эти параметры для расширения низкой степени приведены в работе Гольдвассера[1] (см. также теорему 5 данной работы). Представлены он следующим образом:

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

Мы обходим эту техническую проблему путем делегирования функции . К счастью, эти функции могут вычисляться полиномиальной схемой глубины не более, чем , исходя из предположения, что делегируемая функция является полиномиальной (см. предположение 1). Мы передаем вычисление каждой из функций , используя при этом протокол , чтобы удостовериться в незначительной ошибке. Поэтому, в итоге исполнителю нужно выявить точек в расширении низкой степени ( точек для каждой функции )[прим. 9].

Заключительная техническая сложность, с которой мы столкнулись - это необходимость запуска всех рассмотренных алгоритмов в параллельном режиме, так как мы стремились к тому, чтобы наша итоговая схема делегирования была неинтерактивной (состояла только из двух сообщений). Обычно, на практике не возникает проблем в запуске нескольких неинтерактивных протоколов одновременно[24][25]. Однако, в нашем случае отправитель использует общий секретный вход в этих протоколах. А именно, отправитель использует секретную случайную последовательность в приготовлениях к использованию протокола в параллельном режиме, в конце которого возникает необходимость проверить для каждого . В дополнение к этому, отправитель использует эти в протоколе делегирования . Более того, в конце каждой итерации отправителю необходимо проверить, что выполняется равенство для случайно точки . В конце необходимо использовать протокол выявления для каждого , обозначенно через .

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

Благодарности

Мы очень благодарны Shai Halevi за сотрудничество с нами на начальном этапе данной работы, и Salil Vadhan за полезные дискуссии.

Контакты авторов материала

  1. Department of Computer Science, Cornell University, Ithaca, NY, USA, E-mail: chung@cs.cornell.edu
  2. Microsoft Research New England, Cambridge MA, USA, E-mail: yael@microsoft.com
  3. Department of Computer Science, Brown University, Providence RI, USA, E-mail: fenghao@cs.brown.edu
  4. Department of Mathematics and Computer Science, Weizmann Institute of Science, Rehovot, Israel, E-mail: ran.raz@weizmann.ac.il

Примечание

  1. Гранты №2006060 и CNS-0831289.
  2. Таким образом, для каждой константы , если мы ограничим глубину , чтобы быть наиболее ближе к , то отправитель будет значительно эффективнее.
  3. Мы предполагаем, что .
  4. Обычно, при выполнении расширения низкой степени, берется такое, чтобы быть расширением поля , а - это просто подмножество (причем, необязательно подполе). В этой работе, следуя работе Гольдвассера, мы взяли как подполе. Однако, все, что действительно необходимо уяснить, так это то, что размер этого поля для любого .
  5. Применительно к этой работе, когда мы говорим, что машина Тьюринга принимает на вход некое поле , то подразумевается, что машине дают его короткое описание, что позволяет выполнять операции над полем за полилогарифмическое время в зависимости от его размера.
  6. Чем больше полином, тем меньше устойчивость.
  7. На самом деле, по техническим причинам нужно выбирать новую хеш-функцию после каждой операции . В данной работе мы не будем подробно останавливаться на этом вопросе.
  8. Протокол в задаче делегирования памяти значительно отличается от версии, представленной для задачи потокового делегирования
  9. Мы отмечаем, что есть несколько возможных путей повышения эффективности, например, предположение, что последовательность является одной функцией. Однако, ради простоты изложения, мы выбираем наиболее простое (даже если оно менее эффективное) решение.

Литература

  1. 1,00 1,01 1,02 1,03 1,04 1,05 1,06 1,07 1,08 1,09 1,10 1,11 1,12 1,13 1,14 Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum. Delegating computation: interactive proofs for muggles. In STOC, pages 113-122, 2008.
  2. 2,0 2,1 2,2 Silvio Micali. Cs proofs (extended abstracts). In FOCS, pages 436-453, 1994.
  3. 3,0 3,1 3,2 3,3 Yael Tauman Kalai and Ran Raz. Probabilistically checkable arguments. In CRYPTO, 2009.
  4. 4,0 4,1 4,2 Kai-Min Chung, Yael Tauman Kalai, Feng-Hao Liu, and Ran Raz. Memory delegation. Cryptology ePrint Archive, Report 2011/273, 2011. http://eprint.iacr.org/.
  5. Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil P. Vadhan. Short pcps verifiable in polylogarithmic time. In IEEE Conference on Computational Complexity, pages 120-134, 2005.
  6. Mihir Bellare and Phillip Rogaway. Minimizing the use of random oracles in authenticated encryption schemes. In ICICS, pages 1-16, 1997.
  7. Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan. Algebraic methods for interactive proof systems. J. ACM, 39(4):859868, 1992.
  8. Adi Shamir. IP = PSPACE. Journal of the ACM, 39(4):869-877, 1992.
  9. Lance Fortnow and Carsten Lund. Interactive proof systems and alternating timespace complexity. Theoretical Computer Science, 113(1):55-73, 1993.
  10. Gilles Brassard, David Chaum, and Claude Criffepeau. Minimum disclosure proofs of knowledge. Journal of Computer and System Sciences, 37(2):156-189, 1988.
  11. 11,0 11,1 11,2 Silvio Micali. Computationally sound proofs. SIAM J. Comput., 30(4):1253-1298, 2000.
  12. Joe Kilian. A note on efficient zero-knowledge proofs and arguments (extended abstract). In STOC, pages 723-732, 1992.
  13. 13,0 13,1 Boaz Barak and Oded Goldreich. Universal arguments and their applications. In Proceedings of the 17th Annual IEEE Conference on Computational Complexity, pages 194-203, 2002.
  14. Amos Fiat and Adi Shamir. How to prove yourself: Practical solutions to identification and signature problems. In CRYPTO, pages 186-194, 1986.
  15. Ran Canetti, Oded Goldreich, and Shai Halevi. The random oracle methodology, revisited. Journal of the ACM,51(4):557-594, 2004.
  16. Boaz Barak. How to go beyond the black-box simulation barrier. In FOCS, pages 106-115, 2001.
  17. Shafi Goldwasser and Yael Tauman Kalai. On the (in)security of the fiat-shamirparadigm. pages 102-113, 2003.
  18. 18,0 18,1 18,2 18,3 18,4 18,5 Rosario Gennaro, Craig Gentry, and Bryan Parno. Non-interactive verifiable computing: Outsourcing computation to untrusted workers. In CRYPTO, pages 465-482, 2010.
  19. 19,0 19,1 19,2 19,3 Kai-Min Chung, Yael Kalai, and Salil P. Vadhan. Improved delegation of computation using fully homomorphic encryption. In CRYPTO, pages 483-501, 2010.
  20. Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. From secrecy to soundness: Efficient verification via secure computation. In ICALP (1), pages 152-163, 2010.
  21. Laszlo Babai, Lance Fortnow, and Carsten Lund. Non-deterministic exponential time has two-prover interactive protocols. Computational Complexity, 1:3-40, 1991.
  22. Laszlo Babai, Lance Fortnow, Leonid A. Levin, and Mario Szegedy. Checking computations in polylogarithmic time. In STOC, pages 21-31, 1991.
  23. G. Cormode, J. Thaler, and K. Yi. Verifying computations with streaming interactive proofs. Technical Report TR10-159, ECCC Report, 2010.
  24. Mihir Bellare, Russell Impagliazzo, and Moni Naor. Does parallel repetition lower the error in computationally sound protocols? In FOCS, pages 374-383, 1997.
  25. Ran Canetti, Shai Halevi, and Michael Steiner. Hardness amplification of weakly verifiable puzzles. In TCC, pages 17-33, 2005.