Головоломки блокирующие время в Случайных Моделях Oracle

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 15:08, 2 ноября 2015.
Time-Lock Puzzles in the Random Oracle Model
TLPiROM.png
Авторы Mohammad Mahmoody, Tal Moran, and Salil Vadhan
Опубликован 2011 г.
Сайт International Association for Cryptologic Research
Перевели Oleg Tadzhibaev
Год перевода 2015 г.
Скачать оригинал

__NUMBEREDHEADINGS__

Аннотация. Головоломка блокирующая время это механизм для отправки сообщений «в будущее». Отправитель опубликовывает головоломку, решение которой это сообщение для отправки, таким образом, скрывая его, пока есть достаточно времени до истечения времени для решения головоломки. Для головоломки блокирующее время полезно что бы создание головоломки занимало меньше времени, чем её решение. Так противники могут иметь доступ к большему количеству компьютеров, чем честных решателей, массовые параллельные решатели не должны быть в состоянии производить решения гораздо быстрее, чем серийные.

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

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

Введение

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

В дополнение к основному виду использования «отправка сообщений в будущее», есть много других потенциальных применений тайм-релиза криптографии. Ривеста, Шамир и Вагнер [2] предполагают, что среди других целей: задержка цифровых наличных платежей, sealed-bid аукционы и ключи Escrow. Боне и Наор[3] определили обязательства по времени и время подписей, и показали что лини могут быть использованы для справедливого подписания контракта, сохранение честности аукционов и многое другое.

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

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

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

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

Бихам, Горен и Ишай[4] предлагают дополнительный импульс, а так же: получение (слабых) ключей-соглашений протоколов на основе односторонней функции которая не поддается квантовой атаке. Они показывают, что в классическом мире существуют слабые ключи-соглашения протоколов на основе односторонних функций (сила конечной степени), которые заставляют противника работать в времени, квадратичному времени честных лиц, на основе варианта головоломок Меркеля[5]. Тем не менее, обе их конструкции и оригинальные головоломки Меркля уязвимы для квантовой атаки через алгоритм поиска Гровера[6]. Битам и др. обратили внимание, что ускорение Гравера применяется только к параллельному поиску и остаются в качестве открытого вопроса, существуют ли такие головоломки, которые устойчивы к параллельной атаке (и таким образом к квантовой).

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

Случайная модель oracle интересна по нескольким причинам. Во-первых, негативные результаты в этой модели исключают конструкции «черного ящика» из односторонних перестановок и устойчивость к коллизии хэш-функции (т.к. случайная функция устойчива к коллизии и неотличима от случайной перестановки, используя только небольшое количество запросов, смотреть пример,[[5],[3],[7]] для более подробной информации). Во-вторых, большинство «обычных» протоколов, которые как было доказано в безопасности в модели случайного оракула, кажется, должны быть безопасными в практике также (хотя некоторые «искусственные» протоколы безопасны в этой модели, но небезопасны для любого явного экземпляра случайного оракула[8]), и построение протокола в этой модели иногда является первым шагом к строительству доказуемом безопасностью протокола в простой модели (например, первая эффективная схема МБЧ была доказана в безопасности в модели случайного оракула[9], после чего конструкции были найдены в стандартной модели, а так же [[10],[11],[12]]). И, наконец, модель случайного оракула гораздо проще анализировать, чем модели, которые вычисляют вычислительную мощность, и лучше понять проблемы в этой обстановке может дать представление о случае теоретико-сложности.

Мы можем думать о генераторе головоломки блокирующее время в рандомизированом алгоритме оракула (где случайный вход и Н случайный оракул) есть пара : головоломка и валидатор решения . Решающая программа, учитывая , должна вывести решение х, что . Когда головоломка блокирующее время имеет одно решение, например, когда оно используется, что бы скрыть зашифрованное сообщение, просто сравнивает своё содержание с этой постоянную величиной. В целом, однако, может выполнять более сложные проверки и наши отрицательные результаты верны, даже если не является эффективным (обратите внимание, что v не имеет доступа к случайному оракулу). Для того, что бы головоломка блокирующее время была хорошей, мы бы хотели, что бы было бы легко вычислить, но в меру трудно решить, даже для противника с параллельной атакой. Точнее, если мы можем вычислить используя n запросов Н, и мы бы хотели, что бы это удовлетворяло :

