Ограничения на преобразования групп составного порядка в группы простого порядка: случай циклически-оптимальных подписей вслепую

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 23:52, 30 октября 2015.

Оригинал

Аннотация. Начиная с работы Грота и Сахаи, появился большой интерес к актуальному преобразованию схем основывающихся на парах в группы составного порядка для получения эквивалентных им групп простого порядка. Метод достижения такого преобразования недавно был предложен Фриманом, который выявил два свойства парных значений, используя группы составного порядка – «отмена» и «проецирование» - на которых основывается много схем, и показал, как какое-либо из этих свойств можно получить для групп простого порядка.

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

Введение

Группы составного порядка были представлены для криптографии основывающейся на парных значениях в 2005 Бонехом, Гохом, и Ниссимом [12] и с тех пор используются для реализации большого количества криптосистем (см., например, схемы Фримана [24]). В тоже время, ограниченное число семейств эллиптических кривых для которых применимы группы составного порядка и наличие больших размеров параметра связанного с группами составного порядка (см. [23,13]) мотивировало исследование преобразования данных схем в более упрощённые для групп простого порядка.

В одной из первых работ для объединения набора параметров группы составного и простого порядков, Грот и Сахай [31] разработали не интерактивные схемы с нулевым разглашением, которые можно было представить не только для составной или простой группы, но можно также было рассмотреть вариант и другого представления. Это в свою очередь упрощает гибкость реализации новой абстракции для парной криптографии посредством модулей над конечными коммутативными кольцами со связанным билинейным отображением; эта абстракция применяется для одновременного использования трёх различных криптографических предположения: предположение о сокрытии Подгруппы (SGH) Бонеха, Гоха, и Ниссима [12] в группах составного порядка; предположение о Линейном Решении (DLIN) Бонеха, Боена, и Шачама [11], и также для него семейство k-линейных обобщений [45,33], для групп простого порядка; и так называемое предположении симметрического расширения Диффи-Хеллмана [7], также для групп простого порядка.

В более поздних работах Фримана [24], Гарга, Сахаи и Уотерса [27] были предложены методы преобразования схем безопасных в условиях составного порядка в также безопасные схемы (при других, но всё же аналогичных по смыслу предположениях), но уже для простого порядка. Фриман, в частности, выявил два свойства парных значений групп составного порядка, а именно, отмену и проецирование, и показал, как каждое из них можно получить для групп простого порядка. Также он показал, как преобразовать несколько известных криптосистем, основывающихся на одном из этих свойств из групп составного порядка в группы простого порядка.

Наш вклад: ограничения на преобразование составного порядка в простой. В данной работе мы показали ограничения реализации преобразования составного-в-простой такие, о которых упоминалось выше, принимая во внимание то, что некоторые схемы физически нельзя преобразовать. В нашей основной теореме, Теорема 6.5, мы показали, что не парные значения над группами простого порядка – за исключением пренебрежимо малого количества случаев – могут обладать как свойством отмены, так и проецирования, когда неразличимость подгруппы основывается на основном k-Линейном методе, при этом «основной» означает, что мы следуем предположению настолько точно насколько это возможно.

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

Подписи вслепую были предложены Чаумом в 1982 [17]. В схеме подписи вслепую пользователь взаимодействует в протоколе с подписывающим участником для получения подписи сообщения, выбранного им. Когда завершается выполнение протокола, пользователь получает подпись, но подписывающему не известно ничего о сообщении, которое он подписал. Подписи вслепую использовались как составная часть различных приложений, включающих такие как электронные деньги [20] и электронное голосование [19].

Одним из полезных свойств подписи вслепую является параллелизм. К примеру, если подпись вслепую используется в электронной денежной системе, то на безопасность не оказывает никакого влияния то, что подписывающий участник оперирует в нескольких протоколах параллельно, хотя это и позволяет осуществить некоторые атаки отказа в обслуживании. Параллелизм в свою очередь довольно трудно получить для случая с подписями вслепую, чем для других криптографических протоколов. Т.к. множество схем подписи вслепую имеют доказуемую безопасность только для определённого числа выполнений протокола, но проблемы возникают не только с доказательствами. В одном из своих примеров, Мартинет, Поупард, и Сола [38] показали, что подписи, в частности схема подписи вслепую Чао, Лин и Ксу [16] можно подделать, если подписывающий участник оперирует параллельно с двумя пользователями.

Наш вклад: циклически-оптимальная схема подписи вслепую. Как упоминалось выше, мы предлагаем новую схему подписи вслепую основанную на парных значениях. Наш протокол подписи вслепую является циклически-оптимальным: он состоит только из 2 этапов (запрос и ответ), что обеспечивает нам безопасность даже при параллельной работе протокола подписи. Наша схема, в частности, имеет доказательство безопасности (без случайных оракулов) в общей связанной строчной модели, и основывается на фальсифицированной гипотезе и не интерактивных предположениях: вычислимости Диффи-Хеллмана и Сокрытие Подгруппы. Эти предположения более подходят, чем использованные ранее для практической реализации параллельной подписи вслепую, включая те, что были для модели случайного оракула. («Практическая» в данном контексте означает то, что она не основывается на общих NIZK при NP в качестве его составной части.) Нашу схему в действительности можно расширить для получения практичной схемы подписи вслепую [3] с теми же свойствами.

