Адаптивные псевдо свободные группы и их применение

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 17:12, 2 декабря 2015.
Adaptive Pseudo-free Groups and Applications
NTRU.PNG
Авторы Dario Catalano1,[@: 1],
Dario Fiore[@: 2],
Bogdan Warinschi[@: 3]
Опубликован 2011 г.
Перевели Artem Crook
Год перевода 2011 г.
Скачать оригинал

__NUMBEREDHEADINGS__


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

Введение

История вопроса. Поиск понятий, определяющих основные свойства безопасности для примитивов и протоколов, имеет решающее значение в криптографии. Кроме прочих преимуществ, такие понятия позволяют проводить модульный анализ безопасности, применять повторяющиеся и масштабируемые доказательства. Результатами можно назвать модель случайного алгоритма[1], концепцию универсальной компонуемости [2] и ее версии [3] [4] [5] модели Долева-Яо [6]. Большинство таких понятий (включая вышеперечисленные) применяются к примитивам и протоколам, и не связаны с более сложными математическими структурами, лежащими в основе нынешней криптографии. Заметным исключением для псевдо-свободных групп является понятие, выдвинутое Хохенбергом [7], уточненное в последствии Ривестом [8]. В этой работе мы продолжаем анализ данного понятия.

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

Например, в псевдосвободной группе, если имеется случайная величина , то будет трудно найти решение для уравнения вида если или для уравнения но не для случая Последнее уравнение тривиально, так как оно может быть решено для свободной группы (решением в свободной группе будет ), решение в свободной группе сразу же переводится на решение в рамках G. Понятие псевдо-свободы обобщает строгое предположение алгоритма RSA (когда G является группой RSA), в то же время используя многие другие предположения современной криптографии, см. [8] для дальнейших подробностей. Гипотеза Ривеста о том, что RSA группа является псевдо-свободной была подтверждена Мицианцио [9], который доказал, что это действительно в случае, когда модуль RSA является произведением двух простых чисел.

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

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

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

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

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

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

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

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

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

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

Мы показали, что почти все строгие RSA схемы подписей будут частными случаями нашей общей схемы построения. Мы объясняем, как получить схемы Крамера и Шоупа [10], Фишлина [11], Камениша и Лизанского [12], Чжу [13], Хофхейнца и Килтса [14](Заметим, что в этом случае наша концепция применяется к разновидности с неоптимизированными параметрами. Применение концепции к меньшим противникам является интересным и открытым вопросом. ); и что схемы Дженнаро, Халеви, и Рабина [15] можно получить путем создания соответствующих изменений в нашем общем распределении. Безопасность для всех этих схем следует из безопасности нашего общего построения.

Другие работы. В работе [14] Хофхейнц и Килтс вводят понятие программируемых хэш-функции (PHF), это инструмент, который при использовании в группах, где дискретный логарифм трудно применим, позволяет иметь дело с адаптивными атаками в доказательствах для черных ящиков и других криптографических построений. Среди прочего, они показали, как построить общие подписи на основе строгого RSA предположения. Тем не менее, PHF функции и адаптивные псевдо свободные группы это отличные от описываемых в статье аспекты подписей в строгом RSA алгоритме (например, PHF могут иметь дело с билинейными группами, в то время как наша концепция позволяет охватить сетевые подписи).

Предварительные сведения и обозначения

В своей работе мы используем понятие неразрешимых функций деления. На деле функция H будет неразрешимой функцией деления, если противник A не может найти такие что и разделяет произведение Легко видеть, что этому определению соответствует любая функция, которая соотносит входные данные с простыми числами. Такие соотношения могут быть получены без каких-либо криптографических предположений (см. схему построения в [16]), хотя на практике они будут не очень эффективны.

Дженнаро и соавт. ввели в [15] понятие неразрешимых хеш-функций деления и показали, как получить практическое применение для них.

Из-за ограниченности объема статьи мы предлагаем заинтересованным читателям обратиться к полной версии для рассмотрения стандартных определений и обозначений, используемых в работе.

