MulBasicIdent (MulBasicIdent)

MulBasicIdent — базовый мультилинейный алгоритм шифрования на основе идентификационных данных^[1]. Данный алгоритм является обобщением метода выработки общего ключа с помощью билинейных спариваний (BasicIdent), предложенного Дэном Боне и Мэтью К. Франклином в 2001 году^[2].

Параметры протокола

В протоколе используются следующие параметры и группы:

$n$ — число участвующих в генерации общего ключа сторон;
$ID_{i}$ — уникальное двоичное число (идентификатор) пользователя с номером $i$ ;
$G_{1}$ — аддитивная циклическая группа;
$G_{2}$ — мультипликативная циклическая группа.

Группы $G_{1}$ и $G_{2}$ используются для дальнейшего построения мультилинейного отображения.

Описание алгоритма

Данный алгоритм решает задачу шифрования сообщения для $n$ абонентов с идентификаторами $ID_{1},\ldots ,ID_{n}$ ^[1]. Протокол состоит из этапов инициализации, получения закрытого ключа, шифрования и расшифрования. Пусть $k\in \mathbb {Z}$ — принимаемый алгоритмом на этапе инициализации параметр стойкости.

Инициализация

На основе $k$ Центром генерации закрытых ключей (PKG) вырабатывается простой порядок $q$ групп $G_{1}$ и $G_{2}$ , $2n$ -мультилинейное отображение $\mu \colon \underbrace {G_{1}\times G_{1}\times \ldots \times G_{1}} _{2n}\to G_{2}$ и произвольный образующий элемент группы $P\in G_{1}$ .
Центром PKG случайным образом выбираются элементы $s_{1},\ldots ,s_{n}\in \mathbb {Z} _{q}^{*}$ и вычисляется набор открытых ключей $P_{pub_{1}}=s_{1}P,\ldots ,P_{pub_{n}}=s_{n}P$ .
Центром PKG выбираются криптографические хеш-функции $H_{1}\colon \{0,1\}^{*}\to G_{1}^{*}$ и $H_{2}\colon G_{2}\to \{0,1\}^{l}$ для некоторого $l\in \mathbb {Z}$ , где $\{0,1\}^{*}$ — множество двоичных векторов произвольной длины, а $\{0,1\}^{l}$ — множество двоичных векторов длины $l$ .

В данном алгоритме пространства сообщений и шифротекстов представляют собой множества $\vartheta =\{0,1\}^{l}$ и $C=G_{1}^{*}\times \{0,1\}^{l}$ соответственно, элементы $s_{1},\ldots ,s_{n}\in \mathbb {Z} _{q}^{*}$ являются мастер-ключами абонентов, а системными параметрами является набор $\langle G_{1},G_{2},\mu ,l,P,P_{pub_{1}},\ldots ,P_{pub_{n}},H_{1},H_{2}\rangle$ .

Получение закрытого ключа

Для идентификаторов абонентов $ID_{1},\ldots ,ID_{n}\in \{0,1\}^{*}$ :

Центр вычисляет $Q_{ID_{1}}=H_{1}(ID_{1})\in G_{1}^{*},\ldots ,Q_{ID_{n}}=H_{1}(ID_{n})\in G_{1}^{*}$ .
Центр вычисляет закрытые ключи $d_{ID_{1}}=s_{1}Q_{ID_{1}},\ldots ,d_{ID_{n}}=s_{n}Q_{ID_{n}}$ , где $s_{1},\ldots ,s_{n}$ — мастер-ключи.

Шифрование

Для шифрования сообщения $M$ с помощью идентификаторов $ID_{1},\ldots ,ID_{n}\in \{0,1\}^{*}:$ абонент выполняет следующие операции:

Вычисляет $Q_{ID_{1}}=H_{1}(ID_{1})\in G_{1}^{*},\ldots ,Q_{ID_{n}}=H_{1}(ID_{n})\in G_{1}^{*}$ .
Выбирает случайный элемент $r\in \mathbb {Z} _{q}^{*}$ .
Вычисляет шифротекст $C=\langle rP,M\oplus H_{2}(g^{r})\rangle$ , где $g=\mu (Q_{ID_{1}},\ldots ,Q_{ID_{n}},P_{pub_{1}},\ldots ,P_{pub_{n}})\in G_{2}^{*}$ .

Расшифрование

Для расшифрования шифротекста $C=\langle U,V\rangle$ абонентом с идентификатором $ID_{i}$ с помощью закрытого ключа $d_{ID_{i}}\in G_{1}^{*}$ вычисляется открытый текст следующим образом:

V\oplus H_{2}(\mu (Q_{ID_{1}},\ldots ,Q_{ID_{i-1}},d_{ID_{i}},Q_{ID_{i+1}},\ldots ,Q_{ID_{n}},P_{pub_{1}},\ldots ,P_{pub_{i-1}},U,P_{pub_{i+1}},\ldots ,P_{pub_{n}}))=M

Корректность схемы

Корректность алгоритма подтверждается выполнением следующего равенства, смысл которого сводится к подстановке в аргумент функции $H_{2}$ на этапе расшифрования выражений для закрытого ключа $d_{ID_{i}}=s_{i}Q_{ID_{i}}$ и элемента $U=rP$ :

{\begin{aligned}\mu (Q_{ID_{1}},\ldots ,Q_{ID_{i-1}},d_{ID_{i}},Q_{ID_{i+1}},\ldots ,Q_{ID_{n}},P_{pub_{1}},\ldots ,P_{pub_{i-1}},U,P_{pub_{i+1}},\ldots ,P_{pub_{n}})\\=\mu (Q_{ID_{1}},\ldots ,Q_{ID_{n}},P_{pub_{1}},\ldots ,P,\ldots ,P_{pub_{n}})^{s_{i}r}\\=\mu (Q_{ID_{1}},\ldots ,Q_{ID_{n}},P_{pub_{1}},\ldots ,P_{pub_{n}})^{r}=g^{r}\\\end{aligned}}

Так как $V=M\oplus H_{2}(g^{r})$ , то на этапе расшифрования получаем $M\oplus H_{2}(g^{r})\oplus H_{2}(g^{r})=M$ .

Криптографическая стойкость

Протокол является стойким при адаптивной атаке с выбором открытого текста и в предположении сложности мультилинейной проблемы Диффи-Хеллмана (MDH)^[1].

Описание атаки на протокол

Модели безопасности широковещательного шифрования основаны на играх, проводимых злоумышленником (атакующим алгоритмом) с запросчиком (challenger).

Игра злоумышленника, проводящего атаку на алгоритм широковещательного шифрования, состоит из процедуры инициализации, 2-х этапов проведения запросов, постановки задачи и вывода результата.

Инициализация

Запросчик принимает параметр стойкости $k\in \mathbb {N}$ , запускает процедуру инициализации алгоритма, передает атакующему алгоритму параметры $params$ и сохраняет мастер-ключи $master-keys$ в секрете. Определены $G_{1}$ — аддитивная циклическая группа простого порядка $q$ с образующим элементом $P$ , и $G_{2}$ — мультипликативная циклическая группа простого порядка $q$ .

Этап 1

Атакующий алгоритм генерирует запросы $q_{1},\ldots ,q_{m}$ и отправляет их запросчику, где $q_{i}$ является:

Запросом закрытого ключа $\langle ID_{i}'\rangle$ . В данном случае запросчик запускает процедуру генерации закрытого ключа $d_{i}'\in G_{1}$ , соответствующего открытому ключу $\langle ID_{i}'\rangle$ , и передает $d_{i}'\in G_{1}$ атакующему алгоритму.
Запросом расшифрования $\langle ID_{i}',C_{i}'\rangle$ . В данном случае запросчик запускает процедуру генерации закрытого ключа $d_{i}'\in G_{1}$ , соответствующего открытому ключу $\langle ID_{i}'\rangle$ . Далее запускает процедуру расшифрования шифротекста $C_{i}'$ с помощью $d_{i}'$ и передает полученный открытый текст атакующему алгоритму.