Наши подписи вслепую включают в себя схему подписи Уотерса [46] с не интерактивными доказательствами (при неразличимых свидетельствах) рассмотренную отчасти в работах Грота, Островского, и Сахаи [30,29,31]. В данной структуре наша схема основывается на схеме групповой подписи Боена и Уотерса [15]. Основным минусом нашей схемы, отличающим её от групповой подписи Боена-Уотерса, является её реализация бита во времени, которая делает запрос пользователя на подпись вслепую довольно ёмким: иногда это 40 килобит при 1024-битном уровне безопасности. Однако, ответ подписывающего и результирующие подписи довольно малы по размерам.

Схожие работы. Литература по подписи вслепую довольно различна и многообразна. Ниже мы коротко опишем наиболее современные схемы с параллельной безопасностью; см. [5,4] для более полного их описания.

В модели случайного оракула, существует довольно эффективная циклически оптимальная схема подписи вслепую, предложенная Чаумом [18] и Болдырёвой [10], особенностями которой являются короткие открытые ключи, короткие подписи, и эффективный протокол подписи вслепую. К несчастью, доказательства безопасности таких схем основывается на стойких интерактивных предположениях: предположение инверсии известного целевого значения RSA [9], и предположении выбранного целевого значения CDH.

Для общей связанной строчной модели также были представлены несколько практических схем подписи вслепую с параллельной безопасностью. В отличие от наших схем, они основываются на предположениях, которые являются интерактивными или размерность в утверждении которых растёт при сокращении количество запросов (т.е. «q-типными»). Киаяс и Зоу [35] опубликовали четырёхступенчатую схему подписи вслепую и схему подписи частично вслепую безопасные при (интерактивном) LRSW предположении [37], предположении Пайлера [42], и DLIN. Окамото в [40] показал четырёхступенчатую схему подписи вслепую и схему подписи частично вслепую основанные на (q-типном) предположении о двух стойких переменных Диффи-Хеллмана и Пайлера. Фучсбауер [25] описал двухступенчатую схему подписи вслепую основанную на (q-типном) стойком предположении о скрытом ассиметрическом удвоении Диффи-Хеллмана, предположении о слабой ассиметрической гибкости CDH, и DLIN. Помимо этого, Абе, Хараламбиев и Окубо [4] описали двухступенчатую схему подписи вслепую основанную на (q-типном) предположении одновременного нахождения гибких парных значений и DLIN. (Две последние работы можно встретить в [2].)

Также в общей строчной модели, подписи вслепую использующие общие NIZK для NP (вследствие чего практически не реализуемые) были представлены Джульсом, Лаби, и Островским [34], Фишлином [22], и Абе, Окубо [5]. Схемы Фишлина и Абе-Окубо являются циклически-оптимальными.

Окамото [40] впервые отметил, что подпись Уотерса можно совместить с доказательствами неразличимого по признакам свидетельства для простого NP языка, чтобы получить подпись вслепую и практически реализуемую подпись вслепую. Нашу схему можно рассматривать как частный случай методики Окамото (хотя мы по другому подписываем), в которой преимущество над доказательством Грота-Островского-Сахаи будет в исключении привязки к циклу.

До недавнего момента, не было пока схем подписи вслепую с параллельной безопасностью для общей модели с открытым ключом. Первая такая схема была предложена Хазаем и др. [32]; она основывалась на общих NIZK, и её циклическая сложность была полиномиально-логарифмической для количества параллельных итераций при гарантированной безопасности.

Приложения и расширения.В качестве приложения для наших методов, мы показываем (в полной версии нашей работы [39]) как наши подписи вслепую можно использовать для IBE системы Уотерса [46] для получения IBE схемы подписи вслепую, которая рассмотрена Грином и Хохенбергером в [28]. В сравнении с протоколом извлечения подписи вслепую Грина и Хохенбергера, наш протокол достигает параллельной безопасности, но при этом необходимо добавить ещё общую связующую строку и зависимость от SGH предположения. Более того, подпись Уотерса в действительности можно расширить до иерархической подписи основанной на идентификации (см. [43]); применение нашей схемы на 2 уровне для результирующей подписи позволяет также получить подпись вслепую основанную на идентификации [47] с параллельной безопасностью для общей связанной строковой модели. Альтернативным вариантом может быть использование групповой подписи Боена-Уотерса [15] на 1 уровне иерархии и нашей подписи вслепую на 2 уровне, что даёт подпись вслепую [36] с параллельной безопасностью для общей связанной строковой модели.


Исходные математические данные

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

Модули

Сперва рассмотрим определение модуля; оно служит основополагающим элементом для нашей схемы подписи вслепую, и для привязок Грота-Сахаи использующихся в нашей схеме. (См. [21, часть 10] для более подробного описания моделей.)

Определение 2.1. Пусть есть конечное коммутативное кольцо. –модуль A есть абелева группа (A,+,0) такая, что существует оператор (а именно, скалярное умножение) , обозначенный как удовлетворяющий следующим 4 свойствам для всех и  :

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

Концепция модульного обобщения заключается в векторном пространстве: если это поле, то определения -модуля и -векторного пространства совпадают. Концепция модуля также обобщается концепцией абелевой группы, т.к. любую абелеву группу можно рассмотреть как -модуль. Если А изоморфично как абелевой группе, то r является рангом А. Если поле, то ранг модуля будет таким же как размерность векторного пространства. В криптографии, в основном оперируют - и –модулями; к примеру, любую конечную группу степени p можно рассматривать как –модуль.

