Русская Википедия:Лемма разветвления

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

История

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

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

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

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

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

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

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

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

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

<math> \text{x ← IG; } h_{1}, ... , h_{q}\text{ ← H; (J,σ) ←} A(x, h_{1}, ... , h_{q})</math>

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

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

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

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

Тогда:

<math>\text{frk} \geq \text{acc} \cdot \left ( \frac{\text{acc}}{q} - \frac{1}{h} \right) (1)</math>

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

<math>\text{acc} \leq \left ( \frac{\text{q}}{h} + \sqrt{\text{q} \cdot \text{frk}} \right ) (2)</math>

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

Пример

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

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

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

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

<math>h_{1}, ... , h_{q}\text{ ← H; (J,σ) ←} A(x, h_{1}, ... , h_{q})</math>.

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

<math>frk(x) \geq acc(x) \cdot \left ( \frac{acc(x)}{q} - \frac{1}{h} \right) (3)</math>.

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

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

<math> = \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). </math>

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

<math>frk(x) = Pr[ I = I^\prime \wedge I \geq 1 \wedge h_{I} \neq h^\prime_{I}] \geq Pr[ I = I^\prime \wedge I \geq 1] - Pr[ I \geq 1 \wedge h_{I} \neq h^\prime_{I}] = </math>

<math> = 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} </math>

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

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

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

<math>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] = </math> <math> = \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</math>. Пусть <math>x_{i} = E[X_{i}]</math> для <math> x \in {1, ... , q}</math>. Тогда
<math> \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.</math> Это доказывает <math>(3)</math>, и, следовательно, <math>(1)</math>. Докажем теперь <math>(2)</math>. С учетом <math>(1)</math> получим, что
<math>\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}.</math>
Взяв с обеих сторон квадратный корень, и учтя, что

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

получим:

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

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

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

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

Литература

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