Количественное приведение схемы идентификации Шнорра к DLP

Вопрос

я ищу количественно лучше доказательство теоремы 13.11 в работе Каца и Линделла. Введение в современную криптографию (3^рд версия) (или почти эквивалентно, теорема 19.1 в свободно доступной книге Дэна Боне и Виктора Шоупа). Высший курс прикладной криптографии). Доказательство относится к схеме идентификации Шнорра для группы общего положения. $\mathcal G$ первого порядка $q=\lvert\mathcal G\rvert$ и генератор $g\in\mathcal G$, для иска:

Если задача дискретного логарифмирования сложна относительно $\mathcal G$, то схема идентификации Шнорра безопасна.

Схема идет:

• Доказывающий (P) рисует закрытый ключ $x\gets\mathbb Z_q$, вычисляет и публикует открытый ключ $у:=г^х$, с предполагаемой целостностью.
• При каждой идентификации:
  1. Доказательство (P) рисует $k\gets\mathbb Z_q$, вычисляет и отправляет $I:=g^k$
  2. Верификатор (V) рисует и отправляет $r\gets\mathbb Z_q$
  3. Prover (P) вычисляет и отправляет $s:=r\,x+k\bmod q$
  4. Верификатор (V) проверяет, $g^s\;y^{-r}\;\overset?=\;I$

Доказательство дано от противного. Мы предполагаем алгоритм PPT $\математический А$ что, учитывая $у$ но нет $х$, успешно идентифицируется с ненулевой вероятностью. Построим следующий алгоритм PPT $\mathcal А'$:

1. Бег $\mathcal А(у)$, которому разрешено запрашивать и просматривать честные стенограммы $(я,р,с)$, прежде чем перейти к следующему шагу.
2. Когда $\математический А$ выходы $I$, выберите $r_1\gets\mathbb Z_q$ и дай это $\математический А$, который отвечает с $s_1$.
3. Бег $\mathcal А(у)$ второй раз с той же случайной лентой и честными расшифровками, а когда выводит (то же самое) $I$, выберите $r_2\gets\mathbb Z_q$ с $r_2\ne r_1$ и дать $r_2$ к $\математический А$.

   В итоге, $\математический А$, отвечает с $s_2$.

4. Вычислить $x:=(r_1-r_2)^{-1}(s_1-s_2)\bmod q$, решение ДЛП.

Скажем, шаг 2 завершается с вероятностью $\эпсилон$. Я понимаю, что доказательство книги устанавливает, что шаг 3 завершается с вероятностью не менее $\эпсилон^2-1/q$, почему шаг 4 решил DLP, почему $\эпсилон^2$ появляется и зачем нужен большой $q$ подойти к этому.

Можем ли мы достичь более убедительного количественного сокращения до DLP?

Неудовлетворительные вещи: $\эпсилон^2$, что может привести к низкой вероятности успеха. Нам бы хотелось, чтобы вероятность успеха росла линейно с затраченным временем для низкой вероятности. Также вероятность успеха получается усредненной по всем $y\in\mathcalG$, а не для конкретной проблемы DLP.

Чтобы конкретизировать первый вопрос: если $\математический А$ удается с вероятностью $\эпсилон=2^{-20}$ в $1$ во-вторых, доказательство говорит о том, что мы можем решить среднее DLP с такой вероятностью, как $2^{-40}$ в $2$ секунды. Это бесполезно напрямую, даже если бы мы могли превратить это в вероятность $1/2$ в $2^{40}$ секунд (11 вв.). Нам нужна вероятность $1/2$ в $2^{21}$ секунд (25 дней).

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

Это моя попытка, для критики. Я утверждаю, что мы можем решить любую конкретную DLP в $G$ с ожидаемым временем $2т/\эпсилон$ (и с вероятностью $>4/5$ вовремя $3т/\эпсилон$), плюс время на выявленные задачи, при условии алгоритма $\математический А$ которые идентифицируют случайный открытый ключ во времени $t$ с неисчезающей вероятностью $\эпсилон$, и $q$ достаточно большим, мы можем не учитывать попадание определенного значения в случайный выбор в $\mathbb Z_q$.

Заявленное доказательство:

Сначала мы строим новый алгоритм $\mathcal A_0$ что на входе описание настройки $(\mathcalG,g,q)$ и $h\in\mathcal G$