Привязки Грота-Сахая

Грот и Сахай [31] выделили 2 типа привязок: привязки к элементам в –модуле А, и привязки к элементам в кольце . Для нашего случая, необходимы только привязки к битам; мы можем ещё больше всё упростить с помощью приравнивания А к G для нашей билинейной группы G.

Для формирования привязок к модульным элементам, Грот и Сахай определили -модуль В и два гомоморфизма и . Эти отображения определены таким образом, чтобы некоторые элементы в для всех i и были не тривиальны для всех x, не входящих в . Привязка к тогда определяется как для случайных значений . Это означает, что элементы выступают в роли ключа для схемы привязки, и что общая связующая строка будет . Получается два случая:

  • Сокрытие ключей: в этом случае, элементы генерируют модуль В; другими словами, . Это подразумевает под собой, что , следовательно, c(x) будет сокрыто (т.к. каждая привязка будет случайным элементов В).
  • Задание ключей: в данном случае, и для некоторого соответствующего пространства входов х. Для определения данного пространства, отметим, что с определяет класс где находится . Т.о. для того, чтобы привязка задавалась необходимым образом мы должны ограничить пространство входов х до инверсии ; т.к. нам известно, что , и и будут не тривиальными и т.о. данное ограничение на область определения будет значимым. (Т.к. В есть абелева группа, частный модуль будет всегда определён.)

Ясно, что для этих определений набор ключей не может быть задан и сокрыт одновременно, т.к. каждая установка требует наличия определённых свойств ключей привязки . Для получения какого-либо свойства подписи вслепую, однако, необходимо чтобы обе установки были неразличимы по признакам. Поэтому необходимо предположение, которое обеспечит нам это; выбор предположения зависит от конкретного примера.


Определения безопасности для подписей вслепую

Теперь дадим определение схемы подписи вслепую или подписи частично вслепую для общей связанной строчной (CRS) модели в виде набора 4 протоколов: Setup() алгоритм, который выводит , KeyGen () алгоритм, который выводит пару ключа подписи (pk, sk), BlindSign протокол, состоящий из операции (в котором подписывающий выводит success, если протокол успешно завершился, а пользователь выводит success и раскрытую подпись ), и наконец, алгоритм, который выводит accept если подпись корректна и fail если нет.

В общем случае есть два свойства, которым должны удовлетворять подпись вслепую и подпись частично вслепую: сокрытие и стойкость. Проще говоря, сокрытие означает, что в процессе подписи пользователем сообщения, подписывающий не получает никакой информации о подписываемом им сообщении. А стойкость означает, что если пользователь взаимодействует с подписывающим l раз, то он должен произвести l подписей и не более (т.е. в частности он не может произвести l + 1). Теперь распишем эти свойства более подробно.

Подписи вслепую

Общие определения подписей вслепую представлены Джулсом, Лаби, и Островским в [34], но оба свойства были рассмотрены конкретно по данному вопросу в работе Чаума [17], также стойкость анализировалась в общем случае в работе Поинтчеваля и Стерна для безопасности аргументов подписей [44].

В обобщении Джулса-Лаби-Островского, свойство сокрытия определяется следующим образом: злоумышленнику известна пара открытый-секретный ключ и выход сообщений . Далее он принимает участие в подписывающих протоколах наряду с доверенными пользователями: первый пользователь запрашивает подпись для сообщения , а второй для сообщения , где b это случайный бит неизвестный злоумышленнику. Затем злоумышленник задаёт результирующие подписи , , но только при том, что обе итерации успешно завершаются, а его целью в данном случае будет выявить бит b (для заданных сообщений, соответствующих подписей, и транскрипций подписывающего протокола).

В данной работе мы использовали стойкую версию свойства сокрытия, что позволяет злоумышленнику генерировать пару ключа подписи самому, возможно путём вредоносного воздействия. Это допущение стойкости было предложено независимо в нескольких недавних работах [1,41,35].

Свойство же стойкости непосредственно можно определить следующим образом: злоумышленнику дан открытый ключ и он участвует в нескольких выполнениях протокола подписи вслепую наряду с подписывающим; злоумышленник может выбрать как именно будут чередоваться выполнения. Т.о., злоумышленник реализует всё успешно, если он может вывести l + 1 конкретных пар сообщение-подпись , где l есть число выполнений, в которых подписывающий выводит success.

В данном определении пары сообщение-подпись и рассматриваются как разные, даже если (т.е. если и есть две разные подписи одного сообщения) для . К сожалению, это также означает, что любая схема подписи, в которой подписи можно перераспределить случайным образом (как наша схема подписи, что мы увидим в Разделе 4), будет автоматически не удовлетворять свойству стойкости. В связи с этим мы ослабим свойство путём постановки условия, что злоумышленник не способен вывести l + 1 пару сообщение-подпись, в которых все сообщения различны. Это преобразованное определение также было рассмотрено ранее Окамото [41].

Скомпоновав всю эту информацию вместе мы дали общее определение безопасности для схем подписи вслепую в полной версии нашей работы [39].

Подпись частично вслепую

Данные свойства безопасности подписей вслепую также можно расширить до подписей частично вслепую; это обобщение предложено Абе и Окамото [6]. При подписи частично вслепую, злоумышленник выводит 2 информационные строки и в дополнение к сообщениям . Затем он взаимодействует с двумя разными пользователями также как и раньше, кроме того, что в данном случае первый запрос подписи пользователя для использует , а второй запрос подписи для будет с . Злоумышленник задаёт результирующую подписи , если оба взаимодействия были успешными и если . Как и прежде его целью является выявление бита b.

