Неклонируемое неинтерактивное нулевое знание в модели квантового случайного оракула

Таблица ссылок

Аннотация и введение

Технический обзор

Предварительные сведения

Неклонируемые неинтерактивные технологии с нулевым разглашением в модели CRS

Неклонируемый НИЗК в модели Quantum Ramdon Oracle

Неклонируемые сигнатуры знаний

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

5. Неклонируемый НИЗК в модели квантового случайного оракула

5.1 Модифицированный протокол Sigma

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

Доказательство. Совершенная полнота Это непосредственно следует из совершенной полноты П.

и любой x с ассоциированным λ ∈ N, удовлетворяющим

у нас есть

Мы определяем Ext 3 с доступом оракула к Π.Ext и некоторому A следующим образом:

Вход: х, С.

(1) Учитывая (x, α, s) из AΠ: отправьте α в Π.Ext, получите β от Π.Ext и отправьте β в AΠ.

(2) После получения γ от AΠ: отправьте γ на Π.Ext.

(3) Выведите результат Π.Ext как w.

Определим следующий набор параметров: c = cΠ, p(·) = pΠ(·), negl0 (·) = negl0,Π(·) и negl1 (·) = negl1,Π(·).

Пусть дана квантовая схема полиномиального размера A = (A 0, A 1) и (x, S) такая, что

Теперь мы определяем AΠ = (A0,Π, A1,Π) с доступом оракула к A. A0,Π жестко связан с S, принимает входные данные x, отправляет (x, S) в A0, получает ((x, α, s ), |sti) из A0 и выходы (α, |sti). A1,Π жестко связан с S, принимает входные данные (x, |sti, β), отправляет ((x, S), |sti, β) в A1, получает γ от A1, выводит γ. По структуре нашего доказательства и определению нашего проверяющего это означает, что

что удовлетворяет ограничению в уравнении (15). Это означает, что в сочетании с нашим определением Ext мы имеем, что

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

Вычислительная честная проверка с нулевым разглашением с помощью квантового симулятора . Пусть Π.Sim — вычислительный квантовый симулятор с нулевым разглашением и честной верификацией для Π. Мы определяем Sim с доступом оракула к Π.Sim следующим образом:

Вход: х, С.

(1) Вычислить (α, β, γ) ← Π.Sim(1λ, x)

(2) Образцы из S.

(3) Выход ((x, α, s), β, γ).

Пусть даны полином p(·), квантовая схема D полиномиального размера, λ ∈ N и ((x, S), w) ∈ R такие, что

Определим сведение к свойству нулевого разглашения Π следующим образом:

Сокращение: к нулевому знанию Π при наличии доступа оракула к D.

Зашито с: x, S.

(1) Получите (реальные или смоделированные) (α, β, γ) от претендента.

(2) Образцы из S.

(3) Отправьте ((x, α, s), β, γ) в D. Получите b от D.

(4) Выход b.

Когда претендент отправляет реальное (или смоделированное) доказательство для Π, приведение генерирует доказательство, идентичное реальному (соответственно смоделированному) доказательству. По сути, это сокращение сохраняет отличительное преимущество D . Это приводит к противоречию со свойством нулевого разглашения Π. Следовательно, наш протокол должен быть с нулевым разглашением.

По определению честного доказывающего P.Com,

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

Следствие 5.2. Эвристика Фиата-Шамира, примененная к постквантовому сигма-протоколу, определенному в теореме 5.1, дает классический постквантовый NIZKPoK Π' в QROM (определение 3.11).

Доказательство . Это следует из теоремы 5.1 и теоремы 3.12.

5.2 Определения неклонируемости

Неклонируемые NIZK в модели квантового случайного оракула определяются аналогично модели CRS – для полноты мы повторяем эти определения в модели QRO.

Определение 5.3. (Неклонируемая безопасность для жестких экземпляров). Доказательство (P,V) удовлетворяет неклонируемой безопасности по отношению к квантовому случайному оракулу O, если для каждого языка L с соответствующим отношением RL, для каждого семейства квантовых схем полиномиального размера {Cλ}λεN и для каждого жесткого распределения {Xλ ,Wλ}λεN над RL, существует пренебрежимо малая функция negl1 (·) такая, что для любого λ ∈ N