Данные запросы проводятся адаптивно, то есть каждый запрос $q_{i}$ может зависеть от ответов на запросы $q_{1},\ldots ,q_{i-1}$ .

После завершения этапа 1 атакующий алгоритм генерирует 2 открытых текста $M_{0},M_{1}\in \vartheta$ равной длины и набор идентификаторов абонентов $ID_{1},\ldots ,ID_{n}$ , для которых он проводит атаку, где $\vartheta$ — множество открытых текстов произвольной длины. Единственным ограничением является тот факт, что $ID_{i}\neq ID_{j}'$ при $i=1,\ldots ,n,j=1,\ldots ,m$ во время этапа 1.

Постановка задачи

Запросчик случайно выбирает бит $b\in \{0,1\}$ и отправляет $C_{b}=Encrypt(params,ID_{1},\ldots ,ID_{n},M_{b})$ алгоритму.

Этап 2

Атакующий алгоритм генерирует и отправляет запросчику дополнительные запросы $q_{m+1},\ldots ,q_{l}$ , где $q_{i}$ является:

Запросом закрытого ключа $\langle ID_{j}'\rangle$ , где $ID_{i}\neq ID_{j}'$ для $i=1,\ldots ,n,j=m+1,\ldots ,l$ . Запросчик отвечает так же, как и во время этапа 1.
Запросом расшифрования $\langle ID_{j}',C_{j}'\rangle$ , где $\langle ID_{j}',C_{j}'\rangle \neq \langle ID_{i}',C_{i}'\rangle$ для $i=1,\ldots ,n,j=m+1,\ldots ,l$ . Запросчик отвечает так же, как и во время этапа 1.

Данные запросы могут проводиться адаптивно, как и во время этапа 1.

Результат

Атакующий алгоритм возвращает бит $b'\in \{0,1\}$ и выигрывает игру, если $b=b'$ .

Выигрышем при проведении атаки злоумышленника $A$ на алгоритм $E$ называется следующая функция параметра стойкости $k\in \mathbb {N}$ : $Adv_{E,A}(k)=\left|Pr[b=b']-{\frac {1}{2}}\right|$ , где $Pr[b=b']$ — вероятность события, состоящего в совпадении значений битов $b$ и $b'$ .

Улучшение

На основе алгоритма MulBasicIdent с помощью метода Фуджисаки-Окамото построен полный алгоритм широковещательного шифрования на основе идентификационных данных MulFullIdent.

Примечания

↑ ¹ ² ³ Косолапов Д. О. Построение многосторонних мультилинейных алгоритмов в условиях различных моделей безопасности : Дисс.. канд. физ.-мат. наук. — М., 2010.
↑ Boneh D. and Franklin M. Identity-based encryption from the Weil Pairing, Crypto'2001 // Springer-Verlag : Lecture Notes in Computer Science. — 2001.

Литература

Косолапов Д. О. Построение многосторонних мультилинейных алгоритмов в условиях различных моделей безопасности. — 2010.
Косолапов Д. О., Харин Е. А., Гончаров С. М., Корнюшин П. Н. Мультилинейные криптосистемы в асимметричной криптографии (рус.) : статья в журнале - научная статья. — Томск: Томский государственный университет систем управления и радиоэлектроники, 2008. — № 2—1 (18). — С. 51—53. — ISSN 1818-0442.

[diss-1] ¹ ² ³ Косолапов Д. О. Построение многосторонних мультилинейных алгоритмов в условиях различных моделей безопасности : Дисс.. канд. физ.-мат. наук. — М., 2010.

[2] Boneh D. and Franklin M. Identity-based encryption from the Weil Pairing, Crypto'2001 // Springer-Verlag : Lecture Notes in Computer Science. — 2001.

[1]

[2]