MulBasicIdent

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

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

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

• [math]\displaystyle{ n }[/math] — число участвующих в генерации общего ключа сторон;
• [math]\displaystyle{ ID_i }[/math] — уникальное двоичное число (идентификатор) пользователя с номером [math]\displaystyle{ i }[/math];
• [math]\displaystyle{ G_1 }[/math] — аддитивная циклическая группа;
• [math]\displaystyle{ G_2 }[/math] — мультипликативная циклическая группа.

Группы [math]\displaystyle{ G_1 }[/math] и [math]\displaystyle{ G_2 }[/math] используются для дальнейшего построения мультилинейного отображения.

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

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

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

1. На основе [math]\displaystyle{ k }[/math] Центром генерации закрытых ключей (PKG) вырабатывается простой порядок [math]\displaystyle{ q }[/math] групп [math]\displaystyle{ G_1 }[/math] и [math]\displaystyle{ G_2 }[/math], [math]\displaystyle{ 2n }[/math]-мультилинейное отображение [math]\displaystyle{ \mu \colon \underbrace{G_1 \times G_1 \times \ldots \times G_1}_{2n} \to G_2 }[/math] и произвольный образующий элемент группы [math]\displaystyle{ P \in G_1 }[/math].
2. Центром PKG случайным образом выбираются элементы [math]\displaystyle{ s_1, \ldots, s_n \in \mathbb{Z}_q^* }[/math] и вычисляется набор открытых ключей [math]\displaystyle{ P_{pub_1} = s_1 P, \ldots, P_{pub_n} = s_n P }[/math].
3. Центром PKG выбираются криптографические хеш-функции [math]\displaystyle{ H_1 \colon \{0,1\}^* \to G_1^* }[/math] и [math]\displaystyle{ H_2 \colon G_2 \to \{0,1\}^l }[/math] для некоторого [math]\displaystyle{ l \in \mathbb{Z} }[/math], где [math]\displaystyle{ \{0,1\}^* }[/math] — множество двоичных векторов произвольной длины, а [math]\displaystyle{ \{0,1\}^l }[/math] — множество двоичных векторов длины [math]\displaystyle{ l }[/math].

В данном алгоритме пространства сообщений и шифротекстов представляют собой множества [math]\displaystyle{ \vartheta = \{0,1\}^l }[/math] и [math]\displaystyle{ C = G_1^* \times \{0,1\}^l }[/math] соответственно, элементы [math]\displaystyle{ s_1, \ldots, s_n \in \mathbb{Z}_q^* }[/math] являются мастер-ключами абонентов, а системными параметрами является набор [math]\displaystyle{ \langle G_1, G_2, \mu, l, P, P_{pub_1}, \ldots, P_{pub_n}, H_1, H_2 \rangle }[/math].

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

Для идентификаторов абонентов [math]\displaystyle{ ID_1, \ldots, ID_n \in \{0,1\}^* }[/math]:

1. Центр вычисляет [math]\displaystyle{ Q_{ID_1} = H_1(ID_1) \in G_1^*, \ldots, Q_{ID_n} = H_1(ID_n) \in G_1^* }[/math].
2. Центр вычисляет закрытые ключи [math]\displaystyle{ d_{ID_1} = s_1Q_{ID_1}, \ldots, d_{ID_n} = s_nQ_{ID_n} }[/math], где [math]\displaystyle{ s_1, \ldots, s_n }[/math] — мастер-ключи.

Шифрование

Для шифрования сообщения [math]\displaystyle{ M }[/math] с помощью идентификаторов [math]\displaystyle{ ID_1, \ldots, ID_n \in \{0,1\}^*: }[/math] абонент выполняет следующие операции:

1. Вычисляет [math]\displaystyle{ Q_{ID_1} = H_1(ID_1) \in G_1^*, \ldots, Q_{ID_n} = H_1(ID_n) \in G_1^* }[/math].
2. Выбирает случайный элемент [math]\displaystyle{ r \in \mathbb{Z}_q^* }[/math].
3. Вычисляет шифротекст [math]\displaystyle{ C = \langle rP, M \oplus H_2(g^r) \rangle }[/math], где [math]\displaystyle{ g = \mu (Q_{ID_1}, \ldots, Q_{ID_n}, P_{pub_1}, \ldots, P_{pub_n}) \in G_2^* }[/math].

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