Определение 5.4 ((k-1)-в-k-неклонируемый извлекаемый NIZK в QROM). Пусть задан параметр безопасности λ ∈ N и NP-отношение R с соответствующим языком L. Пусть Π = (P,V) задано так, что P и V являются квантовыми алгоритмами размера поли(λ). Мы имеем, что для любого (x, ω) ∈ R P получает пару экземпляров и свидетелей (x, ω) в качестве входных данных и выводит π, а V получает экземпляр x и доказательство π в качестве входных данных и выводит значение в {0, 1}.

Π является неинтерактивным (k - 1)-к-неклонируемым протоколом NIZKPoK для языка L относительно случайного оракула O, если выполняется следующее:

• Π — протокол NIZKPoK для языка L в модели квантового случайного оракула (определение 3.11).

• (k−1)-к-k-неклонируемое с извлечением: существует квантовая схема E полиномиального размера с помощью оракула такая, что для каждой квантовой схемы A полиномиального размера для каждого кортежа из k − 1 пар экземпляр-свидетель ( x1, ω1), . . . ,(xk−1, ωk−1) ∈ R для каждого x, где мы определяем

такой, что существует многочлен p(·), где

тогда существует также многочлен q (·) такой, что

Как и в предыдущем разделе, у нас есть следующая лемма.

Лемма 5.5. Пусть Π = (Setup, P,V) — неинтерактивный квантовый протокол с нулевым разглашением, не допускающий клонирования 1 к 2 (определение 5.4). Тогда Π удовлетворяет определению 5.3.

За доказательством леммы 5.5 мы отсылаем к приложению А.

5.3. Неклонируемость NIZK подразумевает квантовые деньги с открытым ключом в QROM

Теорема 5.6. Пусть O — квантовый случайный оракул. Пусть (X ,W) — жесткое распределение над языком L ∈ NP. Пусть Π = (P,V) — неклонируемый неинтерактивный совершенно полный протокол с нулевым разглашением данных для L в модели QRO (определение 5.4).

Тогда (P,V) подразумевает мини-схему квантовых денег с открытым ключом в модели QRO (определение 3.15), как описано на рисунке 4.

Доказательство . Совершенная корректность . Это следует непосредственно из совершенной полноты П. Неподделываемость. Пусть p(·) — полином, а A — квантовый противник с полиномиальным временем такой, что для бесконечного числа λ ∈ N +,

Мы создаем редукцию, которая нарушает определение неклонируемости (определение 5.3), которое, как мы показываем (в приложении А), подразумевается из нашего определения (определение 5.4). Претендент, имеющий доступ к случайному оракулу O, выбирает пару жестких экземпляров-свидетелей (x, w) ← (X, Y) и доказательство π ← PO(x, w). Затем претендент пересылает (x, π) в редукцию, которая также имеет доступ оракула к O. Тогда редукция устанавливает |$i = π и s = x. Сокращение отправляет (|$i, s) противнику A, который возвращает обратно (|$0, s0, |$1, s1). Затем сокращение анализирует и устанавливает πi = |$ii для i ∈ {0, 1}. Затем сокращение отправляет π0 и π1 обратно претенденту.

5.4 Построение и анализ

Лемма 5.7. Пусть λ, k ∈ N и задана мини-схема квантовых денег с открытым ключом ( NoteGen,Ver ). Пусть точки q1, . . . , qk со следующей структурой: точка q содержит порядковый номер s, выбранный в соответствии с NoteGen (1λ ).

Точки q1, . . . , qk должны быть различны с подавляющей вероятностью.

Доказательство . Каждая точка содержит серийный номер, выбранный в соответствии с алгоритмом генерации квантовых денег NoteGen (1λ). Из-за непредсказуемости серийных номеров квантовых денег (определение 3.13) все k честно сгенерированных серийных номеров должны быть различны с подавляющей вероятностью. Следовательно, эти k точек будут различны с подавляющей вероятностью.

