Лемма разветвления

Лемма разветвления (Шаблон:Lang-en) — лемма в области криптографических исследований.

На практике, лемма разветвления широко используется для доказательства безопасности различных схем цифровой подписи и других криптографических конструкций на основе случайного оракулаШаблон:Sfn.

История

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

Лемма была позже обобщена Шаблон:Iw и Грегори Невеном.Шаблон:Sfn

Формулировка

Лемма разветвления (оригинальная)

Первоначальный вариант леммы Шаблон:Sfn, сформулированный и доказанный Поинтчевалом и Стерном, выглядит следующим образом:

Пусть $(G,\mathrm{\Sigma },V)$ — общая схема цифровой подписи с секретным параметром $k$. Пусть $A$ — вероятностная машина Тьюринга с некоторым полиномиальным временем работы, вход которой состоит только из открытых данных. Обозначим через $Q$ количество запросов, которые $A$ может задать случайному оракулу. Предположим, что в течение времени $T$, $A$ дает с вероятностью $\epsilon \ge \frac{7Q}{2^k}$, валидную подпись $(m,{\sigma }_1,h,{\sigma }_2)$. Тогда есть другая машина, которая имеет контроль над А и производит две валидные подписи $(m,{\sigma }_1,h,{\sigma }_2)$ и $(m,{\sigma }_1,h^{\prime },{\sigma }_{2^{\prime }})$ такие, что $h\ne h^{\prime }$ за ожидаемое время $T_0\le \frac{84480TQ}{\epsilon }$.

Обобщенная лемма разветвления

Также существует обобщенный вариант этой леммыШаблон:Sfn , сформулированный и доказанный Белларом и Невеном. В отличие от классического варианта леммы Поинтчевала и Стерна, обобщенная лемма оперирует не со схемами подписей и случайными оракулами, а скорее концентрируется на выходном поведении алгоритма, когда он запускается дважды на связанных входах. Это делает её легко применимой в контекстах, отличных от стандартных схем подписи, и отделяет вероятностный анализ от фактического моделирования в доказательстве безопасности, что позволяет использовать более легкие для проверки доказательства. Для понимания связи между леммами следует воспринимать $x$ как открытый ключ и набор чисел $(h_1,\mathrm{...},h_q)$ как ответы на запросы случайного оракула.
Формулировка обобщенной леммы разветвления:

Зафиксируем целое число $q\ge 1$ и набор $H$ размером $h\ge 2$. Пусть $A$ — вероятностная машина Тьюринга, которая на вход получает набор $(x,h_1,\mathrm{...},h_q;r)$, где $r$ — случайная лента для $A$. Пусть $A$ возвращает пару $(J,y)$, где $J$ является целым числом в диапазоне $(0,\mathrm{...},q)$, а второй элемент называется побочным выводом. Предположим далее, что $IG$ — это распределение вероятностей, из которого берется $x$. Вероятность принятия $A$ обозначаемая $acc$, определяется как вероятность того, что $J\ge 1$ в эксперименте

$\text{x ← IG; }{h}_1,\mathrm{...},h_q\text{ ← H; (J,σ) ←}A(x,h_1,\mathrm{...},h_q)$

Определим «алгоритм разветвления» $F_A$ для заданной машины Тьюринга A, который принимает входные данные $x$, следующим образомШаблон:Sfn:

1. Выберем случайную ленту $r$ для $A$.
2. Выберем $h_1,\mathrm{...},h_q$ равномерно из $H$.
3. Запустим $A$ c набором $(h_1,\mathrm{...},h_q;r)$ на входе, чтобы получить набор $(J,y)$.
4. Если $J=0$, то вернуть $(0,0,0)$.
5. Выберем $h_{1^{\prime }},\mathrm{...},h_{q^{\prime }}$ равномерно из $H$.
6. Запустим A с набором $(x,h_1,\mathrm{...},h_{J-1},h_{J^{\prime }},\mathrm{...},h_{q^{\prime }};r)$ на входе, чтобы получить набор $(J^{\prime },y^{\prime })$.
7. Если $J^{\prime }=J$ и $h_J\ne h_{J^{\prime }}$, вернуть $(1,y,y^{\prime })$, в противном случае вернуть $(0,0,0)$.

