Головоломки Меркла в квантовом мире

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 11:45, 5 декабря 2015.
Merkle Puzzles in a Quantum World
Two-Output Secure Computation with Malicious Adversaries.png
Авторы Gilles Brassard[@: 1],
Peter Høyer[@: 2],

Kassem Kalach[@: 3],
Marc Kaplan[@: 4],
Sophie Laplante[@: 5] and
Louis Salvail[@: 6]

Опубликован 2011 г.
Сайт Department of Computer Science
Перевели Malik Safiev
Год перевода 2015 г.
Скачать оригинал
Аннотация. В 1974 году Ральф Меркл предложил первую открытую схему для безопасной связи через незащищенные каналы. Когда легитимные стороны готовы потратить вычислительные мощности, пропорциональные некоторому параметру , злоумышленник не сможет влезть в канал, не затратив время, пропорциональное , которое более квадратично, чем легитимные усилия. Мы показывали в предыдущей работе, что схемы Меркла полностью неустойчивы к квантовому противнику, но их безопасность может быть частично восстановлена, если законные стороны также могут использовать квантовые вычисления: злоумышленнику необходимо потратить время, пропорциональное , чтобы взломать нашу квантовую схему. Более того, все предыдущие классические схемы могут быть полностью взломаны натиском квантового противника, поэтому мы предположили, что данное неизбежно.
Мы представляем две новые ключевые схемы соглашения в Меркловском духе. Первая может быть взломана квантовым противником, который прикладывает усилие, пропорциональное для применения квантового случайного блуждания в графе Джонсона, напоминающего квантовый алгоритм Эндриса Амбаинса для проблемы четкости элемента. Данная атака оптимальна вплоть до логарифмических факторов. Наша вторая схема является чисто классической, но она не может быть взломана квантовым злоумышленником, который готов потратить только такие усилия, которые пропорциональны усилиям легитимных сторон.
Ключевые слова: Головоломки Меркла, Распределение Открытых Ключей, Квантовая Криптография.

Введение

В то время, когда Ральф Меркл представлял в 2005 году почетную лекцию Международной Ассоциации Криптографических Исследований (МАКИ) на ежегодной Крипто конференции в Санта-Барбаре, которая описывала его оригинальную неопубликованную схему 1974 года[1] для распределения открытых ключей (более простую и более элегантную, чем его впоследствии опубликованная, более известная как головоломки Меркла[2]), один из нас (Браззард) сразу понял, что эта схема полностью уязвима для злоумышленника, который обладает квантовым компьютером. Возник очевидный вопрос: могут ли идеи Меркла переработаны и стать безопасными снова уже в квантовом мире? Определяющими характеристиками протокола Меркла являются (1) Легитимные стороны общаются строго по аутентифицированному классическому каналу, на котором ведется неограниченное подслушивание и (2) Протокол считается безопасным, если злоумышленнику требуются такие криптоаналитические усилия, чтобы узнать ключ, которым обмениваются легитимные стороны, которые растут быстрее линейной функции с законной работой.

Мы частично переделали схему Меркла в работе [3] со схемой, в которой злоумышленнику необходим объем работы в , чтобы получить ключ, установленный квантовыми легитимными сторонами, чей объем работы равен O(N). Это не так хорошо, как работа в , необходимая классическому прослушивателю против оригинальной схемы Меркла, но значительно лучше чем работа в , достаточной для квантового злоумышленника против аналогичной схемы. Два вопроса остались открытыми в работе [3]:

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

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

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