• равномерно случайно выбрать $u\gets\mathbb Z_q$
• вычисляет $y:=h\;g^u$
• работает алгоритм $\математический А$ с вводом $у$ служит случайным открытым ключом
• в любое время $\математический А$ запрашивает честную расшифровку $(я,р,с)$
  • равномерно случайно выбрать $r\gets\mathbb Z_q$ и $s\gets\mathbb Z_q$
  • вычислять $I:=g^s\;y^{-r}$
  • поставлять $(я,р,с)$ к $\математический А$, который отличается от честной расшифровки открытого ключа $у$
• если $\математический А$ выходы $I$ в течение выделенного времени выполнения $t$, попытка аутентификации
  • (примечание: мы начнем отсюда)
  • равномерно случайным образом выбирает $r\gets\mathbb Z_q$ и передает его $\математический А$
  • если $\математический А$ выходы $s$ в течение выделенного времени выполнения $t$
    • чеки $g^s\;y^{-r}\;\overset?=\;I$ и если да, то выводит $(т,р,с)$
    • в противном случае прерывается безрезультатно.

Алгоритм $\mathcal A_0$ это алгоритм PPT, который для любого фиксированного входа $h\in\mathcal G$ имеет при каждом прогоне вероятность $\эпсилон$ к выходу $(т,р,с)$, так как $\математический А$ выполняется в условиях, определяющих $\эпсилон$.

Делаем новый алгоритм $\mathcal A_1$ что при вводе настройки $(\mathcalG,g,q)$ и $h\in\mathcal G$

• Неоднократно запускать $\mathcal A_0$ с этим вводом, пока он не выводит $(и,r_1,s_1)$. Каждый запуск имеет вероятность $\эпсилон$ чтобы добиться успеха, поэтому ожидается, что этот шаг потребует $т/\эпсилон$ время работает $\математический А$.
• Рестарт $\mathcal A_0$ от отмеченной точки перезапуска (эквивалентно: перезапустите его с самого начала с тем же вводом и случайной лентой до точки перезапуска, с новой случайностью после точки перезапуска), пока он не выведет $(и,r_2,s_2)$. Каждый запуск имеет вероятность не менее $\эпсилон$ добиться успеха (доказательство следует из та теорема о неубывающей вероятности успеха алгоритма Я пытаюсь попросить ссылку), поэтому ожидается, что этот шаг потребует не более $т/\эпсилон$ время работает $\математический А$.
• В (предполагаемом чрезвычайно вероятном) случае $r_1\ne r_2$, вычислить и вывести $z:=s_1-s_2-u\bmod q$.

В этом случае обе серии $\mathcal A_0$ который произвел $(и,r_1,s_1)$ и $(и,r_2,s_2)$ проверили $g^{s_i}\;y^{-{r_i}}=I$ с $ у = ч ^ и $ для того же $u$ и $I$ что $\mathcal A_0$ определяется, и $ч$ мы дали при вводе $\mathcal A_1$. Следовательно $\mathcal A_1$ найденный $z$ с $ч=г^г$, тем самым решая ДЛП для произвольного $ч$. Это ожидаемое время работы, проведенное в $\математический А$ самое большее $2т/\эпсилон$, а остальное составляет $\mathcal O(\log(q))$ групповые операции для каждого запуска $\математический А$ и каждая честная расшифровка этого требует.

$\lfloor3/\эпсилон\rfloor$ прогоны $\математический А$ достаточно, чтобы по крайней мере два из них преуспели с вероятностью лучше, чем $1-4\,е^{-3}>4/5$: см. этот сюжет $1-(1-\epsilon)^{\lfloor3/\epsilon\rfloor}-\lfloor3/\epsilon\rfloor\,\epsilon\,(1-\epsilon)^{\lfloor3/\epsilon\rfloor-1} $

$ \ новая команда {\ sR} {\ mathcal {R}} \newcommand{\sG}{\mathcal{G}} \newcommand{\sB}{\mathcal{B}} $

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

(Приведенный ниже анализ относится к фиксированному экземпляру DLP, но идеи можно легко расширить.)