Завершенность

— Существует (случайным образом) алгоритм g за полиномиальное время (честный решатель), который решает головоломки генерируемые : с большой вероятностью (более случайных монет и g и случайного оракула Н), если мы генерируем и и . Мы используем сокращенную запись [ ;  ; ], что бы снять обращение внимания на событие, и как головоломка была генерирована как описано выше, решатель бы запускал и решение было действительным бы. Обозначим через число запросов g делающих H. m измеряет трудность для честного решателя и должно быть больше в меру, чем n, например, большой полином из n.

Обоснованность

— Любой алгоритм, который решает и делает до запросов H должен использовать по крайней мере уровня адаптивности. Например, мы могли бы взять и . Количество уровней адаптивности измеряет сложность для противника параллельной атакой; это требование означает, что если противник не делает очень большое количество запросов, то использование параллелизма не даст ему преимущества над честным решателем.

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

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

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

Формально, мы докажем следующие две теоремы:

TemplateTheoremIcon.svg Теорема Теорема 1
(Оптимальна адаптивость, но противник неэффективен). Пусть алгоритма оракула, который делает запросов случайного оракула и g алгоритма оракула, что делает более запросов к .
Доказательство

Если ; ;

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


TemplateTheoremIcon.svg Теорема Теорема 2
(Эффективна, но противник не оптимален).Пусть алгоритм оракула, делающий более запросов случайного оракула и алгоритма оракула, делающий более запросов к .
Доказательство

Если ; ; то для всех существует детерминированный противник Javier (обозначается ), который делает в большинстве запросов , использует только уровни адаптивности и удовлетворяет ; ; . Кроме того, время работы это Õ раз времени работы .

Некоторое понимание для доказательств обеих теорем, а также полное доказательство Теоремы 2, можно найти в Разделе 2. Из-за соображений экономии места, доказательство Теоремы 1 отложено до полной версии.

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

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

Доказательство. Пусть , где является полной публичной расшифровкой когда используют Алиса случайные монеты и Боб случайные монеты . Решением будет

По результатам [13], существует противник, который делает не более запросов и выводит "правильное" решение этой головоломки (то есть, выход, что согласуется с Бобом) с вероятностью . Считаем, что этот противник - решатель . По Теореме 1 следует, что существует решатель, преуспевающий с вероятностью делающих запросов и использующих только уровни адаптивности ( потому что общее количество запросов, сделанных ограниченно общим числом запросов сделанным Алисой и Бобом ).

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

TemplateTheoremIcon.svg Теорема Теорема 3
(Пусть параметр безопасности). Существуют функции Oracle и .
Доказательство
  1. (Эффективность) может использовать паралелльных (не адаптивных) запросов .
  2. (Полнота) может быть вычислена с помощью серий (адаптивных) запросов и выход всегда удовлетворяет ( детерминирована).
  3. (Прочность) для каждого Oracle функция состовляет менее N серий запросов на пол запросов в общей сложности , нег (где нег незначительная функция в )


Идея конструкции - заставить решается делать последовательные запросы «шифрования», каждый последующий запрос с результатом Oracal вызывает своего предшественника. Полная конструкция и её доказательство безопасности появится в Разделе 3.

Связанное с работой

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

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

Головоломки. Термин «головоломки» описывающий криптографическую конструкцию как «значит сломать» был впервые использован Мерклом в контексте соглашений протоколов ключей[5]. Протокол Меркля обмена ключами позволяет двум пользователям обмениваться ключом от решения одной головоломки, в то время, как заставляет противника решить множество головоломок, что бы обнаружить его. Протокол не требует большой структуры из головоломок, и может быть реализован с черным ящиком использующим односторонние функции. Разрыв между вычислениями честных пользователей и противником является квадратичной в схеме Меркл: если честный пользователь требует времени, чтобы восстановить ключ, злоумышленник может восстановить его в времени.