Перед тем, как описать наши новые протоколы (Главы 3 и 4), квантовые атаки против них (Разделы 3.1 и 4.1), доказательства оптимальности для этих атак (Разделы 3.2 и 4.2), и домыслы о существовании более лучших схем (Глава 5), мы начнем с обзора (взятой из работы [3] оригинальной идеей Меркла, ее краха против квантового злоумышленника, и нашего более раннего частичного квантового решения (Глава 2). Некоторые технические инструменты, требуемые для наших нападений, рассмотрены в приложении,и введены новые нижние оценки методов.

Оригинальная схема Меркла. Как ее взломать и как частично восстановить

Первый несекретный документ, когда-либо написанный, который вел распределение открытого ключа и криптографию открытого ключа, был проектным предложением, написанным Мерклом в 1974 году, когда он был студентом компьютерных курсов Лэнса Хоффмана по компьютерной безопасности в Калифорнийском университете, Беркли [1]. Хоффман отклонил данное предложение, и Меркл бросил курсы, но “продолжал работать над идеей” и в конечном счете издал ее как одну из большинства оригинальных криптографических работ во второй половине двадцатого века [2]. Схема Меркла в его опубликованной работе несколько отличалась от его оригинальной идеи 1974 года, но обе разделяют свойство, которое говорит о том, что они “вынуждают любого врага израсходовать объем работы, который увеличивается как квадрат работы, требуемой от двух [легитимных] сторон” [2]. Прошло 35 лет, прежде чем Боуи Барак и Махмуди-Гидери доказали, что данное квадратичное несоответствие между законными и мошенническими усилиями - самое лучшее в классическом мире [5].

В его выдающийся лекции Ошибка цитирования Отсутствует закрывающий тег </ref>! Вот его оригинальные машинописные слова:

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

Обсуждение: Нет, я не шучу.

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

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

Вскоре после того Витфилд Диффи и Мартин Хеллман открыли знаменитый метод для распределения открытого ключа, который делает криптоаналитическое усилие очевидно экспоненциально тяжелее, чем легитимное усилие [6]. Однако нет никакого доказательства, что схема Diffie-Hellman безопасна вообще, так как она полагается на предугаданную трудность извлечения дискретных логарифмов, и это предположение, обреченно на провал, когда квантовые компьютеры станут доступными. Напротив, подход Меркла предлагает доказуемую квадратичную безопасность против любого возможного классического нападения под единственным предположением, что не может быть инвертирован никакими другими средствами, кроме как исчерпывающим поиском.

Затем, мы объясняем, почему первоначальное предложение Меркла становится абсолютно небезопасным, если злоумышленник способен к квантовому вычислению (изданные “загадки” Меркла [2] одинаково небезопасны). Тогда мы делаем набросок протокола, согласно ссылке [3], который не полностью сломан. Это достигнуто, благодаря предоставлению похожих квантовых возможностей вычисления одной из легитимных сторон сообщения.

Квантовая атака и частичная защита от нее

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

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

Из точек в области существует ровно решений проблем нахождения так, что . Бобу достаточно применить BBHT обобщение [8] алгоритма Гравера [7], которое находит за вызовов (и поэтому на ). Боб отсылает обратно Алисе, которая знает значение , потому что она с осторожностью хранила свои случайно выбранные точки. Поэтому достаточно вызовов Алисой и Бобом, чтобы договориться о ключе .

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

Улучшенная схема распределения ключей

Для любого положительного целого числа , обозначим как набор целых чисел от 1 до . Мы описываем наш новый протокол распределения ключей, принимающий существование двух черных ящиков случайных функций и , к которым можно получить доступ в квантовой суперпозиции входов. Константы и выбраны достаточно большие для того, чтобы не было никаких коллизий по образам и , не считая незначительной вероятности. (Для простоты мы будем систематически игнорировать возможность существования таких коллизий). Заметьте, что единственный бинарный случайный оракул (который “осуществляет” случайную функцию от целых чисел {0, 1}) может использоваться, чтобы определять обе функции и , если мы игнорируем логарифмические факторы в наших исследованиях, так как вызовов к случайному оракулу достаточно, чтобы вычислить или на любом единственном входе. Поэтому подразумевается в дальнейшем, что все наши результаты неявно заявлены “до логарифмических факторов”. Как упомянуто в предыдущем разделе, единственный ресурс, который мы рассматриваем в наших исследованиях эффективности и нижних оценок - это число вызовов, сделанных к этим функциям или, что тоже самое, к основному бинарному случайному оракулу.

TemplateDifinitionIcon.svg Определение «Протокол 1.»
  1. Алиса выбирает на случайном различные значения , где и передает зашифрованные значения Бобу. Обозначим и и соответственно. Заметим, что Алиса знает и в то время как Боб и злоумышленник непосредственно знают (то есть без обращения к черному ящику для функции ) только .
  2. Боб находит прообразы и от двух различных случайных элементов из . Чтобы найти каждый из них, он использует BBHT [8], чтобы найти таким образом, что , где определен следующим образом:
    Существует ровно значений таких, что из точек в области . Поэтому Боб может найти одно такое случайное за обращений к функции . Ему необходимо повторить этот процесс дважды, чтобы получить и (Маленькое изменение в функции может использоваться во второй раз, чтобы удостовериться что ).
  3. Боб высылает обратно Алисе.
  4. Поскольку Алиса держит в тайне случайно выбранный установленный , то существует только таких пар кандидатов , что равно . Используя алгоритм Гровера, она может найти пару , которую задумал Боб, за вызовов функции .
  5. Пара является общим ключом Алисы и Боба.

Все посчитав, Алиса делает вызовов на шаге 1 и вызовов на шаге 4, тогда как Боб делает обращений к на шаге 2 и единственное обращение к на шаге 3. Если протокол построен по бинарному случайному оракулу, его придется вызвать раз, так как необходимо бинарных запросов, чтобы вычислить любую функцию на любом данном входе.

Квантовая Атака

Все очевидные (и не столь очевидные) криптоаналитические нападения на эту схему, такие как прямое использование алгоритма Гровера (или BBHT), или еще более сложные нападения, основанные на увеличении амплитуды [10], требуют, чтобы злоумышленник вызвал раз функции и/или . К сожалению, более сильное нападение, основанное на более свежей парадигме квантовых прогулок в цепях Маркова [11], позволяет злоумышленнику восстановить ключ Алисы и Боба за ожидаемые вызовов и вызовов g. Это нападение было вдохновлено квантовым алгоритмом Амбэйниса для определенности элемента [4], который может найти уникальную пару таким образом, что за ожидаемых запросов к функции единственного столкновения , чья область содержит элементы (тогда как все предыдущие подходы, основанные на алгоритме Гровера и увеличении амплитуды [12,9], потребовали запросов).

TemplateTheoremIcon.svg Теорема Теорема 1.
Существует подслушивающая стратегия, которая производит пару в Протоколе 1 за ожидаемые квантовых запросов к функциям и .
Доказательство
Короче говоря, мы применяем алгоритм Амбэйниса для определенности элемента с двумя модификациями: (1) вместо того, чтобы искать и , таким образом, что , мы ищем и таким образом, что и (2) вместо того, чтобы получить случайные выбранные значения по образу с единственным требованием к оракулу за значение, мы должны получить случайные элементы , применив BBHT на список , который требует вызовов к оракулу за элемент. Вторая модификация объясняет, почему число вызовов к , по сравнению с вызовов к для определенности элемента, умножено на . Следовательно, нам нужно вызовов функции . Чтобы определить число требуемых вызовов функции , мы должны углубится в алгоритм подслушивания.

Алгоритм подслушивания использует квантовое блуждание на графе Джонсона — посмотрите Приложение для обзора этой темы. Каждый узел графа содержит некоторое число (будет определено позже) различных элементов из . Мы ищем узел, который содержит эти два элемента и таким образом что , где значение, объявленное Бобом на третьем шаге протокола. Мы применяем Теорему 5 (Приложение), чтобы проанализировать стоимость квантового блуждания на этом графе [2, 17]. Набор стоимостью соответствует нахождению случайных элементов из . Так как BBHT может использоваться для одного такого элемента за вызовов , и даже найти элемент из , который гарантированно отличается от уже тех, которые есть в начальном узле (если ), то вызовов f. Стоимость обновления соответствует нахождению одного случайного элемента из не в узле, который вызовов к , снова с помощью BBHT. Проверочная стоимость требует от нас решить, есть ли пара элементов в узле такая, что , которая может быть получена за вызовов к , используя алгоритм Гровера, так как есть пар элементов в узле. Собрав все вместе, ожидаемая криптоаналитическая стоимость составит:


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

Заметим, что использование алгоритма Гровера в шаге проверки не было необходимо, для доказательства Теоремы 1. Если этот шаг выполнен классически, это привело бы к вызовов к . Конечный результат состоял бы в том, что ключ найден после ожидаемых вызовов и также вызовов к .


Нижняя оценка

Доказательство оптимальности описанной выше квантовой атаки против нашего протокола состоит из 3 этапов.

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

Во-первых, рассмотрим функцию так, чтобы там существовала единственная пара, для которой . Квантовый алгоритм Амбэйниса для определенности элемента [4] может найти эту пару за запросов к функции , и Скотт Аэронсон, и Яоюнь Ши доказали, что это оптимально даже для решения варианта этой проблемы [12].

Теперь, рассмотрим функцию , где обозначает . Область этой функции составлена из “блоков” размера , где соответствует ’ому блоку, . В блоке , все значения функции равны 0 за исключением одного единственного случайного ,для которого :

Это следует из определений и , что есть единственная пара отличных и в области , такие что . Насколько трудно найти эту пару, выдаваемую черным ящиком для функции , но не прямым доступом к ?

TemplateTheoremIcon.svg Теорема Лемма 1.
Данный структурирован как выше, найдя пару различных элементов и в области таким образом, что требует квантовых запросов к , кроме незначительной вероятности.
Доказательство
Эта проблема может быть смоделирована как состав определенности элемента через блоки с нахождением единственного входа отличного от нуля в каждом блоке. Поэтому, это особый случай технической Леммы 5, заявленной в Приложении, с параметрами (число блоков) и (размер блоков). Из этого следует, что нахождение желаемой пары требует


квантовых запросов к , кроме незначительной вероятности


Рассмотрим теперь немного отличающуюся проблему поиска, в которой нет больше никаких блоков, но есть добавленная координата по образу функции: определенная так, что на всех кроме случайно выбранных точек в его области, а именно . На этих точках , где - функция, рассмотренная в начале этой главы. Мы обязаны считать уникальную пару различных и в [N^3] так, что , где "" обозначает проекцию на вторую координату (аналогично для ""). Нижняя оценка раней проблемы поиска касательно подразумевает непосредственно ту же нижнюю оценку для новой проблемы поиска относительно , так как любой алгоритм, способный к решению новой проблемы, может использоваться по той же самой стоимости, что и решение ранней проблемы через рандомизацию. Другими словами, более структурированная версия проблемы не может быть более сложнее, чем менее структурированная. Следующая Лемма формализует аргумент выше.

TemplateTheoremIcon.svg Теорема Лемма 2.
Данный структурированный как вышеуказанный, находя пару отличных элементов и в области таким образом, что требует квантовых запросов к , кроме незначительной вероятности.
Доказательство

Определим посредническую функцию так, что

Это элементарно - уменьшить проблему поиска касательно до той, которая относительно , также, как и проблема поиска относительно до той, которая относительно . Поэтому, нижняя оценка относительно , данная в Лемме 1, применяется с необходимыми изменениями к .


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

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

Мы начинаем, поставляя с абсолютно поддельным “разговором” между “Алисой” и “Бобом”: для достаточно большого и , мы случайно выбираем точек в и одну точку , и мы делаем вид, что Алиса послала Бобу, и что Боб ответил . Мы также выбираем случайные функции и , а также случайную Булеву переменную . Заметим, что выбор и может занять много времени, но это не учитывается числом запросов, которые будут сделаны из функции , и наша нижняя оценка проблемы поиска касается только количества запросов. Булева переменная указывает, когда истинно (resp. ложный), что поддельное “выполнение” таково, что “Боб” сначала выбрал и затем таким образом что (resp. ). Оба случая происходят с вероятностью равной в любом реальном выполнении и для любых открытых объявлений и . Значение s будет использоваться в сокращении, чтобы различить и так, чтобы только был установлен в .
Теперь, мы ждем запросов к и .

  • Когда просит для некоторых , есть два варианта:
    • Если , возвращаем к как значение для .
    • Иначе, возвращаем .
  • Когда просит для некоторых , снова есть два варианта.
    • Если и если верен, и или ложно и , то возвращаем как значения для .
    • Иначе, возвращаем .

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

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


Полностью классическая схема распределения ключей

В этой главе мы возвращаемся к оригинальной установке, предполагаемому Мерклом в том смысле, что Алиса и Боб теперь чисто классические. Однако мы позволяем полную квантовую силу злоумышленнику. Вспомните, что оригинальные схемы Меркла [1][2] полностью нарушены в этом контексте [3]. Возможно ли восстановить некоторую безопасность в этом очень соперничающем (и несправедливом!) сценарии? Следующий чисто классический протокол распределения ключей, который вдохновлен нашим квантовым протоколом, описанным в предыдущей главе, дает положительный ответ на эту загадку.

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

TemplateDifinitionIcon.svg Определение «Протокол 2.»
  1. Алиса выбирает случайно различных значений с и передает зашифрованные значения Бобу. Положим, что и обозначают и , соответственно.
  2. Боб находит прообразы и двух различных случайных элементов в . Чтобы найти каждый из них, он выбирает случайные значения из и применяет к ним, пока не будет найден тот, чей образ находится в . На основании парадокса дня рождения он, ожидает успеха после вызовов функции . До сих пор это идентично оригинальной схеме Меркла, за исключением факта, что Боб должен найти два элемента , а не один.
  3. Боб передает обратно Алисе. Кроме того, он выбирает случайных элементов из , и он формирует набор из количества элементов , добавляя и к этим элементам. Он посылает элементы к Алисе в возрастающем порядке значений.
  4. Поскольку Алиса сохраняла ее случайно выбранный набор , она знает прообразы каждого элемента . Обозначим . Исчерпывающим поиском по всем парам элементов Алиса находит одну пару такую, что .
  5. Ключ, разделенный Алисой и Бобом, является парой .

Все посчитав, Алисой сделала вызовов к на шаге 1 и при большинстве вызовов к в шаге 4, потому что есть пар элементов и один из них, является правильным. Что касается Боба, он делает ожидаемые вызовов к в шаге 2, и единственный вызов на шаге 3. Полное ожидаемое число вызовов к и находится поэтому в для обеих легитимных сторон.

Квантовая Атака

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

элементов (а не ). Злоумышленник может найти случайные элементы от его знания за ожидаемые

вызовов на элемент из . Поэтому, вызовов к , вызовов к и вызовов к . Кроме того, все еще , но . Соединив все это, ожидаемый квантовая криптоаналитическая стоимость составит:


.

Чтобы уменьшить число вызовов , мы выбираем такое, что , где . 
Это значит, что злоумышленник может найти ключ за ожидаемые вызовов к f и вызовов к .


Нижняя оценка

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

Мы отсылаем читателя к главе 3 за нотацией и разделу 3.2 для определений проекций , и значение нотации . Рассмотрим функцию такую, что существует единственная пара , , для которой . Нижняя оценка Ааронсона и Ши [12] говорит нам, что нахождение этой пары требует вызовов функции . Сейчас, рассмотрим функцию , где означает ’ый блок, . В блоке все значения функции равны 0 кроме одного: есть одно случайное такое, что . Это следует из определения и , что есть единственная пара различных и в области такие, что .

TemplateTheoremIcon.svg Теорема Лемма 3.
Данный структурировал как выше: нахождение пары различных элементов и в области </math>h</math>, такие что , требует квантовые запросов к , кроме незначительной вероятности.
Доказательство
Доказательство идентично доказательству Леммы 1, с соответствующими изменениями. Это снова особый случай Леммы 5, но с параметрами (количество блоков), и (размер блоков). Из этого следует, что нахождение желаемой пары требует


квантовых запросов к h, исключая небольшую вероятность.


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

TemplateTheoremIcon.svg Теорема Лемма 4.
Данный структурированный как выше: нахождение пары различных элементов и в области , такие что требует квантовых запросов , кроме незначительной вероятности.
Доказательство
Без доказательства.


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

TemplateTheoremIcon.svg Теорема Теорема 4.
Любая подслушивающая стратегия, которая возвращает ключ в протоколе 2, требует в общей сложности квантовых запросов к функциям и , кроме незначительной вероятности.
Доказательство
Рассмотрим любую подслушивающую стратегию , которая слушает общение между Алисой и Бобом и пытается определить ключ , запрашивая функции черного ящика и . Как прежде, у снижения нет доступа к Алисе и Бобу, но вместо этого есть к функции , описанной выше и данной как оракул, для которого мы хотим решить проблему поиска, используя как ресурс.

Мы выбираем случайные функции и так же, как и случайную булеву функцию , у которой есть та же самая цель как в доказательстве Теоремы 2. Обозначим как образ функции . Затем мы применяем с поддельным “разговором” между “Алисой” и “Бобом”: мы случайно выбираем точек в [N^k], точек в , и одна точка . Мы предполагаем, что Алиса послала список Бобу (в случайном порядке), и что Боб ответил (в увеличивающемся порядке) и .
Теперь, мы ожидаем запросы от к и

  • Когда спрашивает на нескольких , есть две возможности:
    • Если , возвращаем для (f^)(i) как значение для
    • В остальных случаях, возвращаем .
  • Когда спрашивает на нескольких , есть две возможности:
    • Если и любой есть истина и >math>i < j</math> или есть ложь и <math.i > j</math>, возвращаем как значение для
    • В остальных случаях, возвращаем .

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

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


Заключение, предположения и открытые вопросы

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

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

Наши нападения продолжаются квантовыми блужданиями в графах Джонсона, подобных тем, что использовали в доказательствах Теорем 1 и 3, чтобы получить оптимальные атаки на наши протоколы 1 и 2. Если они - самые лучшие против наших новых протоколов, то протоколы распределения ключей а-ля Меркл могут быть как угодно столь же безопасным в нашем квантовом мире, как они были в причудливом классическом мире, известной Мерклом в 1974: произвольно близкий к квадратичной безопасности может быть восстановлен. Очевидный нерешенный вопрос должен доказать оптимальность наших нападений. Также было бы интересно найти квантовый протокол, который точно достигает квадратичной безопасности... или лучше! Действительно, даже при том, что было доказано в классическом случае, что квадратичная безопасность является лучшей, которая может быть достигнута [5], еще нет никакого убедительного свидетельства того, что такое ограничение существует в квантовом мире.

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

Даже при том, что наши протоколы, и требуют, чтобы классическая Алиса получила доступ к функции случайного черного ящика только раз, она должна работать какое-то "время" в , чтобы закончить её долю протокола. (Это можно было уменьшить до для , если бы и Алис и Боб использовали квантовые вычислительные возможности, но это остается нелинейным как только . Могли ли подобные протоколы существовать, в которым Алиса будет эффективна даже вне необходимых требований к функции черного ящика?

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

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

Мы благодарны Troy Lee и Mohammad Mahmoody-Ghidary за проницательные обсуждения. Г. Б. также благодарен Ральфу Мерклу за его самую вдохновляющую, Выдающейся Лекцию в Крипто ’05, которая зажгла всю эту линию работы. Г.Б. поддержан частично Canada’s Natural Sciences and Engineering Research Council of Canada (Nserc), the Institut transdisciplinaire d’informatique quantique (Intriq), the Canada Research Chair program, the Canadian Institute for Advanced Research (Cifar) и сетью QuantumWorks. П.Х. поддержан частично Nserc, Cifar, QuantumWorks, и the Canadian Network Centres of Excellence for Mathematics of Information Technology and Complex Systems (Mitacs). С.Л. поддержан частично European Union 7th framework program Qcs, Anr Défis Qrac and Anr Jeune chercheur Cryq. L. S. поддержан частично Nserc, QuantumWorks, Fundamental Research on Quantum Networks и Cryptography (Frequency) and Intriq.

Приложение A Квантовая сложность запроса

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

Верхние оценки

Наши атаки могут быть смоделированы, как квантовая прогулка на графах Джонсона. Граф является неориентированным графом, в котором каждый узел содержит некоторый номер различных элементов и есть дуга между двумя узлами, если и только если они отличаются точно двумя элементами. Интуитивно, мы можем думать о “ходьбе” от одного узла до смежного узла, пропуская один элемент и заменяя его другим. Задача состоит в том, чтобы найти определенное -подмножество . Узлы, которые содержат это подмножество, называют отмеченными. Случайная прогулка на графе Джонсона может квантоваться, и стоимость получающегося квантового алгоритма может быть записана как функция S, U и C. Это затраты на подготовку квантового регистра в состояние, которое соответствует постоянному распределению, перемещающееся унитарно от одного узла до смежного узла, и проверяя, отмечен ли узел, чтобы изменить его фазу, если это, соответственно.

TemplateTheoremIcon.svg Теорема Теорема 5.
[4][11]Положим либо пустым, либо как набор вершин, которые содержат фиксированное подмножество постоянного размера . Тогда есть квантовый алгоритм, который находит с высокой вероятностью -подмножество, если не пуст по ожидаемой стоимости в порядке

где промежуток собственного значения симметричной прогулки на и - вероятность, что узел отмечен.
Доказательство
Без доказательства.


Нижние оценки

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

Рассмотрим два параметра целого числа и и три функции , , такие, что существует единственная пара , , для которой , что назывется коллизией, и


Задача состоит в том, чтобы найти уникальное непутевую коллизию в h, имея только доступ к черному ящику, который вычисляет h. Это может считаться ищущий среди β возможностей единственный h отличный от нуля (, ·) для каждого я и затем нахождение двух из тех элементов, среди α возможностей, которые не отличны. Наша главная техническая лемма, приведенная ниже, дает нижнюю оценку на требующееся число запросов h.

TemplateTheoremIcon.svg Теорема Лемма 5.
Нахождение ненулевой коллизии в , структурированной как выше, требует квантовых запросов к h, исключая незначительную вероятность.
Доказательство
Без доказательства.


Полное доказательство этой леммы появится отдельно, но сейчас сделаем его набросок. По техническим причинам, более удобно доказать эту нижнюю оценку для связанной проблемы решения: нам дают функцию h, приведенную выше, но она либо основана на функции , у которой есть единственная коллизия (как указано выше) или на один-к-одному функции c (когда h без коллизий, за исключением для нулевого значения в образе). Задача состоит в том, чтобы решить, что имеет место. Очевидно, любой алгоритм, который может решить проблему поиска с вероятностью успеха, по крайней мере, , может быть использован, чтобы решить проблему решения с ошибкой, ограниченной  : запускаем поисковый алгоритм; если коллизия найдена (и проверена), выводим “коллизия”, иначе выводим или “коллизия” или “нет коллизии” с равной вероятностью после броска справедливой монеты. Из этого следует, что любая нижняя оценка на проблему решения ограниченной ошибки, применяется одинаково хорошо и к проблеме поиска.

Снова по техническим причинам, мы изменим примечание, чтобы приспособить его к нормальному использованию в области квантовой сложности запроса. Например, функция будет представлена элементом . Это позволяет думать о версии решения отчетливости элемента как о Булевой функции ED: , хотя это - частичная функция, так как есть обещание на действительных входах к ED: Данные целые числа , обещание состоит в том, что либо все элементы различны; либо все элементы различны кроме двух, говоря что . Цель состоит в том, чтобы решить, какой из этих двух случаев происходит, делая как можно меньше запросов к функции, которая возвращает на входе .

Квантовый алгоритм отчетливости элемента Амбэйниса [4] работает в запросах на вход, и Аэронсон и Ши доказали, что это оптимально [12]. Хотя нижняя оценка была доказана с использованием полиномиального метода [13], текущая теорема [14] показывает, что обобщенная оценка злоумышленника трудна. Так как наше доказательство нижней оценки получено с использованием обобщенного антагонистического метода [15], мы можем прийти к заключению, что там существует оценка злоумышленника для отчетливости элемента.

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

Составленная функция, которую мы изучаем, является H ED pSEARCH. Мы теперь вновь заявляем об Лемме 5 в ее версии проблемы решения.

TemplateTheoremIcon.svg Теорема Лемма 6.
Квантовая сложность запроса H - .
Доказательство
Без доказательства.


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

TemplateDifinitionIcon.svg Определение «Определение 1.»
Зафиксируем функцию . Симметричная матрица - матрица злоумышленника для при условии, что , если . Положим . Оценка злоумышленника для c использованием составит

,

где обозначает !_! (или Адамара) продукт и обозначает спектральную норму (которая равна ее самому большому собственному значению). Оценка злоумышленника - максимум, по всем матрицам злоумышленника для , .

Так как определен как композиция и , хотелось бы применить теорему композиции для обобщенного метода злоумышленника [15], который скажет что, если функция , то (c точностью до постоянных множителей, которые больше не будут упоминаться). К сожалению, теорема композиции в [15] требует, чтобы внутренние и внешние функции были Булевыми, что не является здесь случаем для внутренней функции. (Фактически, внешняя функция не должна быть Булевой согласно Заключению 5.6 в [14], но нет никаких общих результатов, известных авторам, которые приводят к подобной теореме, когда внутренняя функция не Булева.) Тем не менее, мы все еще в состоянии доказать нижнюю оценку, используя методы из [15]. Хотя наша внутренняя функция не Булева, у нее такая структура, которая, оказывается, достаточна для доказательства по модулю некоторых модификаций, который мы кратко набросали здесь. (Для полной версии теоремы композиции мы отсылаем читателя к версии [15].) Наша цель состоит в том, чтобы построить матрицу злоумышленника , чтобы определить трудность применения к случаям . Напомним, что точна для сложности запроса, таким образом, мы знаем, что там существует матрица злоумышленника для которой . У нас нет явного выражения для этой матрицы, не говоря уже о ее спектральном разложении, но мы знаем, что она существует. Для внутренней проблемы мы строим матрицу злоумышленника, которую мы называем , чтобы сохранять совместимость с обозначениями из [15]. Мы можем проанализировать эту матрицу и дать ее явное спектральное разложение. Блочная конструкция матрицы и форма ее собственных значений ключевые для доказательства нижней оценки, таким образом, наше доказательство не держится для произвольных небулевых внутренних функций .

Есть две главных части к доказательству что . Сначала мы даем нижнюю оценку на , затем мы даем верхнюю оценку на для каждого .

TemplateDifinitionIcon.svg Определение «Утверждение.»
.

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

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

Для любого запроса мы анализируем его в индекс , в котором это происходит в пределах и индекса положения, подвергнутого сомнению в пределах . Затем разлагается естественно в две части, и .

TemplateDifinitionIcon.svg Определение «Утверждение.»
, который разлагается в ,
.

Объединяя два требования, мы добираемся

,

где обозначает квантовую сложность вопроса, и где заключительное неравенство следует из факта, что (ИЛИ) особый случай . Лемма следует при помощи известной квантовой сложности вопроса за более низкими границами для , который находится в [9], и для , который находится в [12].

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

  1. Département d’informatique et de recherche opérationnelle Université de Montréal, C.P. 6128, Succursale Centre-ville Montréal (QC), H3C 3J7 Canada
  2. Department of Computer Science, University of Calgary 2500 University Drive N.W., Calgary, AB, T2N 1N4 Canada
  3. Département d’informatique et de recherche opérationnelle Université de Montréal, C.P. 6128, Succursale Centre-ville Montréal (QC), H3C 3J7 Canada
  4. Département d’informatique et de recherche opérationnelle Université de Montréal, C.P. 6128, Succursale Centre-ville Montréal (QC), H3C 3J7 Canada
  5. LRI, Université Paris-Sud, 91400 Orsay, France
  6. Département d’informatique et de recherche opérationnelle Université de Montréal, C.P. 6128, Succursale Centre-ville Montréal (QC), H3C 3J7 Canada

Примечание

Литература

  1. 1,0 1,1 1,2 R. Merkle, “C.S. 244 Project Proposal”, 1974. Facsimile available at http://www.merkle.com/1974.
  2. 2,0 2,1 2,2 2,3 2,4 R. Merkle, “Secure communications over insecure channels”, Communications of the ACM 21(4):294–299, 1978.
  3. 3,0 3,1 3,2 3,3 3,4 G. Brassard and L. Salvail, “Quantum Merkle puzzles”, Proceedings of Second In- ternational Conference on Quantum, Nano, and Micro Technologies (ICQNM08), Sainte Luce, Martinique, February 2008, pp. 76–79.
  4. 4,0 4,1 4,2 4,3 4,4 A. Ambainis, “Quantum walk algorithm for element distinctness”, SIAM Journal on Computing 37:210–239, 2007.
  5. 5,0 5,1 B. Barak and M. Mahmoody–Ghidary, “Merkle puzzles are optimal — An O(n2)– query attack on any key exchange from a random oracle”, Advances in Cryptology – Proceedings of Crypto 2009, Santa Barbara, California, pp. 374–390, 2009.
  6. W. Diffie and M. E. Hellman, “New directions in cryptography”, IEEE Transac- tions on Information Theory 22(6):644–654, 1976.
  7. 7,0 7,1 L. K. Grover, “Quantum mechanics helps in searching for a needle in a haystack”, Physical Review Letters, 79(2):325–328, 1997.
  8. 8,0 8,1 M. Boyer, G. Brassard, P. Høyer and A. Tapp, “Tight bounds on quantum search- ing”, Fortschritte Der Physik 46:493–505, 1998.
  9. 9,0 9,1 C. H. Bennett, E. Bernstein, G. Brassard and U. V. Vazirani, “Strengths and weak- nesses of quantum computing”, SIAM Journal on Computing 26(5):1510–1523, 1997.
  10. G. Brassard, P. Høyer, M. Mosca and A. Tapp, “Quantum amplitude amplification and estimation”, in Quantum Computation and Quantum Information, Samuel J. Lomonaco, Jr. (editor), Contemporary Mathematics 305:53–74, AMS, 2002.
  11. 11,0 11,1 M. Sa ́ntha, “Quantum walk based search algorithms”, Proceedings of 5th Theory and Applications of Models of Computation (TAMC08), Xian, April 2008, LNCS 4978, pp. 31–46.
  12. 12,0 12,1 12,2 12,3 S. Aaronson and Y. Shi, “Quantum lower bounds for the collision and the element distinctness problems”, Journal of the ACM 51(4):595–605, 2004.
  13. R. Beals, H. Buhrman, R. Cleve, M. Mosca and R. de Wolf, “Quantum lower bounds by polynomials”, Journal of the ACM 48(4):778–797, 2001.
  14. 14,0 14,1 T. Lee, R. Mittal, B. W. Reichardt and R. Sˇpalek, “An adversary for algorithms”, http://arxiv.org/abs/1011.3020v1, 2010.
  15. 15,0 15,1 15,2 15,3 15,4 15,5 15,6 15,7 P. Høyer, T. Lee and R. Špalek, “Negative weights make adversaries stronger”, Proceedings of 39th Annual Symposium on Theory of Computing (STOC), June 2007, pp. 526–535. The complete version can be found at http://arxiv. org/abs/quant-ph/0611054v2.