Свойство стойкости также очень схоже со свойством для подписи вслепую; здесь, злоумышленнику позволено выбрать info строку для каждой итерации с подписывающим. Целью злоумышленника является вывод info строки , а также l + 1 пар сообщение-подпись , где l есть число взаимодействий, в которых подписывающий выводит , при использовании информационной строки .


Основополагающая Схема подписи

Для нашей основополагающей схемы подписи мы используем немного модифицированную версию схемы подписи Уотерса [46]. В действительности, нам необходимо только обобщить схему подписи Уотерса путём рассмотрения её относительно языка модулей, т.о. чтобы можно было использовать её в совокупности с привязкой Грота-Сахая для создания нашей схемы подписи вслепую.

Задание CRS

Для подписи Уотерса необходимые элементы для общей связующей строки будут описываться билинейной группой G, целевой группой и отображением , также как и генераторы для G, где k обозначает длину подписываемого сообщения. Теперь добавим элементы расписанные в Разделе 2.2: начнём с кольца R такого, что G можно представить как R-модуль. Затем добавляем R-модуль В, отображение , отображение , и билинейное отображение , которое также нам необходимо для утверждения целевого модуля и результирующих отображений . Это означает, что CRS будет . Отношения между всеми этими отображениями комплексно показаны на следующем рисунке:

Файл:Ogr-1.png
Рис.1. Коммутативная диаграмма для наших модулей.

Протокол подписания

В нашей обобщенной подписи Уотерса, размер пространства сообщения будет для некоторого значения k (например, для того, чтобы использовать хэш подпись с SHA-1 в качестве хэш функции нам необходимо выбрать k = 160). Как отмечалось выше, CRS, разделяемое между пользователем и подписывающим, будет содержать k + 1 случайных генераторов G.

  • Setup(): Выводим кортеж , который был рассчитан так как описано в предыдущем разделе.
  • KeyGen(): Выбираем случайное значение и устанавливаем . Открытый ключ будет pk = A, а секретный (в действительности допустимо и ).
  • Sign(,sk,M): Записываем сообщение побитно как и записываем . Выбираем случайное и вычисляем

и

Выводим подпись .

  • Verify ( ): Опять записываем общение побитно и также записываем подпись как , а открытый ключ как pk = A. Проверяем удовлетворяют ли эти значения следующему уравнению (1):

Если да, выводим accept; в противном случае fail. Одним хорошим свойством подписи Уотерса (и нашей расширенной подписи Уотерса) является то, что кто угодно может получить новые случайные значения для подписи с помощью и вычисляя и . Т.к. это приводит к и , данный процесс в действительности выдаёт нам корректную подпись. В частности, случайность в результирующей подписи будет информационно-теоретически зависеть от случайности r выбранного подписывающим для подписи .

Напомним, что предположение вычисления Диффи-Хеллмана (CDH) использующееся для подписи Уотерса будет заключаться в:

Предположение 4.1.Пусть это алгоритм выводящий кортеж (q, G, g), где G это группа порядка q (не обязательно простая), а g генератор g. Говорят, что G удовлетворяет вычислительному предположению Диффи-Хеллмана если вычислительно неосуществим расчёт значения заданного кортежа . Говоря более общими словами, для всех PPT злоумышленников А существует пренебрежимо малая функция и параметр безопасности такие, что следующее уравнение выполняется для всех  :

Схема подписи Уотерса действительно стойкая если G удовлетворяет CDH предположению. В нашей расширенной версии, схема подписи будет действительно стойкой, если В удовлетворяет CDH предположению. Доказательство заключается в тривиальном расширении доказательства Уотерса, которое по понятным причинам мы сюда не включаем.


Наша схема подписи вслепую

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

Установки для CRS

В наш CRS должны входить все необходимые элементы для привязок Грота-Сахая и к тому же значения для кортежа из раздела 4.1. Это значит, что наш CRS будет, где элементы являются задающимися ключами для привязок Грота-Сахая. Особенность в том, что элементы генерируют корректный подмодуль модуля В использующегося в схеме подписи Уотерса.

Протокол подписи частично вслепую

В данном протоколе пользователь и подписывающий имеют доступ к информационной строке info. В конце протокола, пользователь получает подпись info || M для сообщения М, в то время как подписывающий не получает никаких данных кроме того, что для М применялась info. К тому же, пользователь и подписывающий согласуют длину строки info; назовём её при . Установим соответственно для подписи полностью вслепую, а при получаем обычную (обобщённую) схему подписи Уотерса.

  • Setup(): Выводим , который был рассчитан так как описано в предыдущем разделе (Раздел 5.1).
  • KeyGen(): Та же операция что и KeyGen из Раздела 4.2.
  • User( , pk, info, M): сперва запишем информационную строку побитно и аналогично запишем сообщение . Теперь для каждого i такого, что , выберем случайные значения и вычислим

и ,

где выступает в роли GS привязки для бита , а – доказательства, что значение содержащееся в по сути либо 0 либо 1. Отправляем кортеж как запрос участнику (и сохраняем некоторую информацию как state).

  • Signer( , sk, info, reg): Сперва, записываем info=, и . При получении запроса, проверяем, чтобы каждый является соответствующей привязкой для 0 или 1 с помощью (2)