Барак и Махмуд показали, что это по существу оптимально[13], улучшив предыдущий результат Импальяццо и Рудич[15]. Обе эти работы дают верхнюю границу для вычисления промежутка произвольных протоколов обмена ключами в модели случайного Oracle (в том числе протоколов, которые требуют нескольких раундов взаимодействия между двумя честными сторонами). Наша работа рассматривает только протоколы одного сообщения, но ограничивает параллельную сложность противника (в отличии [[15],[13]], которые анализируют сложность последовательных противников).

Головоломки так же были предложены в качестве доказательства правильности работы механизмов для управления спама и предотвращения отказа в обслуживании атак. Идея была впервые введена Двором и Набором [16], и разработана в нескольких последующих работах [[17],[18],[19],[20]]. Ривест и Шамир даже предположите один вариант для использования в качестве системы микроплатежей[21].

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

Для обоих типов головоломок, все еще важно учитывать разрыв между вычислительной мощности честного пользователя и противника. Абади, Берроуз, Манассе и Воблер предлагают основу трудности головоломки на время доступа к памяти [17], в предположении, что это имеет меньшую дисперсию среди пользователей, чем скорость процессора. В последующей работе, Дворк, Голдберг и Наор [19] построят такую функцию в модели случайного Oracle, который использует "указатель" в большойслучайной таблице. Это имеет очень похожую изюминку нашей конструкции головоломки блокирующее время в Разделе 3, хотя цель несколько иная и анализ фокусируется на ограничении доступа к памяти (в таблице), а не слоями адаптивности или запросами к случайному Oracle.

Отрицательные результаты для Головоломок блокирующее время

В этом разделе мы даем понимание доказательств основных результатов (Теорем 1 и 2), а так же полное доказательство Теоремы 2.

После основополагающей работы Импальяццо и Рудич [15] по протоколам ключа соглашения в модели случайного Oracle, наши противники (для обеих теорем) пытаются найти все пересечения запросов между генератором головоломки (Алиса) и решателем (Боб) - все запросы сделаны Алисой и Бобом. В случае успеха, противник может имитировать честного решателя, не спрашивая дополнительных запросов. Новизна нашей работы в том, что мы заботимся не только о общем числе запросов, сделанных противником, но и о количестве уровней адаптивности.

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

Изъяснение в Теореме 1

Для доказательства Теоремы 1 мы используем идеи (и конструкции) Импальяццо и Рудич [15] (и более поздние усовершенствования от Барака и Махмуда [13]), но измененные, чтобы свести к минимуму количество раундов запросов, используемых противником. Нош злоумышленник, Плющ, выбирает ее запросы в случайном Oracle в раундов ( числа запросов, сделанных Алисой). В первом раунде , Плющ вычисляет набор тяжелых запросов, на которых она будет запрашивать Oracle в конце раунда. Тяжелыми запросами являются те, которые имеют высокую вероятность (по мнению Айва) того, что были сделаны сделаны Алисой, где «высота» является параметром, который зависит от , (число запросов, сделанных честным решателем) и (вероятность с которой Айв потерпит неудачу).

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

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

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

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

Доказательство для Теоремы 2

Хавьер, противник, сконструированный в доказательстве Теоремы 2, работает, выполняя честные решения в каждом раунде, но заменяя свои запросы к случайной модели oracle (так что никаких запросов не делаются к реальному oracle во время исполнения). После моделирования Хавьер обновляет имитацию oracle, запрашивая реального oracle (паралелльно) на каждый индекс, который был запрошен во время имитации исполнения. Основная идея в доказательстве этого. так как генератор головоломки запрашивает только запросов,может быть большинство раундов в которых моделируемое выполнения «хитов» это пересечение запроса, которого не было уже известным Хавьеру. В остальных раундах Хавьер знает все пересечения запросов и, следовательно, имитация решателя будет вести себя так же, как реальный честный решатель (и выводиить правильное решения головоломки с той же вероятностью). Формально:

Доказательство (из Теоремы 2). Противник Хавьер следует описанному алгоритму Алг.1, есть множество запросов Хавьера для до (но не включая) раунда , в то время как есть множество запросов имитирующих Боба для Хавьера раунда.