Теперь представим нашу конструкцию на рис. 5 и докажем основную теорему этого раздела.

Теорема 5.8. Пусть k(·) – многочлен. Пусть дано NP-отношение R с соответствующим языком L.

Пусть ( NoteGen, Ver ) — мини-схема квантовых денег с открытым ключом (определение 3.13), а Π = (P,V) — постквантовый сигма-протокол (определение 3.4).

(P,V), как определено на рисунке 5, будет неинтерактивным звуком знания, с нулевым разглашением в вычислительном отношении и (k - 1)-к-неклонируемым с протоколом извлечения для L в квантовой случайной модели оракула (определение 3.11). ).

Доказательство. Пусть параметры и примитивы такие, как указано в формулировке теоремы. Мы утверждаем, что полнота следует из конструкции протокола, показанной на рисунке 5, а остальные свойства мы доказываем ниже.

у нас есть

Пусть заданы квантовые схемы A и x полиномиального размера такие, что

Пусть AF S определен с доступом оракула к некоторым A и O следующим образом:

Вход: х, С.

(1) Дан запрос (x, α, s) от A: отправьте (x, α, s) в O, получите β от O и отправьте β в A.

(2) При получении π = (|$i, s, α, β, γ) от A: вывести πF S = ((x, α, s), β, γ).

По структуре нашего доказательства и определению нашего проверяющего это означает, что

что удовлетворяет ограничению в уравнении (16). Это означает, что в сочетании с нашим определением Ext и S мы имеем, что

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

Нулевое знание. Пусть SimF S — симулятор Π′ из следствия 5.2 (где Π реализует теорему 5.1). Пусть RF S будет отношением для Π' относительно R. Мы определяем Sim с доступом оракула к SimF S и программным доступом к некоторому случайному оракулу O следующим образом:

Ввод: x (игнорирует любые свидетели, которые он может получить).

Пусть задан распознаватель D с помощью оракула, который может выполнять только запросы (x, w) ∈ R, и многочлен p(·) такой, что

Мы определяем сведение к свойству нулевого разглашения Π' следующим образом:

Сокращение: к нулевому разглашению Π' при условии доступа оракула к D и программного доступа к O.

Для каждого (x, w) из D:

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

Неклонируемая извлекаемость. Пусть Ext — квантовая схема экстрактора, который мы определили ранее (в нашем доказательстве того, что рисунок 5 является доказательством знаний). Пусть Sim — квантовая схема симулятора, которую мы определили ранее (в нашем доказательстве того, что рисунок 5 — это протокол с нулевым разглашением). Мы определяем экстрактор E с доступом оракула к некоторому A следующим образом:

Запрограммировано с: некоторый выбор I ⊆ [k − 1], J ⊆ [k], x1, . . . , xk−1 ∈ R, x.

(1) Выборки ℓ ∈ J равномерно случайны.

(2) Создает экземпляр моделируемого и извлекаемого случайного оракула O. Запускает Ext на O на протяжении всего взаимодействия с A (что может включать перемотку назад, и в этом случае мы перемотаем A назад и повторим следующие шаги). Требуйте, чтобы Ext извлекал данные по ℓ-му выводу доказательства, полученному A.

(3) Вычислить πι ← Sim(xι) для ι ∈ [k − 1], где мы сохраним все точки, которые Sim запрограммировал бы в список P.

(4) Отправьте {πι}ιε[k−1] в A.

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

(7) Выводит результат Ext как w.

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

Сценарий первый

Предположим, что A генерирует два принимающих доказательства, которые имеют тот же порядковый номер, что и честно созданное доказательство. Применяя объединение к уравнению (24), мы получаем, что это событие может произойти с вероятностью не менее 1/2p(λ). Символически,

Сценарий второй