для каждого . Если данное уравнение неверно для любого значения i, завершаем протокол и выводим . В противном случае, вычисляем значение

И наконец, выбираем случайное значение и вычисляем

, и для .

Установим , отправим кортеж обратно пользователю, т выведем success и info.

  • User(state, ): Сперва, проверяем получены ли корректно путём подстановки в уравнение (3)

для каждого . Если это уравнение не выполняется для некоторого j, прерываемся и выводим . В противном случае, раскрываем подпись вычисляя (4)

и

Затем проверяем корректная ли это подпись для info || M выполняя Verify( , pk, info || ). Если на этом шаге выводится fail, прекращаем протокол и выводим . Если выводится accept, то перераспределяем случайные значения подписи с помощью выбора случайного значения и вычисления

и .

Конечная подпись будет ; выводим при info и получении success.

  • Verify(, pk, M, ): Выполняем тоже самое что и в Verify из Раздела 4.2.

Теорема 5.1. Схема подписи вслепую представленная выше является корректной и с подписью частично вслепую, по предположению, что значений в процедурах задания и сокрытия неразличимо по признакам.

Доказательство Теоремы 5.1 показано в полной версии данной работы [39]. Теорема демонстрирует корректность и (частичное) сокрытие, но не показывает стойкость. Для того, чтобы доказать последнее свойство необходимо определить свойства парных значений, заимствованных у Фримана [24 параграф 3] для нашего случая:

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

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

Как мы увидим ниже пары Е обе обладают этими свойствами (в соответствие аналогичного разложения ), когда используются группы составного порядка при предположении о сокрытие подгруппы (SGH). Т.к. SGH также обеспечивает необходимые свойства неразличимости по признакам, мы получаем следующую теорему, доказательство которой можно найти в полной версии данной работы [39]:

Теорема 5.4. Схема подписи вслепую указанная выше является стойкой при SGH предположении и предположении о том, что модифицированная схема подписи Уотерса из Раздела 4 является существенно стойкой для подмодулей .

Реализация для SGH предположения

Сперва напомним читателю, что такое предположение о сокрытие подгруппы (SGH):

Предположение 5.5 ([12]). Пусть G это алгоритм выводящий кортеж (p,q, G, ,e), где G и это группы порядка n = pq, а есть невырожденное билинейное отображение. Говорят, что G удовлетворяет предположению о сокрытие подгруппы, если вычислительно неосуществим расчёт разницы между элементом G и элементом . Говоря более общими словами, для всех PPT злоумышленников А существует пренебрежимо малая функция и параметр безопасности такие, что следующее уравнение выполняется для всех :

Для реализации нашей схемы подписи вслепую при этом предположении, используем группу G порядка n = pq с простыми p, q. Определим B = G и для идентичного отображения; это означает, что мы можем использовать E = e. Нам нужен только один элемент , а именно такой, что генерирует в установке задания и генерирует группу G целиком в установке сокрытия. SGH предположение говорит о том, что этот выбор неразличим по признакам. Можно также описать наше отображение как т.к. имеет порядок q. В связи с тем, что это все генераторы для G и , можно заметить, что отображение в действительности покажет бит .

Т.к. генерирует либо G либо , мы получим B= G_p \times G_q </math>, что означает – предположение для безопасности нашей подписи вслепую при CDH будет стойким в . Чтобы показать, что парное значение е обладает свойством отмены, отметим, что каждый элемент можно записать как для некоторого и каждого элемента можно записать для некоторого . Тогда т.к. G имеет порядок n. Чтобы показать, что е обладает свойством проектирования, отметим, что существуют такие , что и , и в дальнейшем это значение эффективно вычислимо (задана факторизация n) при помощи Китайской Теоремы об Остатках. Т.о. возведение в степень отменяет воздействие компонента группового элемента, в то время как оставляет компонент не тронутым. Это позволяет нам определить для и для . Эти отображения легко удовлетворяют свойства проектирования.

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

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


Преобразование в группу простого порядка

В данном разделе мы покажем, что наша схема не реализуется безопасно при общем использовании семейства k-линейных предположений для групп простого порядка. Семейство k-линейных предположений обобщает предположения о решении Диффи-Хеллмана и линейном решении [11] и определяется следующим образом:

Предположение 6.1 ([45,33]). Пусть G это алгоритм генерации выводящий кортеж (p, G, g), где p простое, G это группа порядка p, а g генератор G. Говорят, что G удовлетворяет k-линейному предположению если вычислительно неосуществим расчёт разницы между кортежами вида и кортежами вида для случайного . Говоря более общими словами, для всех PPT злоумышленников А существует пренебрежимо малая функция и параметр безопасности такие, что следующее уравнение выполняется для всех  :


Пусть G будет билинейной группой простого порядка p с парным значением . Когда мы используем понятие «изначального» k-линейного предположения, мы имеем виду, что определяем модуль В как и модуль для генерации с помощью k элементов В разница которых будет подмодулем ранга k. В действительности, единственным способом интерпретации k-линейного предположения будет неразличимость по признакам случайного элемента в подмодуле генерируемого элементами вида для i = 1,…,k при случайном элементе . Наше использование предположения обобщает эту интерпретацию только немного, путём рандомизации генераторов . Отметим, что при нашей установке частный модуль имеет -ранг 1.

