Лемма разветвления () — лемма в области криптографических исследований.
На практике, лемма разветвления широко используется для доказательства безопасности различных схем цифровой подписи и других криптографических конструкций на основе случайного оракула.
История Доказана и впервые использована Дэвидом Поинтчевалом и в «Доказательствах безопасности схем подписи», опубликованных в материалах Eurocrypt в 1996 году. В их статье лемма о разветвлении определена в терминах противника, который атакует схему цифровой подписи, созданную в модели случайного оракула (идеализированная хеш-функция, которая на каждый новый запрос выдаёт случайный ответ, равномерно распределённый по области значений, с условием, что если один и тот же запрос поступит дважды, то ответ должен быть одинаковым). Они показывают, что если злоумышленник может подделать подпись с пренебрежимо малой вероятностью, то есть существует некоторая вероятность того, что тот же противник с той же случайной лентой может создать вторую подделку в атаке с другим случайным оракулом.
Лемма была позже обобщена и Грегори Невеном.
Формулировка
Лемма разветвления (оригинальная) Первоначальный вариант леммы , сформулированный и доказанный Поинтчевалом и Стерном, выглядит следующим образом:
Пусть — общая схема цифровой подписи с секретным параметром . Пусть — вероятностная машина Тьюринга с некоторым полиномиальным временем работы, вход которой состоит только из открытых данных. Обозначим через количество запросов, которые может задать случайному оракулу. Предположим, что в течение времени , дает с вероятностью , валидную подпись . Тогда есть другая машина, которая имеет контроль над А и производит две валидные подписи и такие, что за ожидаемое время .
Обобщенная лемма разветвления Также существует обобщенный вариант этой леммы , сформулированный и доказанный Белларом и Невеном. В отличие от классического варианта леммы Поинтчевала и Стерна, обобщенная лемма оперирует не со схемами подписей и случайными оракулами, а скорее концентрируется на выходном поведении алгоритма, когда он запускается дважды на связанных входах. Это делает её легко применимой в контекстах, отличных от стандартных схем подписи, и отделяет вероятностный анализ от фактического моделирования в доказательстве безопасности, что позволяет использовать более легкие для проверки доказательства. Для понимания связи между леммами следует воспринимать как открытый ключ и набор чисел как ответы на запросы случайного оракула. Формулировка обобщенной леммы разветвления: Зафиксируем целое число и набор размером . Пусть — вероятностная машина Тьюринга, которая на вход получает набор , где — случайная лента для . Пусть возвращает пару , где является целым числом в диапазоне , а второй элемент называется побочным выводом. Предположим далее, что — это распределение вероятностей, из которого берется . Вероятность принятия обозначаемая , определяется как вероятность того, что в эксперименте
Определим «алгоритм разветвления» для заданной машины Тьюринга A, который принимает входные данные , следующим образом: Выберем случайную ленту для . Выберем равномерно из . Запустим c набором на входе, чтобы получить набор . Если , то вернуть . Выберем равномерно из . Запустим A с набором на входе, чтобы получить набор . Если и , вернуть , в противном случае вернуть . Пусть будет вероятностью того, что выдает тройной результат, начиная с 1, при условии, что вход выбран произвольно из :
Тогда:
Что равносильно
Идея состоит в том, что A запускается два раза в связанных исполнениях, где процесс «разветвляется» в определённый момент, когда некоторые, но не все входные данные были исследованы. Точка, в которой процесс разветвляется, может быть тем, что мы хотим определить позже, возможно, основываясь на поведении A в первый раз: вот почему утверждение леммы выбирает точку ветвления на основании выходных данных A. Требование о том, что является техническим требованием, используемым многими леммами. (Обратите внимание, что поскольку и выбираются случайным образом из , то, если большое, что нормально, вероятность того, что два этих значения не будут различаться, чрезвычайно мала.)
Пример Например, пусть будет алгоритмом взлома схемы цифровой подписи в модели случайного оракула. Тогда будет открытым параметром (включая открытый ключ), который атакует , а будет выводом случайного оракула на его -й отдельный вход. Лемма разветвления полезна, когда было бы возможно, учитывая две разные случайные подписи одного и того же сообщения, решить некоторую сложную проблему. Однако противник, который подделывает один раз, порождает того, кто подделывает дважды одно и то же сообщение с немалой вероятностью благодаря лемме о разветвлении. Когда пытается подделать сообщение , мы считаем вывод следующим образом , где — подделка, а таков, что был -м уникальным запросом к случайному оракулу (можно предположить, что запросит в некоторый момент, если должен быть успешным с незначительной вероятностью). (Если выдает неправильную подделку, мы считаем, что выходные данные .)
По лемме разветвления вероятность получения двух хороших подделок и для одного и того же сообщения, но с разными случайными выходами оракула (то есть ≠ ) не пренебрежимо мала, когда параметр также не незначителен. Это позволяет нам доказать, что если основная сложная проблема действительно сложна, то никакой злоумышленник не может подделать подписи. В этом суть доказательства, данного Пойнтхевалом и Стерном для модифицированной схемы подписи Эль-Гамаля.
Доказательство обобщенной леммы Докажем сначала , потом докажем что из следует . Пусть для каждого величина будет обозначает вероятность того, что в эксперименте . Также пусть . Мы утверждаем, что для любого . Затем, зная и с учетом что , получаем
Что доказывает . Перейдем к доказательству утверждения . Для любого входа с вероятностями, взятыми из , мы имеем
Осталось показать что . Обозначим через множество, в котором работает данная машина Тьюринга A. Пусть для каждого соответствующий определяется значением в для всех и . здесь рассматривается как случайная величина с равномерным распределением. Тогда
. Пусть для . Тогда
Это доказывает , и, следовательно, . Докажем теперь . С учетом получим, что Взяв с обеих сторон квадратный корень, и учтя, что для любых вещественных получим: , откуда следует . Лемма доказана.
Известные проблемы с использованием леммы Ограничение, создаваемое леммой о разветвлении, не является жестким. Авторы Поинтчевал и Стерн предложили несколько способов для повышения уровня безопасности цифровых подписей и слепой подписи, основываясь на лемме разветвления. Однако осуществил атаку на слепые схемы подписей Шнорра, которые, как утверждалось, были надежно защищены Поинтчевалом и Стерном. Шнорр также предложил усовершенствования для защиты схем слепых подписей, основанных на проблеме дискретного логарифмирования.
Примечания
Литература
Категория:Криптография Категория:Электронная подпись