Пусть $frk$ будет вероятностью того, что $F_A$ выдает тройной результат, начиная с 1, при условии, что вход $x$ выбран произвольно из $IG$:

$\text{frk}=Pr[\text{b=1: x ← IG; (b, σ, σ′) ← }{F}_A(x)].$

Тогда:

$\text{frk}\ge \text{acc}\cdot (\frac{\text{acc}}{q}-\frac{1}{h})(1)$

Что равносильно

$\text{acc}\le (\frac{\text{q}}{h}+\sqrt{\text{q}\cdot \text{frk}})(2)$

Идея состоит в том, что A запускается два раза в связанных исполнениях, где процесс «разветвляется» в определённый момент, когда некоторые, но не все входные данные были исследованы. Точка, в которой процесс разветвляется, может быть тем, что мы хотим определить позже, возможно, основываясь на поведении A в первый раз: вот почему утверждение леммы выбирает точку ветвления $J$ на основании выходных данных A. Требование о том, что $h_J\ne h_{J^{\prime }}$ является техническим требованием, используемым многими леммами. (Обратите внимание, что поскольку $h_J$ и $h_{J^{\prime }}$ выбираются случайным образом из $H$, то, если $h$ большое, что нормально, вероятность того, что два этих значения не будут различаться, чрезвычайно мала.)

Пример

Например, пусть $A$ будет алгоритмом взлома схемы цифровой подписи в модели случайного оракула. Тогда $x$ будет открытым параметром (включая открытый ключ), который атакует $A$, а $h_i$ будет выводом случайного оракула на его $i$-й отдельный вход. Лемма разветвления полезна, когда было бы возможно, учитывая две разные случайные подписи одного и того же сообщения, решить некоторую сложную проблему. Однако противник, который подделывает один раз, порождает того, кто подделывает дважды одно и то же сообщение с немалой вероятностью благодаря лемме о разветвлении. Когда $A$ пытается подделать сообщение $m$, мы считаем вывод $A$ следующим образом $(J,y)$, где $y$ — подделка, а $J$ таков, что $m$ был $J$-м уникальным запросом к случайному оракулу (можно предположить, что $A$ запросит $m$ в некоторый момент, если $A$ должен быть успешным с незначительной вероятностью). (Если $A$ выдает неправильную подделку, мы считаем, что выходные данные $(0,y)$.)

По лемме разветвления вероятность $frk$ получения двух хороших подделок $y$ и $y^{\prime }$ для одного и того же сообщения, но с разными случайными выходами оракула (то есть $h_J$ ≠ $h_{J^{\prime }}$) не пренебрежимо мала, когда параметр $acc$ также не незначителен. Это позволяет нам доказать, что если основная сложная проблема действительно сложна, то никакой злоумышленник не может подделать подписи. В этом суть доказательства, данного Пойнтхевалом и Стерном для модифицированной схемы подписи Эль-ГамаляШаблон:Sfn.

Доказательство обобщенной леммы

ДокажемШаблон:Sfn сначала $\text{(1)}$, потом докажем что из $\text{(1)}$ следует $\text{(2)}$. Пусть для каждого $\text{x}$ величина $acc(x)$ будет обозначает вероятность того, что $J\ge 1$ в эксперименте

$h_1,\mathrm{...},h_q\text{ ← H; (J,σ) ←}A(x,h_1,\mathrm{...},h_q)$.

Также пусть $frk(x)=Pr[\text{b=1: (b, σ, σ′) ← }{F}_A(x)]$.
Мы утверждаем, что для любого $x,$

