Строгие доказательства для схем подписи без использования Random Oracles

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 11:31, 10 ноября 2015.
Tight Proofs for Signature Schemes without Random Oracles
TPSSRO.png
Авторы Sven Schäge[@: 1]
Опубликован 2011 г.
Сайт International Association for Cryptologic Research
Перевели Ilya Kukhtikov
Год перевода 2015 г.
Скачать оригинал

__NUMBEREDHEADINGS__

Содержание

Аннотация. Мы представляем первые строгие доказательства безопасности для двух основных классов схем подписей, основанных на Strong RSA. Среди пострадавших схем есть схемы Cramer-Shoup, Camenisch-Lysyanskaya, Zhu и схемы подписей Fischlin. Мы также представляем два наших варианта билинейных классов подписей, которые производят короткие подписи. Подобно этому мы покажем, что эти варианты имеют жесткие доказательства безопасности применения SDH (Strong Diffie-Hellman). Таким образом мы получили очень эффективное SDH на основе сигнатур схем Cramer-Shoup, Fischlin и Zhu, и первое полное доказательство недавней сигнатуры схемы Camenisch-Lysyanskaya, которая была доказана и признана безопасной при условии соблюдения SDH. Главным в наших результатах является доказательство нового метода, который позволяет симулятору избегать предположения того, какой из запросов подписи нападавшего снова использован в подделке. В отличие от предыдущих доказательств, наше уменьшение безопасности не теряет здесь фактор q.
Ключевые слова: класс подписи, строгий режим, SRSA, SDH, стандартная модель.

Введение

Доказуемая безопасность и трудные сокращения. Основная идея доказуемой безопасности заключается в том, чтобы создать такую крипто-схему таким способом, с помощью которой нападавший мог бы эффективно взламывать свои свойства безопасности тогда, как можно также разработать эффективный алгоритм , чтобы взломать, предположительно, трудную задачу. Таким образом мы докажем безопасность схемы путем сокращения от предположения плотности. Теперь, если B имеет почти такую ​​же вероятность успеха, как во время работы в примерно в то же время, мы говорим, что снижение безопасности плотно. В противном случая, безопасность сокращается свободно. Не секрет, почему шифровальщики интересуются строгими доказательствами мер безопасности: помимо того, что теоретически интересно, они, в течение короткого времени, повышают эффективность параметров безопасности. Эта работа была также мотивирована наблюдением, что для нескольких из существующих Strong RSA (SRSA) базируемый сигнал - схемы подписи без Random Oracles и мы не знаем, есть ли доказательства для плотной безопасности. Для тех схем, которые мы знаем, чтобы у нас было строгое доказательство мер безопасности, существуют некоторые ограничения относительно осуществимости (которые в свою очередь не могут быть найдены среди схем подписи со свободным сокращением безопасности). В 2007 году Чеваллир-Мэймс и Джой решили эту проблему следующим образом [1]: они взяли плотно безопасную схему подписи, схему [2] Дженнаро-Алеви-Рабина, и эффективно ее улучшили, перепроектировав одну из ее большинства отнимающих много времени функций. Проблема с таким подходом заключается в том, что он только затрагивает новые изменения продуманной схемы подписи. Поэтому, мы БЕРЕМ тот же самый подход как И Бернстайн НА EURO-CRYPT'08, который предоставил строгие доказательства мер безопасности для оригинальной схемы подписи Рабина-Уильямса в модели [3] Random Oracles. Однако, в отличие от Бернстайна, мы концентрируемся на схемах, которые безопасны в стандартной модели.

