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

Лемма разветвления (англ. Forking lemma) — лемма в области криптографических исследований.

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

История

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

Лемма была позже обобщена Михиром Белларом и Грегори Невеном.

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

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

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

Пусть $(G,\Sigma ,V)$ — общая схема цифровой подписи с секретным параметром $k$. Пусть $A$ — вероятностная машина Тьюринга с некоторым полиномиальным временем работы, вход которой состоит только из открытых данных. Обозначим через $Q$ количество запросов, которые $A$ может задать случайному оракулу. Предположим, что в течение времени $T$, $A$ дает с вероятностью $\varepsilon \geq {\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\neq h^{\prime }$ за ожидаемое время $T_{0}\leq {\frac {84480TQ}{\varepsilon }}$.

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

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

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

${\text{x ← IG; }}h_{1},...,h_{q}{\text{ ← H; (J,σ) ←}}A(x,h_{1},...,h_{q})$

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

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

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

${\text{frk}}=Pr\left[{\text{b=1: x ← IG; (b, σ, σ′) ← }}F_{A}(x)\right].$

Тогда:

${\text{frk}}\geq {\text{acc}}\cdot \left({\frac {\text{acc}}{q}}-{\frac {1}{h}}\right)(1)$

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

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

Идея состоит в том, что A запускается два раза в связанных исполнениях, где процесс «разветвляется» в определённый момент, когда некоторые, но не все входные данные были исследованы. Точка, в которой процесс разветвляется, может быть тем, что мы хотим определить позже, возможно, основываясь на поведении A в первый раз: вот почему утверждение леммы выбирает точку ветвления $J$ на основании выходных данных A. Требование о том, что $h_{J}\neq 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$ также не незначителен. Это позволяет нам доказать, что если основная сложная проблема действительно сложна, то никакой злоумышленник не может подделать подписи. В этом суть доказательства, данного Пойнтхевалом и Стерном для модифицированной схемы подписи Эль-Гамаля.

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

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

$h_{1},...,h_{q}{\text{ ← H; (J,σ) ←}}A(x,h_{1},...,h_{q})$.

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

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

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

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

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

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

$frk(x)=Pr[I=I^{\prime }\wedge I\geq 1\wedge h_{I}\neq h_{I}^{\prime }]\geq Pr[I=I^{\prime }\wedge I\geq 1]-Pr[I\geq 1\wedge h_{I}\neq h_{I}^{\prime }]=$

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

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

$Pr\left[J=i:h_{1},...,h_{q}{\text{ ← H; (J,σ) ←}}A(x,h_{1},...,h_{q};\rho )\right]$ для всех $\rho \in \mathbf {R}$ и $h_{1},...,h_{q}\in H$.

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

$Pr[I=I^{\prime }\wedge I\geq 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},...,h_{i-1}}X_{i}(\rho ,h_{1},...,h_{i-1})^{2}\cdot {\frac {1}{|\mathbf {R} |\cdot |H|^{i-1}}}=\sum _{i-1}^{q}E[X_{i}^{2}]\geq \sum _{i-1}^{q}E[X_{i}]^{2}$. Пусть $x_{i}=E[X_{i}]$ для $x\in {1,...,q}$. Тогда
$\sum _{i=1}^{q}E[X_{i}]^{2}\geq {\frac {1}{q}}\cdot \left(\sum _{i=1}^{q}E[X_{i}]\right)^{2}={\frac {1}{q}}\cdot acc(x)^{2}.$ Это доказывает $(3)$, и, следовательно, $(1)$. Докажем теперь $(2)$. С учетом $(1)$ получим, что
$\left(acc-{\frac {q}{2h}}\right)^{2}=acc^{2}-acc\cdot {\frac {q}{h}}+{\frac {q^{2}}{4h^{2}}}\leq q\cdot frk+{\frac {q^{2}}{4h^{2}}}.$
Взяв с обеих сторон квадратный корень, и учтя, что

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

получим:

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

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

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

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

Литература

• Adam Young, Moti Yung. Malicious Cryptography: Exposing Cryptovirology (англ.). — 2004. — P. 344.
• E.Brickell, D.Pointcheval, S.Vaudenay, M.Yung. Design Validations for Discrete Logarithm Based Signature Schemes (англ.). — 2000. — P. 276—292.
• David Pointcheval, Jacques Stern. Security Proofs for Signature Schemes (англ.). — 1996. — P. 387–398.
• Mihir Bellare, Gregory Neven. Multi-Signatures in the Plain Public-Key Model and a General Forking Lemma (англ.). — 2006. — P. 390—399.
• David Pointcheval, Jacques Stern. Security Arguments for Digital Signatures and Blind Signatures (англ.). — 2000. — P. 361—396.
• C.P. Schnorr. Security of Blind Discrete Log Signatures Against Interactive Attacks (англ.). — 2001. — P. 1—13.
• C.P.Schnorr. Enhancing the security of perfect blind DL-signatures (англ.). — 2006. — P. 1305—1320.