$frk(x)\ge acc(x)\cdot (\frac{acc(x)}{q}-\frac{1}{h})(3)$.

Затем, зная $\text{x ← IG}$ и с учетом что $E[acc(x)]=acc$, получаем

$frk=E[frk(x)]\ge E[acc(x)\cdot (\frac{acc(x)}{q}-\frac{1}{h})]=$

$=\frac{E[acc(x{)}^2]}{q}-\frac{E[acc(x)]}{h}\ge \frac{E[acc(x){]}^2}{q}-\frac{E[acc(x)]}{h}=acc\cdot (\frac{\text{acc}}{q}-\frac{1}{h}).$

Что доказывает $(1)$. Перейдем к доказательству утверждения $(3)$.
Для любого входа $x$ с вероятностями, взятыми из $F_A$, мы имеем

$frk(x)=Pr[I=I^{\prime }\wedge I\ge 1\wedge h_I\ne h_{I^{\prime }}]\ge Pr[I=I^{\prime }\wedge I\ge 1]-Pr[I\ge 1\wedge h_I\ne h_{I^{\prime }}]=$

$=Pr[I=I^{\prime }\wedge I\ge 1]-\frac{Pr[I\ge 1]}{h}=Pr[I=I^{\prime }\wedge I\ge 1]-\frac{acc(x)}{h}$

Осталось показать что $Pr[I=I^{\prime }\wedge I\ge 1]\ge \frac{acc(x{)}^2}{q}$.
Обозначим через $𝐑$ множество, в котором работает данная машина Тьюринга A.
Пусть для каждого $i\in \{1,\mathrm{...},q\}$ соответствующий $X_i:𝐑\times H^{i-1}\text{→ [0,1]}$ определяется значением $X_i(\rho ,h_1,\mathrm{...},h_{i-1})$ в

$Pr[J=i:h_1,\mathrm{...},h_q\text{ ← H; (J,σ) ←}A(x,h_1,\mathrm{...},h_q;\rho )]$ для всех $\rho \in 𝐑$ и $h_1,\mathrm{...},h_q\in H$.

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

$Pr[I=I^{\prime }\wedge I\ge 1]=\sum _{i=1}^{q}Pr[I=i\wedge I^{\prime }=i]=\sum _{i=1}^{q}Pr[I=i]\cdot Pr[I^{\prime }=i|I=i]=$

$=\sum _{i=1}^q\sum _{\rho ,h_1,\mathrm{...},h_{i-1}}{X}_i(\rho ,h_1,\mathrm{...},h_{i-1}{)}^2\cdot \frac{1}{|𝐑|\cdot |H{|}^{i-1}}=\sum _{i-1}^{q}E[X_i^2]\ge \sum _{i-1}^{q}E[X_i{]}^2$. Пусть $x_i=E[X_i]$ для $x\in 1,\mathrm{...},q$. Тогда
$\sum _{i=1}^{q}E[X_i{]}^2\ge \frac{1}{q}\cdot {(\sum _{i=1}^{q}E[X_i])}^2=\frac{1}{q}\cdot acc(x{)}^2.$ Это доказывает $(3)$, и, следовательно, $(1)$. Докажем теперь $(2)$. С учетом $(1)$ получим, что
${(acc-\frac{q}{2h})}^2=ac{c}^2-acc\cdot \frac{q}{h}+\frac{q^2}{4h^2}\le q\cdot frk+\frac{q^2}{4h^2}.$
Взяв с обеих сторон квадратный корень, и учтя, что

$\sqrt{a+b}\le \sqrt{a}+\sqrt{b}$ для любых вещественных $a,b\ge 0,$

получим:

$acc-\frac{q}{2h}\le \sqrt{q\cdot frk}+\sqrt{\frac{q^2}{4h^2}}=\sqrt{q\cdot frk}+\frac{q}{2h}$, откуда следует $(2)$.

Лемма доказана.

Известные проблемы с использованием леммы

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

Литература

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья