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

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

Эта концепция была впервые использована Дэвидом Пойнтчевалем и Жаком Стерном в «Доказательствах безопасности для схем подписи», опубликованных в материалах Eurocrypt 1996. ^[1]^[2] В их статье лемма о разветвлении определяется с точки зрения противника, который атакует схему цифровой подписи , созданную в модели случайного оракула . Они показывают, что если злоумышленник может подделать подпись с немалой вероятностью, то существует немаловажная вероятность того, что тот же злоумышленник с той же случайной лентой может создать вторую подделку при атаке с другим случайным оракулом. ^[3] Лемма о разветвлении была позже обобщена Михиром Белларе и Грегори Невеном. ^[4] Лемма о разветвлении использовалась и в дальнейшем обобщалась для доказательства безопасности различных схем цифровых подписей и других криптографических конструкций, основанных на случайных оракулах. ^[2]^[5]^[6]

Утверждение леммы

Обобщенный вариант леммы формулируется следующим образом. ^[4] Пусть A — вероятностный алгоритм с входными данными ( x , h ₁ , ..., h _q ; r ), который выводит пару ( J , y ), где r относится к случайной ленте A (то есть случайному выбору А сделаю). Предположим далее, что IG — это распределение вероятностей, из которого x извлекается , и что H — это набор размера h , из которого каждое из hi _{значений} извлекается в соответствии с равномерным распределением . Пусть acc будет вероятностью того, что на входных данных, распределенных так, как описано, выходной сигнал J от A больше или равен 1.

Затем мы можем определить «алгоритм разветвления» F _A действует следующим образом , который на входе x :

ленту r для A. Выберите случайную
Выбрать h ₁ , ..., h _q равномерно из H .
Запустите A на входе ( x , h ₁ , ..., h _q ; r ), чтобы получить ( J , y ).
Если J = 0, верните (0, 0, 0).
Выбрать h' _J , ..., h' _q равномерно из H .
Запустите A на входе ( x , h ₁ , ..., h _{J −1} , h ' _J , ..., h ' _q ; r ), чтобы получить ( J ', y ').
Если J' = J и h _J ≠ h' _J , то верните (1, y , y '), в противном случае верните (0, 0, 0).

Пусть frk — вероятность того, что F _A выдаст тройку, начиная с 1, при условии, что входной сигнал x выбран случайно из IG . Затем

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

Интуиция

Идея здесь состоит в том, чтобы думать, что A выполняется два раза в связанных выполнениях, где процесс « разветвляется » в определенный момент, когда часть входных данных, но не все, были проверены. В альтернативной версии остальные входные данные генерируются заново, но генерируются обычным способом. Момент, в котором процесс разветвляется, может быть чем-то, что мы хотим решить только позже, возможно, на основе поведения A в первый раз: именно поэтому утверждение леммы выбирает точку ветвления ( J ) на основе выходных A. данных Требование, чтобы h _J ≠ h' _J, является техническим требованием, необходимым для многих применений леммы. (Обратите внимание, что поскольку и h _J , и h' _J выбираются случайным образом из H , то если h велико, как это обычно бывает, вероятность того, что эти два значения не будут разными, чрезвычайно мала.)

Пример

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

Согласно лемме о разветвлении, вероятность ( frk ) получения двух хороших подделок y и y' в одном и том же сообщении, но с разными случайными выходными данными оракула (то есть с h _J ≠ h' _J ), не является пренебрежимо малой, когда акк также не является пренебрежимо малым. - ничтожно. Это позволяет нам доказать, что если основная трудная проблема действительно сложна, то ни один злоумышленник не сможет подделать подписи.

В этом суть доказательства, данного Пойнтчевалем и Стерном для модифицированной схемы сигнатуры Эль-Гамаля против адаптивного противника.

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

Сведение, обеспечиваемое леммой о разветвлении, не является строгим. Пойнтчеваль и Стерн предложили аргументы в пользу безопасности цифровых подписей и слепой подписи, используя лемму о разветвлении. ^[7] Клаус П. Шнорр представил атаку на схемы слепых подписей Шнорра, ^[8] с более чем $polylog(n)$ одновременные казни (случай, изученный и доказанный Пойнтчевалем и Штерном). Атака за полиномиальное время, $\Omega (n)$ одновременные казни были показаны в 2020 году Бенхамудой, Лепойнтом, Райковой и Орру.Шнорр также предложил усовершенствования для защиты схем слепых подписей, основанных на задаче дискретного логарифма . ^[9]

Ссылки

^ Эрнест Брикелл , Дэвид Пойнтчеваль , Серж Водене и Моти Юнг , « Проверка проекта для схем подписи на основе дискретного логарифма », Третий международный семинар по практике и теории криптосистем с открытым ключом, PKC 2000, Мельбурн , Австралия , 18–20 января 2000 г. , стр. 276–292.
^ Jump up to: ^а ^б Адам Янг и Моти Юнг, «Вредоносная криптография: разоблачение криптовирусологии», Wiley press, 2004, стр. 344.
^ Дэвид Пойнтчеваль и Жак Стерн , « Доказательства безопасности для схем подписи », Достижения в криптологии — EUROCRYPT '96, Сарагоса , Испания , 12–16 мая 1996 г., стр. 387–398.
^ Jump up to: ^а ^б Михир Белларе и Грегори Невен, « Мультиподписи в модели с простым открытым ключом и общая лемма о разветвлении », Материалы 13-й конференции Ассоциации вычислительной техники (ACM) по компьютерной и коммуникационной безопасности (CCS), Александрия, Вирджиния , 2006 г. , стр. 390–399.
^ Али Багерзанди, Чон Хи Чхон, Станислав Джареки:Мультиподписи безопасны при условии дискретного логарифма и обобщенной леммы о разветвлении. CCS '08: Материалы 15-й конференции ACM по компьютерной и коммуникационной безопасности, 2008 г., стр. 449-458.
^ Хавьер Эрранц, Херман Саес: Леммы о разветвлении для схем кольцевой подписи. 266-279
^ Дэвид Пойнтчеваль и Жак Стерн, «Аргументы безопасности цифровых подписей и слепых подписей», ЖУРНАЛ КРИПТОЛОГИИ , том 13, стр. 361–396, 2000. Доступно в Интернете .
^ CPSchnorr, «Безопасность слепых дискретных подписей журналов от интерактивных атак», Proceedings of ICICS 2001, LNCS Vol. 2229 , стр. 1–13, 2001 г. Доступно в Интернете. Архивировано 13 июня 2011 г. на Wayback Machine .
^ CP Schnorr, «Повышение безопасности по сравнению с идеальными слепыми DL-подписями», Information Sciences, Elsevier, Vol. 176, стр. 1305–1320, 2006 г. Доступно в Интернете. Архивировано 13 июня 2011 г. на Wayback Machine.

[1] Эрнест Брикелл , Дэвид Пойнтчеваль , Серж Водене и Моти Юнг , « Проверка проекта для схем подписи на основе дискретного логарифма », Третий международный семинар по практике и теории криптосистем с открытым ключом, PKC 2000, Мельбурн , Австралия , 18–20 января 2000 г. , стр. 276–292.

[YoungYung-2] Jump up to: ^а ^б Адам Янг и Моти Юнг, «Вредоносная криптография: разоблачение криптовирусологии», Wiley press, 2004, стр. 344.

[3] Дэвид Пойнтчеваль и Жак Стерн , « Доказательства безопасности для схем подписи », Достижения в криптологии — EUROCRYPT '96, Сарагоса , Испания , 12–16 мая 1996 г., стр. 387–398.

[BellareNeven-4] Jump up to: ^а ^б Михир Белларе и Грегори Невен, « Мультиподписи в модели с простым открытым ключом и общая лемма о разветвлении », Материалы 13-й конференции Ассоциации вычислительной техники (ACM) по компьютерной и коммуникационной безопасности (CCS), Александрия, Вирджиния , 2006 г. , стр. 390–399.

[5] Али Багерзанди, Чон Хи Чхон, Станислав Джареки:Мультиподписи безопасны при условии дискретного логарифма и обобщенной леммы о разветвлении. CCS '08: Материалы 15-й конференции ACM по компьютерной и коммуникационной безопасности, 2008 г., стр. 449-458.

[6] Хавьер Эрранц, Херман Саес: Леммы о разветвлении для схем кольцевой подписи. 266-279

[7] Дэвид Пойнтчеваль и Жак Стерн, «Аргументы безопасности цифровых подписей и слепых подписей», ЖУРНАЛ КРИПТОЛОГИИ , том 13, стр. 361–396, 2000. Доступно в Интернете .

[8] CPSchnorr, «Безопасность слепых дискретных подписей журналов от интерактивных атак», Proceedings of ICICS 2001, LNCS Vol. 2229 , стр. 1–13, 2001 г. Доступно в Интернете. Архивировано 13 июня 2011 г. на Wayback Machine .

[9] CP Schnorr, «Повышение безопасности по сравнению с идеальными слепыми DL-подписями», Information Sciences, Elsevier, Vol. 176, стр. 1305–1320, 2006 г. Доступно в Интернете. Архивировано 13 июня 2011 г. на Wayback Machine.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]