Следуя умозаключениям Фримана [24, параграф 2], определим (симметрические) парные значения В заданием для целого m и выбором (k + 1)x(k + 1) (симметрических) матриц над для l=1,...,m. Затем установим l-ый компонент парного значения (5)

где обозначает (i, j)-й вход . Связь между k-Линейным предположением задаётся следующей теоремой:

Теорема 6.2 ([24, Теорема 2.5]). Пусть будут представлены так, как указано выше, с в качестве равномерного случайного подмодуля ранга-k В. Если G удовлетворяет k-линейному предположению, тогда случайный элемент будет вычислительно неразличим по признакам от случайного элемента в В.

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

Начнём с того, что покажем необходимость наличия порядка p для отображения симметрической пары в группе G простого порядка p. Если это выполняется, определим как Е(В,В) подмодуль генерируемый всеми элементами формы Е(x,y) для .

Лемма 6.3. Если G есть группа простого порядка p а есть невырожденное билинейное отображение, тогда порядок e(G,G) будет p.

Доказательство. Сперва рассмотрим экспоненту p e(G,G); для того, чтобы выявить её, заметим, что G имеет порядок p, т.о. получаем для любого . Т.к. e(G,G) имеет экспоненту p, любой элемент будет вида для и . Т.к. G циклична, то можно записать и для генератора g и уникальных . По свойству билинейности, можно записать , и т.о. e(G,G) будет циклической группой генерируемой e(g,g); из невырожденности е следует, что e(g,g) имеет порядок p.

Лемма 6.3 показывает, что заменяя на e(G,G) мы получаем с порядком p без потери общности. Мы покажем это предположение в оставшейся части данного раздела. Мы также утверждаем, что значения используемые для определения парных Е для модуля В будут независимыми подмодулями и  ; если они не независимы, то тот факт, что их можно соотнести (они открыты) с генераторами даёт злоумышленнику информацию о , которую можно использовать для взлома предположения о неразличимости по признакам. Аналогично, если парные значения зависят от , то злоумышленник может воспользоваться данной информацией для вычисления Е(x,y) и выявления, что тогда и только тогда, когда результирующее значение равно 1.

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

В общем, существует 2 метода в литературе для оперирования парными значениями групповых элементов со свойством отмены. Как видно из Раздела 5.3, отмена при составном наборе допустима в связи со следующим: это следует из того, что порядки подгрупп относительно просты. В наборе простого порядка это не является таковым, т.к. каждый компонент (например, ) имеет степень р. В связи с этим необходимо использовать линейные комбинации экспонент для того, чтобы успешно удалять элементы. Наш новый результат можно интерпретировать как выявление того, что формирование этих линейных комбинаций требуется нам для компоновки элементов в парных значениях и т.о. сокращения размеров изображения парных значений. Для упрощения определения мы рассматриваем утверждение относительно (k – 1)-линейного предположения.

Предложение 6.4. Пусть G есть билинейная группа простого порядка p с парными значениями . Пусть В есть G-модуль ранга-k, пусть для некоторых положительных целых m, и пусть будет невырожденное парное значение определённое как в (5). Если это равномерный случайный подмодуль ранга-(k – 1) В и Е это пара обладающая свойством отмены, и независима от разложения , тогда е(В,В) имеет порядок р с преобладающей вероятностью.

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

Предположим, что и  ; давайте рассмотрим что нам потребуется для того, чтобы получить Т = 1. Пусть будет набором генераторов , и запишем для u = 1, … , k – 1. Тогда основной элемент будет задаваться для переменных . Т.к. имеет ранг k – 1, подмодуль имеет ранг 1, а основной элемент задаётся для некоторых фиксированных и переменного . Рассмотрев повторно как наш элемент Т вычисляется в (5), можно увидеть, что условие Т = 1 эквивалентно

В определении матрицы это будет , где есть строковый вектор , а это матрица удовлетворяющая парным коэффициентам (определённым в (5)), это (k – 1) x k матрица, строки которой являются векторами соответствующих генераторов , и есть вектор столбец . Т.к. эти требования должны выполняться для всех значений и t, мы можем в дальнейшем уменьшить уравнение до . Теперь рассмотрим два различных случая: когда Е инвертируемо и когда Е единственно.

Сперва рассмотрим случай когда Е единственно. Свойство отмены требует, чтобы . Если , то парные значения вырождаются из этого компонента, так как и любой парный элемент с будет равен 1. Поэтому, это не может быть единственным типом элементов в парном кортеже, либо в противном случае полностью все парные значения будут вырожденными. С другой стороны, если , то т.к. можно заметить, что это ненулевой вектор с изображением Е и началом А.

Далее рассмотрим случай, когда Е инверсно, и примем во внимание не только элемент Т, но и соответствующий коэффициент матрицы Е’, с условием, что . Тогда получим , что означает, что находится и в АЕ и в АЕ’. Т.к. А имеет ранг k – 1 и мы полагаем, что Е инверсно, то размерность будет 1. Более того, т.к. Е инверсно, мы можем записать

из чего следует, что также содержаться в AE. В силу одноразмерности должен быть константой умноженной на  ; т.е. для некоторого и в качестве собственного вектора .

Теперь предположим что единично. Наше рассмотрение данного случая расписано выше и заключается в том, что если парное Е обладает свойством отмены, то должна быть некоторая матрица с . Как отмечалось выше, выбор модуля эквивалентен выбору одноразмерного подпространства ker A. Т.к. не инверсно, то получиться . Т.о. число одноразмерных подпространств в будет максимум , тогда как число одноразмерных подпространств в будет . Отметим, что вероятность того, что ker (A) имеет нетривиальную реализацию с будет максимально равна . Подытожив это, вероятность, что для некоторого l будет максимально 2m/p, что пренебрежимо мало.