Для расшифрования шифротекста [math]\displaystyle{ C = \langle U, V \rangle }[/math] абонентом с идентификатором [math]\displaystyle{ ID_i }[/math] с помощью закрытого ключа [math]\displaystyle{ d_{ID_i} \in G_1^* }[/math] вычисляется открытый текст следующим образом:

[math]\displaystyle{ 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 }[/math]

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

Корректность алгоритма подтверждается выполнением следующего равенства, смысл которого сводится к подстановке в аргумент функции [math]\displaystyle{ H_2 }[/math] на этапе расшифрования выражений для закрытого ключа [math]\displaystyle{ d_{ID_i} = s_iQ_{ID_i} }[/math] и элемента [math]\displaystyle{ U = rP }[/math]:

[math]\displaystyle{ \begin{align} \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_ir} \\ = \mu(Q_{ID_1}, \ldots, Q_{ID_n}, P_{pub_1}, \ldots, P_{pub_n})^{r} = g^r \\ \end{align} }[/math]

Так как [math]\displaystyle{ V = M \oplus H_2(g^r) }[/math], то на этапе расшифрования получаем [math]\displaystyle{ M \oplus H_2(g^r) \oplus H_2(g^r) = M }[/math].

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

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

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

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

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

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

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

Этап 1

Атакующий алгоритм генерирует запросы [math]\displaystyle{ q_1, \ldots, q_m }[/math] и отправляет их запросчику, где [math]\displaystyle{ q_i }[/math] является:

1. Запросом закрытого ключа [math]\displaystyle{ \langle ID_i'\rangle }[/math]. В данном случае запросчик запускает процедуру генерации закрытого ключа [math]\displaystyle{ d_i' \in G_1 }[/math], соответствующего открытому ключу [math]\displaystyle{ \langle ID_i'\rangle }[/math], и передает [math]\displaystyle{ d_i' \in G_1 }[/math] атакующему алгоритму.
2. Запросом расшифрования [math]\displaystyle{ \langle ID_i', C_i'\rangle }[/math]. В данном случае запросчик запускает процедуру генерации закрытого ключа [math]\displaystyle{ d_i' \in G_1 }[/math], соответствующего открытому ключу [math]\displaystyle{ \langle ID_i'\rangle }[/math]. Далее запускает процедуру расшифрования шифротекста [math]\displaystyle{ C_i' }[/math] с помощью [math]\displaystyle{ d_i' }[/math] и передает полученный открытый текст атакующему алгоритму.

Данные запросы проводятся адаптивно, то есть каждый запрос [math]\displaystyle{ q_i }[/math] может зависеть от ответов на запросы [math]\displaystyle{ q_1, \ldots, q_{i-1} }[/math].

После завершения этапа 1 атакующий алгоритм генерирует 2 открытых текста [math]\displaystyle{ M_0, M_1 \in \vartheta }[/math] равной длины и набор идентификаторов абонентов [math]\displaystyle{ ID_1, \ldots, ID_n }[/math], для которых он проводит атаку, где [math]\displaystyle{ \vartheta }[/math] — множество открытых текстов произвольной длины. Единственным ограничением является тот факт, что [math]\displaystyle{ ID_i \neq ID_j' }[/math] при [math]\displaystyle{ i=1, \ldots, n, j=1, \ldots, m }[/math] во время этапа 1.

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

Запросчик случайно выбирает бит [math]\displaystyle{ b \in \{0,1\} }[/math] и отправляет [math]\displaystyle{ C_b=Encrypt(params, ID_1, \ldots, ID_n, M_b) }[/math] алгоритму.

Этап 2

Атакующий алгоритм генерирует и отправляет запросчику дополнительные запросы [math]\displaystyle{ q_{m+1}, \ldots, q_l }[/math], где [math]\displaystyle{ q_i }[/math] является:

1. Запросом закрытого ключа [math]\displaystyle{ \langle ID_j'\rangle }[/math], где [math]\displaystyle{ ID_i \neq ID_j' }[/math] для [math]\displaystyle{ i=1, \ldots, n, j=m+1, \ldots, l }[/math]. Запросчик отвечает так же, как и во время этапа 1.
2. Запросом расшифрования [math]\displaystyle{ \langle ID_j',C_j'\rangle }[/math], где [math]\displaystyle{ \langle ID_j',C_j'\rangle \neq \langle ID_i',C_i'\rangle }[/math] для [math]\displaystyle{ i=1, \ldots, n, j=m+1, \ldots, l }[/math]. Запросчик отвечает так же, как и во время этапа 1.

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

Результат

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

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

Улучшение

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

Литература

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