Статические псевдо-свободные группы

Для начала напомним определение псевдо-свободной группы, введенное Ривестом [8]. Чтобы отделить его от понятий, вводимых в работе, мы обозначаем данное как определение для статических псевдо-свободных групп.

Свободные абелевы группы. Для любого множества символов мы создаем для множества символов . Пусть и будут двумя непересекающимися множествами постоянных и переменных символов. Уравнением для X с постоянными из А является пара . Мы обычно записываем как и, заглядывая вперед (мы будем рассматривать только уравнения в абелевых группах), мы также можем записать его в качестве где and это целые числа. Пусть будет произвольной абелевой группа и это отображение постоянных в качестве элементов группы. Запишем для уравнения , решаемого в через . Оценка является решением для если

Любое уравнение для и можно рассматривать как уравнение над свободной группой через выражение соотносящее с . Легко показать[8] [9], что уравнение имеет решение в тогда и только тогда, когда для выполняется Мы будем называть такие уравнения тривиальными, в том смысле, что они имеют решения в свободной группе. Все другие уравнения будем считать нетривиальным.

Статические псевдо-свободные группы. Вычислительная группа состоит из (конечного) множества представлений для элементов группы вместе с реализацией двух групповых операций. На деле вычислительная группа будет псевдо-свободной, если трудно одновременно найти уравнение, невыполнимое в свободной группе, и решение для вычислительной группы. Стоит отметить, что если порядок группы известен, то найти решения для нетривиальных уравнений не составит труда. Таким образом, понятие псевдо-свободной группы имеет место для множества вычислительных групп где N выбирается случайным образом из множества индексов (как правило, это последовательность длины k) и соответствующий порядок не известен противнику.

В дальнейшем мы напомним формальное определение, данное Мицианцио в [9] (аналогичное данному Ривестом в [8]). Противник, который рассматривается в следующем определении статичен (в том смысле, что ему известно только описание группы, и никакой другой дополнительной информации). Чтобы отделить этот класс групп от других, используемых в работе, мы будем называть их статическими псевдо-свободными группами.

TemplateDifinitionIcon.svg Определение «Определение 1 (статические псевдо-свободные группы [9]).»
Множество вычислительных групп является статически псевдо-свободным, если для любого множества А размера , (где k это параметр безопасности), и для PPT алгоритма справедливо следующее. Пусть это случайно выбранный групповой индекс, а определяется случайным выбором из равномерных и для каждого Тогда вероятность (для выбора ), что для входных , противник получит уравнение и решение для пренебрежима в k.

Адаптивные псевдо-свободные группы

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

TemplateLemmaIcon.svg Лемма «Условия.»
Претендент случайным образом выбирает вид вычислительной группы (выбрав случайный индекс ) из множества . Затем он фиксирует значение для набора постоянных величин и передает пару противнику.
TemplateLemmaIcon.svg Лемма «Запрос уравнений.»
На этом этапе противник может просмотреть нетривиальные уравнения вместе с их решениями.
TemplateLemmaIcon.svg Лемма «Вывод.»
В какой-то момент противник должен создать новое "нетривиальное" уравнение (определяемое ) вместе с его решением


Обратим внимание, что приведенное выше описание включает в себя предположение, сделанное нами для простоты, что все уравнения одномерны. В общем случае, любое одномерное уравнение для А имеет вид: В случае статических псевдо-свободных групп, это ограничение снимается леммой, доказанной Мицианцио в работе [9]. В лемме говорится о том, что любое (многомерное) уравнение и его решение может быть преобразовано в одномерное уравнение с решением .Поскольку мы применяем определение тривиальности уравнения для многомерного случая (из-за ограниченности места подробно это описано в полной версии статьи), будет интересно посмотреть, если аналогичная лемма применима в контексте адаптивной псевдо-свободы.

Общее определение псевдо-свободы, упомянутое ранее оставляет открытыми два важных момента:

  1. Как определяются уравнения, для которых противник видит решения?
  2. Что будет являться "нетривиальным уравнением", когда известны остальные уравнения и решения?

Мы обсудим и дадим ответы на эти два вопроса в разделах 3.1 и 3.2 соответственно.

Распределения для адаптивных противников

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

Наиболее строгое и точное определение возможно, если рассматривать противника, который может выбирать уравнения (а именно их соответствующих показатели ()) любым ему угодным способом. В частности выбор уравнений может быть сделан адаптивным способом, когда противник запрашивает уравнение, видит его решения, затем переходит к следующему уравнению и так далее. Мы называем такое определение - "Строгая адаптивная псевдо-свобода". На практике такой подход может привести к невыполнимому определению (Неясно, может ли такая группа, как быть отнесенена к строго адаптивно псевдо-свободной в рамках разумных предположений (например, в рамках строгого RSA)). Поэтому мы остановим выбор на промежуточном варианте, когда противник может быть адаптивным, но в тоже время не может выбирать уравнения произвольным образом. Вместо этого, мы рассматриваем некоторый набор уравнений из всего множества, определяемый распределением, над которым противник имеет ограниченный контроль. Сформулируем это ограничение с помощью параметрического распределения для всех возможных уравнений. Выбор уравнения из такого распределения требует наличия параметра M определенной величины, задаваемой противником. Из распределения затем берется набор целых чисел ,который записывается как . Здесь будет целым числом (показателем для переменной), а будет вектором из целых чисел. Идея состоит в том, что когда параметр фиксирован, то будет фиксированным распределением, из которого берется набор .Обратите внимание, что граничные элементы могут быть смоделированы при соответствующем выборе .

Определение нетривиальных уравнений по отношению к остальным

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

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

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

Например, в случае если то также можно утверждать, что где первое равенство получено простым умножение известного уравнения на а второе получается из коммутативности и известных равенств. Вторая возможность показывает, что существуют вычислительные противники (при работе с вычислительными группами). В частности, если равенство вида может быть получены в вычислительной группе, то также можно получить и равенство (в случае, когда q просто определяется порядком групп). Кроме того, поскольку мы работаем с понятиями, не зависящими от порядка групп, то представленное равенство должно быть справедливо для любого q. Следующее определение вытекает из представленного выше рассуждения.

TemplateDifinitionIcon.svg Определение «Определение 2.»
Пусть это свободная абелева группа, а это произвольное бинарное отношение для . Пусть определяет минимальное совпадение в таким, что:


.


Тогда и тривиально равны по отношению к , если

Теперь точное определение для Пусть

Бинарный отношение для определяется как тогда и только тогда, если существует такое, что В данном случае представление слова с числовым параметром определяется (очевидным образом) тогда и только тогда, когда q делит В следующем утверждении говорится, что и являются по сути одинаковыми отношениями. Доказательство представлено в полной версии статьи.

TemplateDifinitionIcon.svg Определение «Утверждение 1.»
Пусть и определены как указано выше. В таком случае будет справедливо тогда и только тогда, когда

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

совместно с соответствующими решениями . (Обратим внимание, что это уравнения из вычислительной группы; решения этих уравнений могут не существовать в свободной группе). Пусть это свободная абелева группа на основе множества символов . Уравнения из создают бинарные отношения в , которые мы также будем обозначать .Таким образом Следующее определение является просто применением определения 2 к случаю одномерных уравнений.

TemplateDifinitionIcon.svg Определение «Определение 3. »
Уравнение будет тривиально по отношению к , если оно имеет решение в .

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

это уравнение, имеющее решение в . Также пусть будет решением для этого случая. Из определения для очевидно следует, что существуют в Q , такие что

Так как представленное равенство является стандартным для ,то представленное соотношение (через последовательное сопоставление показателей) преобразуется в следующее требование. Уравнение имеет решение, если существуют такие в и , что:

(для всех

(для всех

Обратное к данному определению также справедливо: если существуют такие целые и рациональные ,уравнение выполнено, то будет решением для уравнения в .

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

и

Эти величины зависят от , но чтобы не усложнять определения мы не приводим эту зависимость.

TemplateDifinitionIcon.svg Определение « Утверждение 2. (тривиальные уравнения относительно систем уравнений).  »
Уравнение для тривиально относительно тогда и только тогда, когда:
,

где .

Утверждение справедливо если задать для всех

Определение адаптивных псевдо-свободных групп

Далее мы приведем определение адаптивной псевдо-свободы для множества A из операций и для вычислительной группы  ; оно будет характеризоваться распределением , как описано в разделе 3.1.

TemplateDifinitionIcon.svg Определение «Условие.»
Претендент случайным образом выбирает вычислительную группу (выбрав случайный индекс ) из множества . Затем он фиксирует значение для множества A и параметрическое распределение показателей . Противнику дается на входе значение вместе с описанием вычислительной группы и параметрического распределения .
TemplateDifinitionIcon.svg Определение «Запрос уравнений. »
На этом этапе противник может запросить у претендента уравнения и просмотреть их решения. Точнее говоря, противник контролирует последовательность уравнений при помощи параметрического распределения . Для каждого запроса он выбирает параметр и предоставляет его претенденту. Претендент находит вычисляет решение для уравнения которым является величина , затем он передает набор значений противнику .
TemplateDifinitionIcon.svg Определение «Вывод.  »
После того как противник увидел решения, он должен выдать уравнение (определяемое величинами ) вместе с решением . Мы будем считать, что противник побеждает в игре, если является нетривиальным уравнением.
TemplateDifinitionIcon.svg Определение «Определение 4 (Адаптивные псевдо-свободные группы). »
G будет являться множеством адаптивных псевдо-свободных групп относительно распределения если для любого многомерного множества A любой противник одерживает победу в описанной выше игре лишь с ничтожной вероятностью.

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

Применение адаптивных псевдо-свободных групп

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

Подписи в адаптивно псевдо-свободных группах

Класс параметрического распределения .

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

  • - это двоичная строка, взятая в соответствии с некоторым эффективно отобранным распределением (которое может зависеть от М), для которой совпадения происходят с ничтожной вероятностью;
  • , где неразрешимой функцией (См. раздел 1.1), в свою очередь и являются полиномами;
  • т.е. для некоторого эффективно отобранного распределения .

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

Кроме того, необходимо чтобы было для всех противников таким, чтобы вероятность следующего выражения была пренебрежимо мала:

Построение схем подписей.

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

  • .Пусть и будут множествами постоянных и переменных символов. Алгоритм генерации ключей выбирает случайную группу из множества G,фиксирует значение для символов из множества A, и в конце устанавливается в качестве открытого проверочного ключа и проверки и в качестве секретного ключа для подписи. Входные размеры , берутся в качестве размеров для сообщений для схем подписей.

. Алгоритм подписания действует следующим образом:

  • используется для решения уравнения соответственно используется для x. Алгоритм выводит в качестве подписи для М.

. Для проверки подписи для сообщения M, алгоритм будет действовать следующим образом:

  • Сначала проверяется, чтобы выполнялось и в группе при распределении .
  • Если оба равенства справедливы, то выводится 1, в противном случае 0.

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

TemplateDifinitionIcon.svg Определение «Теорема 1. »
Если G является множеством адаптивных псевдо-свободных групп по отношению к распределению , тогда схема подписей будет в строгом смысле достоверна под выбранной атакой.

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

TemplateDifinitionIcon.svg Определение «Следствие 1.  »
Если G является множеством адаптивных псевдо-свободных групп по отношению к распределению , тогда схема подписей будет достоверна под выбранной атакой.

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

Сетевое кодирование подписей из адаптивно псевдо-свободных групп

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

Предлагаемая схема сетевого кодирования подписей. Вниманию заинтересованных читателей предлагаются полная версия статьи или работы [17][18]. В данном разделе мы опишем предлагаемую нами схему сетевого кодирования подписей. Сначала же мы обсудим некоторые дополнительные детали, необходимые для правильного понимания схемы. Как уже упоминалось, файл для подписи выражается в виде множества векторов состоящих из n компонент каждый. Такие векторы будут предваряться вместе с унитарными векторами (из m компонент для каждого). Результирующий вектор мы обозначим .

Используя аналогичные обозначения, как в [18] зададим (для некоторых q) множество, из которого берутся случайным образом коэффициенты. Обозначим через L верхнюю границу для пути от источника к любой цели. Параметром задается наибольшее возможное значение u-координаты создаваемых векторов. Более того, обозначив через М верхнюю границу величины координат начальных векторов , положим .

Пусть будет параметрическим распределением, таким, что оно принимает в качестве входных данных некоторый случайный идентификатор fid векторное пространство с границей . Пусть будет параметром безопасности, а l в свою очередь таким целым числом, что , вычислим , где является функцией деления. Далее для каждого производятся следующие операции. Сначала выбирается (равномерно) - битное случайное целое и выводится . В итоге для выводится набор .

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

Пусть G будет множеством групп, являющимся адаптивно псевдо-свободным по отношению к .Тогда мы можем получить следующую схему подписей .Пусть и будут множествами постоянных и переменных символов. Алгоритм генерации ключей случайным образом группу из множества G, фиксирует параметр для символов из A, и наконец задает в качестве и в качестве секретного ключа. Входные величины для берутся в качестве множеств m-мерных векторов, компонентами которых являются натуральные числа, величины не более чем М.

.Алгоритм подписания осуществляется следующим образом. Выбирается случайный идентификатор fid для векторного пространства V. Далее, применяется для того, чтобы получить .И в конце для до при помощи решается уравнение :

Пусть удовлетворяет будет подписью для . Алгоритм выводит в качестве подписи для V.

. Для того, чтобы проверить подпись σ для векторного пространства V, алгоритм будет работать следующим образом:

  • Сначала проверяется, справедливы ли равенства и для группы и для .
  • Если равенства справедливы, то выводится значение 1, в противном случае 0.

. Используется, чтобы объединить подписи для векторов с одинаковым параметром fid.

  • Отбрасываются ,имеющие отрицательные или большие чем координаты u, или имеющие отрицательные или большие чем координаты . Остальные векторы объединяются.
  • Выбираются случайные величины ,задается и выводится подпись для w после вычисления

Не сложно изменить доказательство следствия 1, чтобы получить следующую теорему.

TemplateDifinitionIcon.svg Определение «Теорема 2.»
Пусть G будет множеством групп, являющимся адаптивно псевдо-свободным по отношению к ,тогда схема подписей , описанная выше, будет безопасной схемой сетевого кодирования подписей.

Группа RSA как адаптивно псевдо-свободная

В разделе 3 мы определили понятие адаптивных псевдо-свободных групп, а в разделе 4 определен класс параметрических распределений (так называемый ), позволяющий создавать подписи на единственном предположении, что множество групп является адаптивно псевдо-свободным по отношению к . На данном этапе важно найти вычислительную группу, являющуюся адаптивно псевдо-свободной. Как было доказано Мицианцио в [9][16], единственная группа из известных, которая будет псевдо-свободной, это RSA группа целых чисел по модулю N, где N это произведение двух "безопасных" простых чисел, отбор которых идет из элементов . Поэтому мы стремимся доказать адаптивную псевдо-свободу для таких групп.

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

Рассмотрим ,где .Для любого входного выводится набор значений ,определенный следующим образом:

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

Алгоритм проверяет, чтобы , и чтобы являются связанными с М. Несложно удостовериться в том, что содержится в классе , определенном в разделе 4.1.

Сформулируем следующую теорему (доказательство представлено в полной версии статьи).

TemplateDifinitionIcon.svg Определение «Теорема 3. »
Если строгое RSA предположение справедливо, то является адаптивно псевдо-свободной по отношению к .

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

TemplateDifinitionIcon.svg Определение «Следствие 2. »
Если строгое RSA предположение справедливо, то будет адаптивно псевдо-свободной по отношению к

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

TemplateDifinitionIcon.svg Определение «Следствие 3.  »
Если строгое RSA предположение справедливо, и СН хамелеонная хэш-функция, то будет адаптивно псевдо-свободной по отношению к

Доказательство в данном случае такое же, как в следствии 2. Суть заключается в том, что можно использовать хамелеонное свойство функции СН при моделировании, для того чтобы «подготовить» значения заранее.

Нестрогая адаптивная псевдо-свобода RSA групп. Понятие не строгой адаптивной псевдо-свободы можно рассматривать в случае, где противник вынужден выбирать параметры для своих запросов в начале игры, то есть, до получения описания группы от претендента. В полной версии статьи показано, что доказательству теоремы 3 остается в силе, даже в отношении более общего распределения, чем , где все множество должно быть связано с М. В таком случае не сложно увидеть, что, начиная с не строго адаптивных псевдо-свободных групп, результаты раздела 4.1 приводят к созданию схем подписей, которые будут не строго безопасными.

Границы для подписей на основе RSA алгоритма

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

Подписи Крамера-Шоупа [10]. Хотя схема Крамера-Шоуп основана на сложности решения системы двух уравнений, мы отметим, что только для одного из этих двух уравнений требуется процесс подписания для нахождения решения (при использовании секретного ключа), тогда как другое уравнение на деле является хамелеонной хэш-функцией для сообщения. Данная схема является частным случаем нашего подхода, выдвинутого в следствии 3.

Подписи Фишлина [11]. Схема Фишлина может быть рассмотрена как частный случай нашей системы, так как распределение показателей для него вписывается в рамки теоремы 3 для .

Подписи Камениша-Лысянской [12]. Эта схема может рассматриваться как частный случай нашей системы, так как распределение ее параметров это частный случай для описанного в следствии 1.

Подписи Чжу [13][19]. Случай схемы Чжу охватывается нашей системой, так как распределение его параметров является частным случаем .

Подписи Хофхайнца-Кильтца [14]. Хофхайнц и Кильтц показали в работе [14], как использовать программируемые хэш-функции, чтобы получить новые эффективные схемы подписей, на основе строгого RSA алгоритма. Не трудно показать, что безопасность их основной схемы5 вытекает из следствия 2.

Подписи Дженнаро-Галеви-Рабина [15]. Схема, предлагаемая в работе [15], соответствует нашей системе для не строго безопасных схем подписей (см. раздел 5), когда используется распределение, в котором и Н является хэш-функцией деления.

Новая сетевая подпись для строгого RSA алгоритма. Легко заметить, что при объединении результатов теоремы 3 и теоремы 2 мы получаем схему сетевого кодирования подписей, приведенную в разделе 4.2, безопасность которой основана на строгом RSA алгоритме в рамках стандартной модели. Отметим, что наша схема не столь эффективна, как предложенная Дженнаро и соавт. в работе [18], но она является безопасной в рамках стандартной модели.

Заключение

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

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

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

Мы благодарим Эйке Кильтца за полезные советы и пояснения относительно работы[14]. Работа, описанная в данной статье была поддержана Европейской Комиссией в рамках программы ICT по контракту ICT-2007-216676 ECRYPT II.

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

  1. Dipartimento di Matematica e Informatica, Universit`a di Catania, Italy, E-mail: catalano@dmi.unict.it
  2. ´Ecole Normale Sup´erieure, CNRS - INRIA, Paris, France, E-mail: dario.fiore@ens.fr
  3. Dept. Computer Science, University of Bristol, UK, E-mail: bogdan@cs.bris.ac.uk

Примечания

Литература

  1. Bellare, M., Rogaway, P.: Random oracles are practical: A paradigm for designing efficient protocols. In: ACM CCS 1993, Fairfax, Virginia, USA, November 3-5, pp.62–73. ACM Press, New York (1993)
  2. Canetti, R.: Universally composable security: A new paradigm for cryptographicprotocols. In: 42nd FOCS, Las Vegas, Nevada, USA, October 14-17, pp. 136–145.IEEE Computer Society Press, Los Alamitos (2001)
  3. Abadi, M., Rogaway, P.: Reconciling two views of cryptography (the computational soundness of formal encryption). Journal of Cryptology 20(3), 395 (2007)
  4. Backes, M., Pfitzmann, B., Waidner, M.: A composable cryptographic library with nested operations. In: ACM CCS 2003, Washington D.C., USA, October 27-30, pp. 220–230. ACM Press, New York (2003)
  5. Micciancio, D., Warinschi, B.: Soundness of formal encryption in the presence of active adversaries. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 133–151. Springer, Heidelberg (2004)
  6. Dolev, D., Yao, A.C.: On the security of public key protocols. In: FOCS, pp. 350–357 (1981)
  7. Hohenberger, S.: The cryptographic impact of groups with infeasible inversion.Master’s thesis, Massachusetts Institute of Technology, EECS Dept. (2003)
  8. 8,0 8,1 8,2 8,3 8,4 8,5 Rivest, R.L.: On the notion of pseudo-free groups. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 505–521. Springer, Heidelberg (2004)
  9. 9,0 9,1 9,2 9,3 9,4 9,5 Micciancio, D.: The RSA group is pseudo-free. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 387–403. Springer, Heidelberg (2005)
  10. 10,0 10,1 Cramer, R., Shoup, V.: Signature schemes based on the strong RSA assumption.In: ACM CCS 1999, Kent Ridge Digital Labs, Singapore, November 1-4, pp. 46–51. ACM Press, New York (1999)
  11. 11,0 11,1 Fischlin, M.: The Cramer-Shoup strong-RSA signature scheme revisited. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 116–129. Springer, Heidelberg (2002)
  12. 12,0 12,1 Camenisch, J., Lysyanskaya, A.: A signature scheme with efficient protocols. In: Cimato, S., Galdi, C., Persiano, G. (eds.) SCN 2002. LNCS, vol. 2576, pp. 268–289. Springer, Heidelberg (2003)
  13. 13,0 13,1 Zhu, H.: New digital signature scheme attaining immunity to adaptive chosenmessage attack. Chinese Journal of Electronics 10(4), 484–486 (2001)
  14. 14,0 14,1 14,2 14,3 14,4 Hofheinz, D., Kiltz, E.: Programmable hash functions and their applications. In:Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 21–38. Springer, Heidelberg (2008)
  15. 15,0 15,1 15,2 15,3 Gennaro, R., Halevi, S., Rabin, T.: Secure hash-and-sign signatures without the random oracle. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 123–139. Springer, Heidelberg (1999)
  16. Cachin, C., Micali, S., Stadler, M.: Computationally private information retrieval with polylogarithmic communication. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 402–414. Springer, Heidelberg (1999)
  17. 17,0 17,1 Boneh, D., Freeman, D., Katz, J., Waters, B.: Signing a linear subspace: Signatureschemes for network coding. In: Jarecki, S., Tsudik, G. (eds.) PKC 2009. LNCS,vol. 5443, pp. 68–87. Springer, Heidelberg (2009)
  18. 18,0 18,1 18,2 18,3 18,4 18,5 Gennaro, R., Katz, J., Krawczyk, H., Rabin, T.: Secure network coding over the integers. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp.142–160. Springer, Heidelberg (2010)
  19. H. Zhu. A formal proof of Zhu’s signature scheme. Cryptology ePrint Archive, Report 2003/155 (2003), http://eprint.iacr.org/