Скомпоновав всё это вместе мы можем расписать нашу основную теорему:

Теорема 6.5. Пусть G это билинейная группа простого порядка p с раными значениями . Пусть В будет G-модулем ранга-k , пусть для некоторых положительных целых m, и пусть это невырожденное парное значение как в (5). Если есть равномерный случайный подмодуль В ранга-(k – 1), а Е это парное значение со свойством отмены независимого разложения , то с большой вероятностью, парное Е не будет обладать проектировочным свойством (по отношению к некоторым разложениям ).

Доказательство. По предположению 6.4, нам известно, что если Е обладает отменой, то Е(В,В) имеет порядок р с большой вероятностью. Это означает, что Е(В,В) циклична и любой её ненулевой элемент является генератором.

Положим, что Е обладает проектировочным свойством и выберем некоторый . Т.к. Е невырожденно, существует некоторые такие, что . Теперь проектировочное свойство применимо и . Т.к. Е(x,y) генерирует Е(В,В) можно выявить, что .

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

Заключения и задачи для будущего рассмотрения

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

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

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

Благодарности. Мы хотим поблагодарить Мелису Чейс за полезные советы по данной работе и анонимным рецензистам за их не менее полезные комментарии. Первый автор спонсировался частично грантом MURI утверждённым научным исследовательским центром Air Force и частично стипендией Чарльза Ли Пауэла. Третий автор спонсировался NSF исследовательского отделения Математических Наук Докторантуры.


Справочная литература

1. Abdalla, M., Namprempre, C., Neven, G.: On the (im)possibility of blind message authentication codes. In: Pointcheval, D. (ed.) CT-RSA 2006. LNCS, vol. 3860, pp. 262–279. Springer, Heidelberg (2006)

2. Abe, M., Fuchsbauer, G., Groth, J., Haralambiev, K., Ohkubo, M.: Structurepreserving signatures and commitments to group elements. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 209–236. Springer, Heidelberg (2010)

3. Abe, M., Fujisaki, E.: How to date blind signatures. In: Kim, K., Matsumoto, T. (eds.) ASIACRYPT 1996. LNCS, vol. 1163, pp. 244–251. Springer, Heidelberg (1996)

4. Abe, M., Haralambiev, K., Ohkubo, M.: Signing on elements in bilinear groups for modular protocol design. Cryptology ePrint Archive, Report 2010/133 (2010), http://eprint.iacr.org/

5. Abe, M., Ohkubo, M.: A framework for universally composable non-committing blind signatures. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 435–450. Springer, Heidelberg (2009)

6. Abe, M., Okamoto, T.: Provably secure partially blind signatures. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 271–286. Springer, Heidelberg (2000)

7. Ballard, L., Green, M., de Medeiros, B., Monrose, F.: Correlation-resistant storage via keyword-searchable encryption. Cryptology ePrint Archive, Report 2005/417, (2005), http://eprint.iacr.org/

8. Baric, N., Pfitzmann, B.: Collision-free accumulators and fail-stop signature schemes without trees. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 480–494. Springer, Heidelberg (1997)

9. Bellare, M., Namprempre, C., Pointcheval, D., Semanko, M.: The power of RSA inversion oracles and the security of Chaum’s RSA-based blind signature scheme. In: Syverson, P.F. (ed.) FC 2001. LNCS, vol. 2339, pp. 319–338. Springer, Heidelberg (2002)

10. Boldyreva, A.: Threshold signature, multisignature and blind signature schemes based on the gap-Diffie-Hellman-group signature scheme. In: Desmedt, Y. (ed.) PKC 2003. LNCS, vol. 2567, pp. 31–46. Springer, Heidelberg (2002)

11. Boneh, D., Boyen, X., Shacham, H.: Short group signatures. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 41–55. Springer, Heidelberg (2004)

12. Boneh, D., Goh, E.-J., Nissim, K.: Evaluating 2-DNF formulas on ciphertexts. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 325–341. Springer, Heidelberg (2005)

13. Boneh, D., Rubin, K., Silverberg, A.: Finding composite order ordinary elliptic curves using the Cocks-Pinch method. Cryptology ePrint Archive, Report 2009/533, (2009), http://eprint.iacr.org/2009/533 Limitations on Transformations from Composite- to Prime-Order Groups 537

14. Boudot, F.: Efficient proofs that a committed number lies in an interval. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 431–444. Springer, Heidelberg (2000)

15. Boyen, X., Waters, B.: Compact group signatures without random oracles. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 427–444. Springer, Heidelberg (2006)

16. Cao, T., Lin, D., Xue, R.: A randomized RSA-based partially blind signature scheme for electronic cash. Computers and Security 24(1), 44–49 (2005)

17. Chaum, D.: Blind signatures for untraceable payments. In: Chaum, D., Rivest, R., Sherman, A. (eds.) Proceedings of Crypto 1982, pp. 199–204. Plenum Press, New York (1983)

18. Chaum, D.: Blind signature system (abstract). In: Chaum, D. (ed.) Proceedings of Crypto 1983, p. 153. Plenum Press, New York (1984)