Лемма о расщеплении [лемма 1, PS]: Позволять $\sG\subseteq\sR_-\times\sR_+$ быть таким, что $$\Pr_{(\rho_-,\rho_+)\in\sR_-\times\sR_+}[(\rho_-,\rho_+)\in\sG]\geq\epsilon.$$ Для любой $\бета<\эпсилон$, определять $$\sB:=\left\{(\rho_-,\rho_+)\in\sR_-\times\sR_+:\Pr_{\rho_+'\in\sR_+}[(\rho_-,\ rho_+')\in\sG\right\}.$$ Справедливо следующее:

1. $\Pr[\sB|\sG]\geq\beta/\epsilon$ и
2. $\Pr_{\rho_+'\in\sR_+}[(\rho_-,\rho_+')\in\sG|(\rho_-,\rho_+)\in\sB]\geq \epsilon-\ бета.$

Здесь, $\sG$ представляет собой набор «хороших» случайных монет в том смысле, что они приводят к успеху противника и $\sB\subseteq\sG$ является подмножеством «лучших» случайных монет в том смысле, что перемотка и повтор с использованием этих монет, вероятно, будут успешными. Первый вывод леммы состоит в том, что хорошие монеты лучше с вероятностью не менее $\бета/\эпсилон$ и второй вывод заключается в том, что повторная выборка лучшей монеты приведет к хорошей монете с вероятностью не менее $\эпсилон-\бета$.

Анализ первой части редукции прост: вероятность того, что все $1/\эпсилон$ казни терпят неудачу $1-(1-\эпсилон)^{1/\эпсилон}$. Предположим, wlog, что последнее выполнение удалось. Обозначим монеты, использованные противником в этом исполнении до и после точки перемотки, через $\ро_-$ и $\ро_+$, соответственно. По лемме о расщеплении вероятность того, что хотя бы один из повторов будет успешным, равна $$\frac{\beta}{\epsilon}\left((1-(1-(\epsilon-\beta))^{1/\epsilon}\right).$$ Здесь, $\бета/\эпсилон$ есть вероятность того, что последнее исполнение (о котором мы знаем, что оно хорошее) лучше (по заключению $1$) и $(\эпсилон-\бета)$ внутри фигурных скобок вероятность того, что повторная выборка лучшей монеты приведет к хорошей монете (по заключению $2$).

Чтобы оптимизировать приведенное выше уравнение, установите $\бета=\эпсилон(1-\эпсилон)$ (что близко к $\эпсилон$). Это дает вероятность успеха $(1-\эпсилон)(1-(1-\эпсилон^2)^{1/\эпсилон})$.

[PS]: Пойнтшеваль и Стерн, Аргументы безопасности для цифровых подписей и слепых подписей, ДжоК 2000.

Попробую ответить на ваш вопрос :)

Во-первых, судя по вашему описанию (упомянутой вами книги у меня не было), этот вопрос относится к доказуемой теории безопасности. Общая идея доказуемой безопасности такова: если предположить, что существует алгоритм/противник А может сломать криптографическую схему с немалой вероятностью е, затем симулятор/челленджер С может решить экземпляр математической задачи, на которой основана схема, взаимодействуя с А с незначительной вероятностью **е' <= е** определяется вероятностью отказа.

Более того, процесс подтверждения безопасности должен основываться на игре/модели атаки злоумышленника, такой как IND-CPA, EUF-CMA и т. д., которая определяет возможности злоумышленника в этой конкретной модели. Итак, я думаю, что доказательство, данное в вашей части вопроса, было основано на EUF-DCMA, а доказательство в вашей части ответа было основано на EUF-CMA.

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

Теперь давайте посмотрим на оригинальное доказательство. Для решения DLP симулятор перематывает А в шаг 3. Это А запускался дважды, поэтому вероятность успешного извлечения Икс является $е'=е*е=е^2$, поскольку это непрерывное событие. Кроме того, на шаге 3 вероятность $r_1=r_2$ является $1/к$. Значит, нам тоже нужно минусовать $1/к$ чтобы зафиксировать окончательную успешную вероятность $e'=e^2-1/q$.

Процесс доказательства безопасности — это своего рода мысленный эксперимент, как Кот Шредингера (может быть, и неуместный), нам не нужно превращать его в реальный эксперимент. Достаточно просто свести безопасность схемы к одной или нескольким сложным проблемам.

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