Вклад. В этой работе, мы задаем следующий вопрос: есть строгие доказательства безопасности для существующих практических схем подписей Крамера-Шоап [4], Чжу [5], Каменич-Лисинская [6] и Фишлин [7] (которые мы знаем только имея свободные сокращения безопасности)? Мы отвечаем на этот вопрос утвердительно и представляем первые строгие доказательства для указанных выше схем подписи. Тем не менее, наш результат не ограничивается исходными схемами. В нашем исследовании, мы обобщаем схемы от Каменич-Лисинской, Фишлин и Чжу путем введения нового семейства функций рандомизации, называемых объединениями функций. Результатом этого обобщения является абстрактная схема подписи, называемая комбинируемой схемой. Аналогичным образом, введем второй общий класс подписи, называемый "хамелеон хэш-схема", которую можно рассматривать как обобщение схемы подписи Крамера-Шоап. Затем мы доказываем комбинированную схему подписи и хамелеон хэш-схему, что они должны быть плотно безопасными при условии предложенного SRSA, когда иллюстрируется примеры любой безопасной функции объединения, то соответственно иллюстрируется хамелеон хэш-функция. Наконец, мы показываем, что наши результаты не только держатся под предположением SRSA. Мы анализируем, существуют ли там также сокращения для строгих мер безопасности для аналогичных схем, основанных на предположении SDH в билинеарных группах. Интересно, большинство вышеупомянутых схем еще не рассмотрено под предположением SDH (за исключением схемы Camenisch-Lysyanskaya), хотя на том же самом уровне безопасности, описание группы намного короче в билинеарных группах, чем в базируемых фактор-группах. Мы разрабатываем SDH на основе варианта объединения схемы подписи и хэш-хамелеон схемы и докажем это, чтобы была экзистенциально неподдельна под адаптивно выбранные сообщения атак со строгим снижением безопасности. При этом мы представляем первые основанные на SDH варианты Фишлин, Чжу и схемы подписи Крамера-Шоупа и первого доказательства строгих мер безопасности основанного на SDH схеме Camenisch-Lysyanskaya. Когда иллюстрируется пример с существующими функциями объединения (соответственно хамелеон хэш-функция), мы получаем короткие и эффективные схемы подписи. Все наши результаты (на объединяющемся классе) могут легко быть расширены на схеме подписи блоков сообщения (как определено в [[6], [8]]), где мы можем даже использовать отличные функции объединения для каждого блока сообщения. Наши результаты могут интерпретироваться двумя положительными способами: 1) Существующие внедрения затронутых схем подписи (с фиксированным размером параметра) обеспечивают более высокую безопасность, чем мы ожидаем. 2) У Новых внедрений могут быть более короткие параметры безопасности, что влияет на более эффективную передачу этих параметров.

Технический вклад. В существующих доказательствах симулятор делит набор подделок при первом предположении , где - число запросов подписи, сделанные нападавшим. Только если подделка нападавшего делит некоторые общие ценности с ответом на j-й запрос подписи, то симулятор может сломать предположение SRSA. Иначе симулятор просто завершает работу. Так как число вопросов подписи увеличивается полиномиальным образом в параметре безопасности, то доказательство безопасности здесь теряет фактор q. Наш основной вклад - новая техника, которая отдает начальное ненужное предположение. Как следствие любая подделка помогает симулятору сломать предположение SRSA. Это приводит к доказательству строгих мер безопасности.

Связанная работа. Наша работа связана с существующим хэшем и схемами подписи знака без Random Oracles, которые доказаны безопасными под SRSA или предположением SDH. Мы впоследствии даем краткий обзор доступных результатов. В 1988 Goldwasser, Micali и Rivest издали первую доказуемо безопасную, но неэффективную схему [9] подписи. Больше чем десятилетие спустя, в 1999, Дженнаро, Хэлеви и Рабин [2] представили схему подписи, которая безопасна в стандартной модели под "Гибким" или "Сильным" предположением RSA (SRSA). Эта схема является более эффективной, и ключ и размер подписи состоят из менее чем двух элементов группы (1024 бит), но есть недостаток - она опирается на непрактичные функции, инъективные сообщениям простых чисел [10]. Предпочтительно, что схема подписи Дженнаро-Алеви-Рабина, как известно, имеет доказательство строгих мер безопасности. В то же время, основываясь на предположении SRSA, Крамер и Шоап [4] предложили эффективную стандартную схему модели подписи, что в отличие от [2], не требует, чтобы отображались сообщения с простыми числами. В противоположность этому, простые числа можно сделать равномерно случайным образом из набора простых чисел заданной битовой длины. На основании этой работы, Чжу [11], [5], Фишлин [7], Каменич и Лисинская [6], и Хофхайнц и Килц [12] и в последующие годы, представили схемы, основанные на SRSA. Эти схемы являются либо более эффективным, чем схемы Крамера-Шоап, либо очень подходят протоколам выдачи подписи, совершенными значениями. В 2004 году Боне и Бойен представили первый хэш и знак схемы подписи, в следствие чего используются билинейные группы [13]. Большим преимуществом билинейных групп является очень компактное представление элементов группы. Схема подписи Боне-Бойена доказана плотно безопасной под новым гибким предположением - -Strong Dife Hellman (SDH). В 2004 году, Каменич и Лисинская также представили схему подписи, которая опирается на билинейные группы [8]. В отличие от схемы Боне-Бойен, их схема доказана для безопасности под предположение LRSW [14]. Тем не менее, в той же работе они также предлагают вариант, основанный на предположении SDH в билинейных группах. Соответствующее доказательство безопасности было предоставлено ​​четыре года спустя в [15], [16]. Подобно оригинальной схеме, доказательство безопасности схемы SDH Каменич-Лисинской мягкое.

Подготовка

Прежде, чем представить наши результаты мы кратко сначала рассмотрим необходимые формальные и математические определения. Для удобства мы также опишем две общие, начальную и ключевую, поколения процедур (параметры настройки) в Разделе 2.7 и Разделе 2.8. Описывая наши схемы подписи в Разделах 3.1, 3.2, 3.5 мы обратимся к соответствующему урегулированию и только тогда опишем поколение сигнатуры и алгоритмы проверки.

Примечание

Для мы пишем , обозначаем набор . Для последовательности мы запишем обозначив его длину в битах. Если , то мы записываем , обозначая при этом абсолютную величину . Для набора мы используем и она относится к его размеру и и укажем, что оттянут от однородно наугад. Для мы используем и обозначим модуль квадратного остатков , т.е. . Если - алгоритм, то мы используем которое обозначает, что ввела параметры . Соответственно означает, что выходы при работе со входами . PPT относится к вероятностному полиномиальному времени. Мы записываем , указывая на параметр безопасности и - описываемая последовательность, состоящая из . В дальнейшем, мы неявно предполагаем, что размер генерируемого ключевого материала всегда зависит полиномиально от параметра безопасности.

Сигнатуры схем

Схема -цифровой подписи состоит из трех алгоритмов. Алгоритм PPT KeyGen на входе генерирует секретный и открытый ключи пары . Знак алгоритма PPT берет в качестве входа секретный ключ и сообщение и выводит сигнатуру . Наконец, детерминированный полиномиальный алгоритм проходит проверку, берет открытый ключ , сообщение и подпись , чтобы проверить, является ли законной подписью на , подписанном держателем секретного ключа, соответствующего . Соответственно, алгоритм выводит 1, если подтверждение прошло успешно, и 0, если произошел отказ.

Strong Existential Unforgeability

Стандартное понятие безопасности для сигнатур подписи исходит из Goldwasser, Micali и Rivest [9]. В этой статье мы используем немного более "сильное" определение, называемое Strong Existential Unforgeability. Сигнатура схемы является Strong Existential Unforgeability и сообщение устойчиво к атаке, если это неосуществимо для "подделывателя", т.е. тот, кто знает открытый ключ и глобальные параметры для подделывания, после получения полиномиальным способом (в параметре безопасности) сигнатур в сообщениях и выбора на сигнатуре , получит новую пару сообщений/сигнатур.

TemplateDifinitionIcon.svg Определение «Определение 1»

Мы говорим, что является -безопасностью, если для всех t-времен противниками А, будет отправлено много запросов сигнатуре Oracle, то будет справедливо, что

,

где берется случайная вероятность и , и среди нет пар сообщений/сигнатур , полученных с помощью (т.е. ).

Устойчивое к столкновению хэширование

TemplateDifinitionIcon.svg Определение «Определение 2»

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

,

где вероятность является случайными битами .

Хэш-функция хамелеон

Хэш-функция хамелеон состоит из трех алгоритмов [17]. PPT алгоритм принимает в качестве входных параметров безопасности К и выводит секретный ключ и открытый ключ . Учитывая , случайная из рандомизации пространства и сообщение от сообщения пространства , алгоритм CHEval выводит хамелеон хэш-значение в хэш-пространство . Аналогично, детерминировано выводит на входной и так, что .

TemplateDifinitionIcon.svg Определение «Определение 3 (Столкновение устойчивых хамелеон хэш-функций)»

Мы говорим, что является устойчивой к столкновениям, если для всех временных противников , которым только предоставляется такие, что

,

где вероятность выбирается случайно и бросается монета .

Мы также требуем, что для произвольного, но фиксированного открытого выходного ключа по , все сообщения генерируют одинаково распределенные случайные значения при составлении равномерно наугад и выводится . Мы пишем для обозначения и для , если ключи видно из контекста. Безопасность хамелеон хэш-функций может быть основана на очень стандартных предположениях, таких как предположение дискретного логарифма [17] или факторинговое предположение [17],[18], которые слабее, чем SDH, соответственно SRSA - предположение.

Объединение функции

В этом разделе, мы вводим новое семейство функций, называемых объединения функций. Мы впоследствии будем использовать концепцию объединения функций для обобщения нескольких существующих сигнатур схем.

TemplateDifinitionIcon.svg Определение «Определение 4 (Комбинированные функции)»

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

1. Для всех справедливо, что где определяется как . Для всех и всех существует эффективный алгоритм что, если , производит уникальную стоимость таким образом, что , и иначе .

2. Для и , у нас есть максимальное (по всем ) статическое расстояние между и что

.

3. Для всех , справедливо для всех -времен противников что

,

где вероятность берется по случайным битам .

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

Таблица 1. Примеры статистически безопасных совмещенных функций. Пусть , , , и будет главной.
combining
EX1
EX2
EX3

В таблице 1 мы приводим три конкретные примера (EX1, EX2, EX3) статистически безопасных совмещенных функций. Следующая лемма показывает, что эти примеры являются допустимыми, сочетающие функции по определению 4.

TemplateTheoremIcon.svg Теорема Лемма 1
EX1 и EX2 составляют - объединяющиеся функции, и EX3 составляет - комбинирующую функцию.
Доказательство

Давайте сначала проанализируем EX1 и EX2. Мы знаем, что для всех и мы можем эффективно вычислить как или для всех взятых и . Кроме того, поскольку взаимно однозначна в обоих входных параметрах , равномерно распределенных в для всех и случайной . Таким образом, . Наконец, поскольку является биекцией во втором входном параметре, это без столкновений (свойство 3) в обоих примерах, то мы имеем, что . Теперь давайте проанализируем EX3. Для данных и выходы , если и иначе . Чтобы показать, что является не сталкивающейся, заметим, что подразумевает для всех . Анализируя сначала заметим, что равномерно в , так как следует, что определяет биекцию для . Для и мы получим

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

TemplateTheoremIcon.svg Теорема Лемма 2
Пусть является устойчивой к столкновению хэш-функцией. Тогда с является комбинированной.
Доказательство

Без доказательства.


Условия Strong RSA

TemplateDifinitionIcon.svg Определение «Определение 5 (Предположение Strong RSA)»

Учитывая RSA модуль , где достаточно большие простые числа, и элемент , мы говорим, что - SRSA и предположение справедливо, если для всех временных противников

где вероятность определяется случайным выбором и случайно подброшенной монетой

TemplateDifinitionIcon.svg Определение «Определение 6 (Условия SRSA)»

В этих условиях выводит пару ключей для безопасных модулей такие, что и являются простыми. Все вычисления выполняются в циклической группе . Пусть для - многочлены. Мы требуем, что и . Кроме того, мы предполагаем, что предположительно выполняются. Мы позволяем быть публичными случайными генераторами с неизвестными . Когда используем комбинированную функцию мы предполагаем, что и . Мы позволим множество -разрядных простых чисел. Наконец, мы требуем, чтобы .

Условия Strong Diffie-Hellman

TemplateDifinitionIcon.svg Определение «Определение 7 (Билинейные группы)»

Пусть и будут группами простого порядка . Функция : является билинейным спариванием, если оно 1) для всех и мы имеем (билинейность), 2) генератор (невырожденность) и 3) эффективно вычислимое (эффективность). Мы называем билинейной группой.

TemplateDifinitionIcon.svg Определение «Определение 8 (Предположение SDH (SDH))»

Пусть билинейная группа. Мы говорим, что -SDH предположение выполняется, если для всех противников по времени , которые дали набор элементов справедливо, что

,

где случайным образом выбираются генераторы и случайный бит .

TemplateDifinitionIcon.svg Определение «Определение 9 (Условие SDH)»

В условии SDH все вычисления выполнены в циклических группах таких, что . PPT выбираются и выходы . Мы предполагаем, что -SDH предположение выполняется. Наконец, мы предположим, что значения являются публичными случайными генераторами такие, что и неизвестны. В случае комбинированных функций мы предполагаем, что и .

Классы подписи

Для удобства введем два общих класса подписей. Объединение схемы подписи является полезной абстракцией Каменич-Лисинской, Фишлин, и схемы подписи Чжу, использующие комбинированные функции. Хамелеон-подпись схемы можно рассматривать в качестве общего варианта исходной схемы подписи Крамера-Шоап, где мы не будем указывать на конкретный экземпляр хамелеон-хэш функции.

SRSA основанная на комбинированной схеме подписи SRSA основанная на комбинированной схеме подписи S C M B , S R S A {\displaystyle {\mathcal {S}} {CMB,SRSA}}

В условии SRSA, случайно привлекает и и вычисляет подпись на сообщении с . Покажем теперь, что наша конструкция обобщает заявленные схемы подписи. Заметим, что мы можем легко получить схему Фишлин [7], если мы экземпляр функции объединяем с EX2 в таблице 1. Кроме того, мы также можем получить схему Каменич-Лисинской [6], используя EX3. Это становится очевидным, если мы подставим от в виде . [прим. 1] Отметим, что, когда мы используем схему Каменич-Лисинской с длинными сообщениями, мы должны сначала обратиться к столкновению устойчивых хэш-функции к сообщению. То, что мы, по существу получаем в схеме Чжу [11], [5]. По лемме 2, в результате чего функция комбинированная. Процедура проверки принимает предполагаемую подпись и проверяем, если , если , и если - эксцентрично.

SDH основанная на комбинированной схеме подписи SDH основанная на комбинированной схеме подписи S C M B , S D H {\displaystyle {\mathcal {S}} {CMB,SDH}}

Мы также представляем SDH на основе варианта из комбинированной схемы подписи. Заметим, что для схемы Каменич-Лисинской уже существует соответствующий SDH на основе варианта, первоначально введенного в [8] и доказанного в безопасности в [15], [16]. Подобно , мы получаем SDH на основе схемы Каменич-Лисинской, когда экземпляр функции объединеняется с EX1. Таким же образом, мы можем также получить варианты SDH на основе схемы подписи Фишлин (с использованием EX2) и схемы Чжу (с использованием леммы 2). В SDH, основанной на комбинированной функции, сначала выбирает случайное и случайное . Затем вычисляем подпись с . Обусловленная схема , проверяется, если .

SRSA основанная на хамелеон-хэш схеме подписи SRSA основанная на хамелеон-хэш схеме подписи S C H , S R S A {\displaystyle {\mathcal {S}} {CH,SRSA}}

Схема определяется в условиях SRSA. дополнительно генерирует ключевой материал для хамелеон-хэш функции. Значение добавляет открытый ключ схемы ( не требуется. Тем не менее, это может быть полезным при включении схемы подписи в онлайн/оффлайн схему подписи [18]). Алгоритм генерации подписи в первую очередь выбирает случайное и случайное простое число . Затем выводит подпись на сообщение , где . Чтобы проверить предполагаемую подпись на , проверяется, если - необычное, если и если .

SDH основанная на хамелеон-хэш схеме подписи SDH основанная на хамелеон-хэш схеме подписи S C H , S D H {\displaystyle {\mathcal {S}} {CH,SDH}}

Определим теперь новый вариант хамелеон-хэш схемы подписи, основанной на предположении SDH. Опять же, также добавляет открытый ключ хамелеон-хэш функции к . В условии SDH сначала выбирается случайное и случайное . Используя , это затем выводит подпись на в виде , где . Чтобы проверить данную подпись </math>\sigma = (r,s,t)</math> на , проверяется . Подходящая хамелеон-хэш функция может быть, например, в [17].

Схема подписи Крамера-Шоап Схема подписи Крамера-Шоап S C H , S R S A {\displaystyle {\mathcal {S}} {CH,SRSA}}

Давайте теперь рассмотрим схему подписи Крамера-Шоап, которая определена в условии SRSA. Схема Крамера-Шоап дополнительно требует устойчивую к столкновении хэш функцию: . Пространство сообщения расширено на . Предполагаем, что .

- дополнительно вычисляет случайное -разрядное простое число . Секретный ключ - , публичный ключ - .

- в первую очередь выбирает случайное и оценивает (хамелеон-хэш функция) . Затем он обращает случайное -разрядное простое число и вычисляет значение . Подпись - .

- повторно вычисляет и проверяет , если - странное, и если .

К сожалению, доказательство более общего класса хамелеон-хэш схемыа формально не переходит к схеме подписи Крамера-Шоупа, потому что в схеме Крамере-Шоупе ключевой материал ее хамелеон-хэш функции не выбран независимо. В частности хамелеон-хэш функция использует тот же самый модуль RSA и то же самое значение . Это требует немного большего ухода в доказательстве безопасности. Мы предоставляем полное доказательство схемы подписи Крамера-Шоупа в полной версии.

Безопасность

TemplateTheoremIcon.svg Теорема Теорема 1

Схема подписи Крамера-Шоапа, комбинированный класс подписи (как в ШАСС и настройки SDH), и класс хамелеон подпись (как в SRSA и условии SDH) плотно защищены от атак адаптивных выбранных сообщений. В частности, это означает, что Каменич-Лисинская, Фишлин, Чжу и SDH, на основе схемы Каменич-Лисинской, плотно защищены от сильных экзистенциальных подделок под адаптивно выбранных атакующих сообщений.

Доказательство

Без доказательства

Мы впоследствии обеспечиваем наши доказательства безопасности интуитивно. В Разделе 4.4 мы представляем полное доказательство безопасности для , которое, как нам кажется, технически наиболее включено в комбинирование. Доказательство продолжается аналогично и появляется в полной версии. Мы тогда неофициально показываем, как передать нашу технику . В полной версии мы также предоставляем полное доказательство безопасности схемы подписи Крамера-Шоупа.

Схема основанная на SRSA

Давайте сначала рассмотрим схемы основанные на SRSA, где берется SRSA, вызывающая с . Предположим, что нападающий "вопросом" отправил запрос подписи . В ответ на каждый запрос с , получает соответствующую подпись .

Напомним, что существующие доказательства безопасности для схем комбинированного класса (например, [7]). Рассмотрим два фальшивомонетчика, которые свободно комбинируются из предположения SRSA. Это тот случай, когда оно имеет место для-подделок что - НОД . [прим. 2] При условии это значит, что для некоторых . Давайте сосредоточимся на случае . Доказательство оставшегося случая и ) очень похоже. Оно дополнительно использует свойства комбинированной функции.

Доказательства в [4], [7], [11], [6], [5]] работают следующим образом: симулятор в первых предположениях . По конструкции, может ответить на все запросы подписи, но только тогда, когда выводит подделку, где он может извлечь решение проблемы SRSA. Во всех остальных случаях (если для некоторых ) просто прерывается. Так как число запросов подписи поднимается за полиномиальный параметр безопасности, вероятность угадать заранее и, следовательно, не является незначительным. Тем не менее, снижение безопасности теряет фактор здесь.

Наша цель - улучшение этого шага редукции. В идеале, мы имеем, что любой подлог, который содержит помогает симулятору сломать предположение SRSA. В результате, имитатор может полностью избежать догадки. Основной задачей является ре-дизайн пути , вычисление входных параметров : на каждые мы должны иметь ровно один выбор так, что может имитировать подписание Oracle без перерыва предположения SRSA. С другой стороны, если выходы с для некоторых и , должен уметь вычислять решение вызова SRSA. Перейдем теперь к более подробному.

Для простоты предположим, что может входные параметры настроить так, что проверка подписи всегда сводится к

(1)

Предположим, что ни ни когда-либо откроется . Мы используем независимо выбранную наугад . Таким образом, она может быть задана до подписания запросов. Теперь, стратегией для имитации подписания Oracle является определение такие, что для любого он может вычислить простое число с . Без того, чтобы сломать предположение SRSA, может затем вычислить и -ый выход подписи в виде .

Давайте теперь обратим наше внимание на стадии экстракции, где данная подделка элементов . По предположению имеем для некоторых и . нуждается в том, что НОД (или ), потому что тогда он может найти решение проблемы SRSA по вычислительной с используя расширенный алгоритм Евклида и вывод

- стратегия, чтобы гарантировать НОД заключается в обеспечении . К сожалению, не может предвидеть . Таким образом, лучшим решением является разработка такое, что для всех .

Очевидно, делает серьезные требования по . Теперь мы представляем наше и утверждаем, что оно отлично выполняет все требования. Мы определяем, как

(2)

для . Более того, должны быть различны простые числа. Во-первых, заметим, что для каждого функция сводится к и поэтому . С другой стороны, оно имеет место для что . Исследуя , мы имеем, что и как различные простые числа, мы, наконец, получим, что НОД и поэтому для .

Схема основанная на SDH

В предположении, SDH, ситуация очень похожа. Здесь мы также проанализируем три возможных типа подделок  : 1.) , 2.) с , но и 3.) , (но ) с . Опять же, мы концентрируемся на втором. В начале, дает вызов SDH . На этот раз, выбирает . В настройках SDH, уравнение (1) трансферты

(3)

В отличие от установки SRSA, теперь многочлен с индетерминантом и максимальной степенью . Опять же, должен иметь и в тайне от . Мы определяем

для и различны . Использовав вызов SDH, <math<\mathcal{B}</math> может легко вычислить , поскольку имеет максимальную степень . Заметим, что это всегда имеет место, что . Если , мы, безусловно, имеем, что . Если , потом длинное разделение дает нам <math<>D \in \Z</math> с и новый полином с коэффициентом в такой, что . Подобно классу SRSA, мы можем найти решение на вызов SDH от подделки в качестве

Безопасный хамелеон-хэш класс подписи

Хамелеон-хэш класс подписи также плотно безопасен в SRSA и в условии SDH. Для удобства будем для и . В общей сложности там снова три типа подделок для рассматривания: 1), 2) но , и 3), но . Доказательство 1) является простым и очень похоже на доказательство I типа фальшивомонетчиков из объединяющегося класса. Доказательство 3), очевидно, сводится к свойствам безопасности хамелеон-хзш функции. Доказательство 2) требует нашу новую технику, чтобы создать . Напомним про Раздел 4, где мы анализировали уравнения и в условиях SRSA (и и в условии SDH).

В доказательстве объединенного класса есть случайные значения (),могут быть определены до этапа моделирования. В доказательстве хамелеон-хэш класс возьмем подобный подход. Теперь является выходным значением хамелеон-хэш функции. В фазе инициализации доказательства мы выбираем случайных входных пар вычислив . Затем мы готовим функцию с и набор случайных простых чисел -разрядных простых чисел (случайные значения ) как в доказательствах объединения класса. Далее, мы вкладываем в показателях двух элементов группы . В фазе моделирования мы даем симулятор , чтобы карта атакуемых сообщений была подготовлена путем вычисления . Таким образом, мы можем успешно имитировать подписание Oracle. В фазе извлечения свойства хамелеон-хэш функции гарантируют это (в противном случае мы можем разорвать безопасность хамелеон-хэш функции). Это гарантирует, что мы можем найти решение проблемы SRSA (вызов SDH).

Безопасный анализ Безопасный анализ S C M B , S R S A {\displaystyle S {CMB,SRSA}}

TemplateTheoremIcon.svg Теорема Лемма 3

В условии SRSA предполагаем, что - SRSA предположительно выполняется и является - комбинирующей функцией. Затем, комбинирующий класс подписи, представленный в Разделе 3.1 [прим. 3][19] защищает от атак выбранных адаптивных сообщений при условии, что

, .

Доказательство

Предположим, что является фальсификатором, - ломающая сильная экзистенциальная . Затем, мы можем сконструировать симулятор , который взаимодействуя с решает проблему SRSA во времени с преимущественно . Мы рассмотрим три типа фальсификаторов, что после q запросов и соответствующие ответы разделяющее множество всех возможных подделок .В доказательство, мы обратимся ко все типам разных атакующих. В начале, мы позволим догадаться с вероятностью не менее , которая выводит подделку . Лемма 3 вытекает с помощью стандартного гибридного аргумента. Мы предполагаем, что дает экземпляр SRSA, вызовывая . Пусть обозначим вероятность успеха злоумышленника успешно подделывающего подписи в игре i.

Доказательство леммы 3 является первым шагом в доказательстве теоремы 1. Отсюда следует, что в оригинале Каменич-Лисинской, Фишлина и Чжу, схема подписи плотно защищена от атаки подделок под экзистенциальных адаптивных выбранных сообщений.


Тип I фальсификатора.

Игра0. Это оригинальная игра-атака. Предполагается, что - ломают при взаимодействии с подписью Oracle . Мы имеем,

.

(4)

Игра1 Теперь, создает значения , используя вызов SRSA вместо выбора их случайным образом из . Во-первых, выбирает случайные - простые числа и три случайных числа . Далее, пусть и . Симулятор вычисляет используя вызов SRSA. Поскольку, неравномерно выбирают наугад из мы должны проанализировать вероятность успеха для выявляющую нашу конструкцию. Заметим, что . Не теряя общий смысл позволим . Теперь, выбрав вероятность случайности , чтобы не быть в , то

С теми же аргументами можно показать, что также распространяется почти равномерно случайным образом в и . Поскольку - простые числа, меньшие чем и , справедливо, что . Таким образом, распределение генераторов практически равно предыдущей игре, и мы получаем от связанного объединения, что

(5)

Игра2. Теперь, имитирует отвечая подписи запросов. Впоследствии, установите и . Симулятор задает и для всех он выбирает случайный и выходы с . Такое распределение вычисленных значений равно предыдущей игре, и

(6)

Игра3. Теперь рассмотрим подделку элементов . Определим . Для подделки элементов справедливо, что . У нас также есть, что НОД НОД, так как по предположению мы знаем НОД . Теперь мы будем анализировать вероятность для событий НОД произойдет. Если НОД (или ) , просто прерывает и перезагружается. Поскольку , он гласит, что НОД. Читаем в виде , где и и заметим, что вид не зависит от . Пусть . Теперь утверждаем, что существует не более одного такой, что . Это очень важно, потому что, если производятся подделки с для всех он всегда держит, что НОД и не могут извлечь решение SRSA вызовом (с помощью методов, описанных ниже). Предположим, что существует, по крайней мере один такой . Тогда, мы имеем, что . Рассмотрим оставшиеся возможности и в виде и . Так НОД мы знаем, что . В виде мы должны иметь . Кроме того, поскольку нечетное мы знаем, что и поэтому . Так, потому что может существовать не более одной с НОД и так как это скрыт от просмотра, вероятность math>\mathcal{A}</math> на выходе . Это означает, что с вероятностью по крайней мере , имеет НОД. Используя элементы подделки , может нарушить условие SRSA путем вычисления <math<a,b \in \Z</math> с НОД и

Наконец, у нас есть, что

(7)

и

(8)

Подключая уравнения (4) - (8), получаем, что .

Тип II фальсификатора. и

Мы только представили различия в предыдущем доказательстве.

Игра1. Во-первых, случайным образом выбирается отличающееся -разрядными простыми числами и -случайными элементами . Кроме того, он выбирает три случайных элемента для . Далее, вычисляет , и используя вызов SRSA. Еще раз,

(9)

Игра2. Теперь имитирует подписание Oracle . На каждой подписи запроса с , отвечает с помощью предварительно вычисленной и и вычисленная в виде

Так как мы выбрали различные простые числа, которые будут, то имеем, что союз обязан, что

(10)

Игра3. Теперь рассмотрим подделку элементов . По предположению существует с и . Тогда у нас есть, что

Поскольку и нечетное число, мы получаем НОД и, как и прежде, мы можем вычислить которая является решением задачи SRSA.

(11)

Подводя итоги уравнений (9) - (11), мы получаем .

Тип III фальсификатора. и

Есть только незначительные различия по сравнению с предыдущим доказательством.

Игра1. Во-первых, случайным образом выбирается отличающееся -разрядными простыми числами и -случайными . Тогда, выбирает три случайных элемента для . Далее, вычисляет и, как , и .

(12)

Игра2. Эта игра равна предыдущей игре, за исключением того, что мы требуем, чтобы быть различными. У нас есть, что

(13)

Игра3. Теперь имитирует подписание Oracle. На каждой подписи запроса с , отвечает . Если , то прерывается. В противном случае он выводит подпись с , время вычисляется как

Свойства комбинированной функции гарантия того, что являются статистически близкой к равномерности по , так, что,

(14)

Игра4. Эта игра, как и предыдущая, за исключением того, когда прерывает происходящее столкновение таким образом, что для некоторых . Заметим, что мы должны иметь , В противном случае просто прокручиваем -сообщение / пару подписей. Для всех противников , атакующих по времени , это происходит с вероятностью не более . Следовательно,

(15)

Рассмотрим подделки элементов . По предположению, существует один индекс с и . Для этого показателя индекс считает, что

Так как мы исключили столкновения, следует, что . В виде , можно вычислить , как вызывается решение SRSA. В заключение,

(16)

Уравнения (12) - (16) показывают, .

Благодарность

Я хотел бы поблагодарить Матиаса Херрманна, Тибора Ягера, Эйке Килтца и Майке Ритсенхофена за полезные замечания по более ранним проектам данного документа и анонимным рецензенторам EUROCRYPT'11, за полезные замечания и предложения.

Контакты авторов материала

  1. Horst Görtz Institute for IT-Security Ruhr-University of Bochum, Sven Schäge, E-mail: sven.schaege@rub.de

Примечания

  1. Чтобы быть точным, наше обобщение несколько отличается от схемы Каменич-Лисинской. В оригинальной схеме, необходимо, чтобы . В результате, авторы рекомендуют для битовых длинных сообщений, которые и . В нашей схеме, мы просто требуем, чтобы . Затем, мы можем установить и для вероятности