В качестве альтернативы предположим, что A не генерирует два принимающих доказательства, которые имеют тот же порядковый номер, что и честно созданное доказательство. По принципу «ячейки» это означает, что A генерирует подтверждающее подтверждение с серийным номером, которого нет среди полученных им. Применяя объединение к уравнению (24), мы получаем, что это событие может произойти с вероятностью не менее 1/2p(λ). В общем, имеем вот это

Используя аргумент усреднения, мы можем зафиксировать индекс j ∈ J, что дает нам то же событие с преимуществом 1/(2kp(λ)). Теперь мы перейдем к гибридному варианту, в котором мы предоставим А смоделированные доказательства по индексам I.

Утверждение 5.9. Существует многочлен q (·) такой, что

Позже мы увидим доказательство утверждения 5.9. На данный момент, предполагая, что это утверждение справедливо, мы можем определить противника, от которого Ext может извлечь действительный свидетель для x.

Утверждение 5.10. Существует многочлен q ′ (·) такой, что

Вскоре мы увидим доказательство утверждения 5.10. Между тем, если это утверждение верно, то мы получим прямое противоречие с уравнением (19). Таким образом, все, что осталось доказать, — это два утверждения: утверждение 5.9 и утверждение 5.10. Начнем с доказательства первого утверждения.

Доказательство утверждения 5.9. Сначала нам нужно доказать, что наша стратегия четко определена, что мы сможем самостоятельно запрограммировать эти k точек. Тогда мы можем утверждать неотличимость перехода одного за другим к смоделированным доказательствам. Мы будем утверждать, что наш симулятор будет работать за ожидаемое полиномиальное время. По лемме 5.7 k точек, которые запрограммирует наш симулятор, будут с подавляющей вероятностью различны. Более того, поскольку мы предположили, что наш квантовый случайный оракул может быть запрограммирован в нескольких различных точках (Определение 3.10), наш симулятор четко определен.

Теперь мы доказываем неотличимость смоделированных доказательств от честно сгенерированных доказательств с помощью гибридного аргумента. Предположим, ради противоречия, что разность вероятностей между уравнением (21) и уравнением (22) составляла 1/p′ (λ) для некоторого многочлена p′ (·). Мы строим серию последовательных гибридов для каждого i ∈ [k − 1], где мы переключаем i-е доказательство с сгенерированного доказательства на моделируемое. Согласно этому гибридному аргументу, должна существовать некоторая позиция ℓ ∈ [k − 1], в которой переключение ℓ-го доказательства имеет разность вероятностей не менее 1/(kp′ (λ)). Теперь мы формализуем сокращение, которое может различать эти две настройки:

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

Учитывая, что A имеет вид, который напрямую соответствует его ожидаемому виду в любой игре, тогда преимущество сокращения такое же, как и преимущество A, которое составляет не менее 1/(kp' (λ)). Это противоречит свойству нулевого разглашения нашего протокола. Таким образом, наше первоначальное утверждение должно быть верным.

Теперь мы продолжим доказательство последнего утверждения.

Доказательство утверждения 5.10. Учитывая справедливость утверждения 5.9, отсюда следует, что

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

Используя уравнение (25), мы приходим к выводу, что

По определению доказательства знания (Определение 3.11), которое имеет некоторые параметры, полиномы p∗ (·) и пренебрежимо малые функции negl0 (·) и negl1 (·), мы имеем, что существует некоторый полином q ′ (·) такой, что

что завершает доказательство нашего утверждения.

Завершив доказательства наших утверждений, мы завершили доказательство утверждения нашей теоремы.

Следствие 5.11. Предполагая, что существуют инъективные односторонние функции и существует постквантовое iO, существует неинтерактивный звук знания, вычислительное нулевое знание и (k - 1)-клонируемое с протоколом извлечения для NP в квантовом случайном оракуле. модель (определение 5.4).

Доказательство. Это следует из теоремы 3.14 и теоремы 5.8.

Таким образом, мы показали, что рисунок 5 представляет собой неклонируемый NIZK PoK в модели ROM, как это определено в соответствии с нашим определением неклонируемости, Определение 5.4.