19. Chaum, D.: Elections with unconditionally-secret ballots and disruption equivalent to breaking RSA. In: G.unther, C. (ed.) EUROCRYPT 1988. LNCS, vol. 330, pp. 177–182. Springer, Heidelberg (1988)

20. Chaum, D., Fiat, A., Naor, M.: Untraceable electronic cash. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 319–327. Springer, Heidelberg (1990)

21. Dummit, D., Foote, R.: Abstract Algebra, 2nd edn. Prentice-Hall, Upper Saddle River (1999)

22. Fischlin, M.: Round-optimal composable blind signatures in the common reference string model. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 60–77. Springer, Heidelberg (2006)

23. Freeman, D., Scott, M., Teske, E.: A taxonomy of pairing-friendly elliptic curves. J. Cryptology 23(2), 224–280 (2010)

24. Freeman, D.M.: Converting pairing-based cryptosystems from composite-order groups to prime-order groups. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 44–61. Springer, Heidelberg (2010)

25. Fuchsbauer, G.: Automorphic signatures in bilinear groups and an application to round-optimal blind signatures. Cryptology ePrint Archive, Report 2009/320 (2009), http://eprint.iacr.org/

26. Galindo, D., Herranz, J., Kiltz, E.: On the generic construction of identity-based signatures with additional properties. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol. 4284, pp. 178–193. Springer, Heidelberg (2006)

27. Garg, S., Sahai, A., Waters, B.: Efficient fully collusion-resilient traitor tracing scheme. Cryptology ePrint Archive, Report 2009/532 (2009), http://eprint.iacr.org/2009/532

28. Green, M., Hohenberger, S.: Blind identity-based encryption and simulatable oblivious transfer. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 265–282. Springer, Heidelberg (2007)

29. Groth, J., Ostrovsky, R., Sahai, A.: Non-interactive zaps and new techniques for NIZK. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 97–111. Springer, Heidelberg (2006)

30. Groth, J., Ostrovsky, R., Sahai, A.: Perfect non-interactive zero knowledge for NP. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 339–358. Springer, Heidelberg (2006)

31. Groth, J., Sahai, A.: Efficient non-interactive proof systems for bilinear groups. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 415–432. Springer, Heidelberg (2008) 538 S. Meiklejohn, H. Shacham, and D.M. Freeman

32. Hazay, C., Katz, J., Koo, C.-Y., Lindell, Y.: Concurrently-secure blind signatures without random oracles or setup assumptions. In: Vadhan, S. (ed.) TCC 2007. LNCS, vol. 4392, pp. 323–341. Springer, Heidelberg (2007)

33. Hofheinz, D., Kiltz, E.: Secure hybrid encryption from weakened key encapsulation. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 553–571. Springer, Heidelberg (2007)

34. Juels, A., Luby, M., Ostrovsky, R.: Security of blind digital signatures. In: Kaliski Jr., B. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 150–164. Springer, Heidelberg (1997)

35. Kiayias, A., Zhou, H.-S.: Concurrent blind signatures without random oracles. In: Yung, M. (ed.) SCN 2006. LNCS, vol. 4116, pp. 49–62. Springer, Heidelberg (2006)

36. Lysyanskaya, A., Ramzan, Z.: Group blind digital signatures: A scalable solution to electronic cash. In: Hirschfeld, R. (ed.) FC 1998. LNCS, vol. 1465, pp. 184–197. Springer, Heidelberg (1998)

37. Lysyanskaya, A., Rivest, R., Sahai, A., Wolf, S.: Pseudonym systems. In: Heys, H., Adams, C. (eds.) SAC 1999. LNCS, vol. 1758, pp. 184–199. Springer, Heidelberg (2000)

38. Martinet, G., Poupard, G., Sola, P.: Cryptanalysis of a partially blind signature scheme, or How to make $100 bills with $1 and $2 ones. In: Crescenzo, G.D., Rubin, A. (eds.) FC 2006. LNCS, vol. 4107, pp. 171–176. Springer, Heidelberg (2006)

39. Meiklejohn, S., Shacham, H., Freeman, D.M.: Limitations on transformations from composite-order to prime-order groups: the case of round-optimal blind signatures. Cryptology ePrint Archive, Report 2010/474 (2010), http://eprint.iacr.org/2010/474

40. Okamoto, T.: Efficient blind and partially blind signatures without random oracles. Cryptology ePrint Archive, Report 2006/102 (2006), http://eprint.iacr.org/

41. Okamoto, T.: Efficient blind and partially blind signatures without random oracles. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 80–99. Springer, Heidelberg (2006)

42. Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238. Springer, Heidelberg (1999)

43. Paterson, K., Schuldt, J.: Efficient identity-based signatures secure in the standard model. In: Batten, L.M., Safavi-Naini, R. (eds.) ACISP 2006. LNCS, vol. 4058, pp. 207–222. Springer, Heidelberg (2006)

44. Pointcheval, D., Stern, J.: Security arguments for digital signatures and blind signatures. J. Cryptology 13(3), 361–396 (2000)

45. Shacham, H.: A Cramer-Shoup encryption scheme from the linear assumption and from progressively weaker linear variants. Cryptology ePrint Archive, Report 2007/074 (2007), http://eprint.iacr.org/

46. Waters, B.: Efficient identity-based encryption without random oracles. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 114–127. Springer, Heidelberg (2005)

47. Zhang, F., Kim, K.: ID-based blind signature and ring signature from pairings. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 533–547. Springer, Heidelberg (2002)