Алгоритм 1 Хавьер запрашивает сообщение  и  oracle с параметром  
1: Случайный выбор 
2: для 
3: выполнив это, Боб получает:  где H_i это oracle, отвечающий на любой запрос  
   так же, как , и  отвечает на все новые запросы  с равномерной случайностью.
4: Запрос  по всем индексам в , где  это запрос Боба, внесенный в .
5: Выход .

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

Обозначим событие выхода Хавьера применением решения валидатора:

.

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

 
              
             
             
             

Головоломки блокирующие время с разрывом линейной сложности

В этом разделе мы дадим конструкцию и доказательство для Теоремы 3.

В приведенном ниже описании мы опустим параметр безопасности : параметр безопасности используется только для определения диапазона случайного oracle - мы предполагаем, что w.l.o.g. это возвращает бит (если oracle возвращает меньшее количество бит, мы можем интерпретировать запрос как объединения нескольких запросов (например, ). Для дальнейшего упрощения обозначений, наше определение генерирует только сообщение M. Решение валидатора (неявного) проверяет его вход равному входу (наше обоснование доказательства намного сильнее - мы показываем, что не противник делаея не менее серий раундов запросов может найти любой действительный прообраз при ).

Определим генерирующую головоломку функцию :

(где вход интерпретируется как индексов запроса)

Честный решатель инвертирует запустив Алгоритм 2:

Доказательство (Теоремы 3). По обследованию, может быть вычислена с неадаптивными запросами: значения могут быть получены параллельно. Правильность честного инвертора (Алг. 2) и то, что он использует серийные запросы также легко увидеть.

Алгоритм 2 Честный решатель , на входе  и oracle 
1:  // не "зашифровано"
2: для {} делаем
3:  // "расшифровка"  требует запрос oracle на индекс .
4: Выход 

Основная часть доказательства показывает, что каждый инвертор делая запросов в , должен использовать по крайней мере раундов адаптивных запросов. Чтобы доказать это, мы сначала утвердим, что любой алгоритм, который выдает с непренебрежимой малой вероятностью должен запрашивать на . Это потому, что, даже вместе взятые, значение , значения {} \ {} и ответы случайного oracle на все вопросы, кроме не дают никакой информации (в теоретико-информационном смысле) о . Таким образом, вероятность того, что выходы алгоритма без запроса на незначительна в (размер выхода ). Обратите внимание, что это по-прежнему верно, если мы позволим, чтобы алгоритм выводил полиномиальное число догадок для .

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

Увеличение коэффициента вычисления/сообщения

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

Запрос. Для каждого oracle функция составляет менее серий раундов запросов Н и запрашивает общую , в общей сложности,

(где neg ничтожно мала в функции ).

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

Обсуждения и открытые вопросы

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

Одним из мотивов для изучения головоломки блокирующее время в модели случайного oracle, это поиск головоломок, которые устойчивы к квантовой атаке. В этом направлении по-прежнему остается работа, которую нужно сделать: на положительной стороне, наша конструкция не может быть в безопасности от противников с квантовым доступа к случайному oracle (например, Дагделен и др. показали протоколы, которые находятся в безопасности в модели случайного oracle, но может быть нарушен нападающим с квантовым доступом к случайному оракулу [22]). С другой стороны, когда квантовой на честной стороне, нижняя граница остается открытым вопросом, а также (Брассорд и Салвайл [23] и, независимо Бихам, и др [4], дают квантовый варианты головоломки Меркля, которые требуют противника сделать запросов для того, чтобы восстановить общий ключ, но не доказать оптимальность).

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

Мы благодарим анонимных рецензентов за полезные замечания и предложения.

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

1.Department of Computer Science, Cornell University mohammad@cs.cornell.edu; http://www.cs.cornell.edu/ ̃mohammad/
2.School of Engineering and Applied Sciences and Center for Research on Computation and Society, Harvard University {talm,salil}@seas.harvard.edu; http://seas.harvard.edu/ ̃{talm,salil}/

Примечание

  • Поддержка NSF grant CNS-0831289

Литература

  1. 1,0 1,1 T.C.May.Timed-releasecrypto.http://www.hks.net/cpunks/cpunks-0/1460.html, February 1993
  2. 2,0 2,1 2,2 R. L. Rivest, A. Shamir, and D. A. Wagner. Time-lock puzzles and timed-release crypto. Technical Report MIT/LCS/TR-684, MIT, February 1996
  3. 3,0 3,1 3,2 D. Boneh and M. Naor. Timed commitments. In CRYPTO ’00, volume 1880 of Lecture Notes in Computer Science, pages 236–254
  4. 4,0 4,1 4,2 E.Biham,Y.J.Goren,andY.Ishai.Basingweakpublic-keycryptographyonstrongone-way functions. In TCC ’08, volume 4948 of LNCS, pages 55–72
  5. 5,0 5,1 5,2 R. C. Merkle. Secure communications over insecure channels. Commun. ACM, 21(4):294– 299, 1978
  6. L.K.Grover.Afastquantummechanicalalgorithmfordatabasesearch.InSTOC’96,pages 212–219. ACM
  7. 7,0 7,1 J. Cathalo, B. Libert, and J.-J. Quisquater. Efficient and non-interactive timed-release en- cryption. In ICICS, volume 3783 of LNCS, pages 291–303, 2005
  8. R.Canetti,O.Goldreich,andS.Halevi.Therandomoraclemethodology,revisited.J.ACM, 51(4):557–594, 2004
  9. 9,0 9,1 D. Boneh and M. K. Franklin. Identity-based encryption from the weil pairing. SIAM J. Comput., 32(3):586–615, 2003
  10. R. Canetti, S. Halevi, and J. Katz. A forward-secure public-key encryption scheme. In EUROCRYPT ’03, volume 2656 of LNCS, pages 255–271
  11. D. Boneh and X. Boyen. Efficient selective-id secure identity-based encryption without random oracles. In EUROCRYPT ’04, volume 3027 of LNCS, pages 223–238
  12. D. Boneh and X. Boyen. Secure identity based encryption without random oracles. In CRYPTO ’04, volume 3152 of LNCS, pages 443–459
  13. 13,0 13,1 13,2 13,3 13,4 B.BarakandM.Mahmoody.Merklepuzzlesareoptimal-anO(n2)-queryattackonanykey exchange from a random oracle. In CRYPTO ’09, volume 5677 of LNCS, pages 374–390
  14. G. D. Crescenzo, R. Ostrovsky, and S. Rajagopalan. Conditional oblivious transfer and timed-release encryption. In EUROCRYPT ’99, volume 1592 of LNCS, pages 74–89
  15. 15,0 15,1 15,2 15,3 R. Impagliazzo and S. Rudich. Limits on the provable consequences of one-way permuta- tions. In STOC ’89, pages 44–61. ACM
  16. C. Dwork and M. Naor. Pricing via processing or combatting junk mail. In CRYPTO ’92, volume 740 of LNCS, pages 139–147
  17. 17,0 17,1 M. Abadi, M. Burrows, M. S. Manasse, and T. Wobber. Moderately hard, memory-bound functions. ACM Trans. Internet Techn., 5(2):299–327, 2005
  18. A.Back.Hashcash—adenialofservicecounter-measure,2002.http://www.hashcash. org/papers/hashcash.pdf
  19. 19,0 19,1 C. Dwork, A. Goldberg, and M. Naor. On memory-bound functions for fighting spam. In CRYPTO ’03, volume 2729 of LNCS, pages 426–444
  20. C. Dwork, M. Naor, and H. Wee. Pebbling and proofs of work. In CRYPTO ’05, volume 3621 of LNCS, pages 37–54
  21. R. L. Rivest and A. Shamir. Payword and micromint: Two simple micropayment schemes. In Security Protocols Workshop, volume 1189 of LNCS, pages 69–87, 1996
  22. O. Dagdelen, M. Fischlin, A. Lehmann, and C. Scha↵ner. Random oracles in a quantum world. Cryptology ePrint Archive, Report 2010/428, 2010. http://eprint.iacr.org/ 2010/428.pdf
  23. G. Brassard and L. Salvail. Quantum merkle puzzles. In ICQNM, pages 76–79. IEEE Com- puter Society, 2008