MulFullIdent

MulFullIdent — полный мультилинейный алгоритм шифрования на основе идентификационных данных. Протокол построен на основе метода Фуджисаки-Окамото, предложенного в 1999 году. Алгоритм является улучшением протокола MulBasicIdent.

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

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

• [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{ 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 \in G_1 }[/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{ H_3:\{0,1\}^l\times\{0,1\}^l\to\mathbb{Z}_q^* }[/math] и [math]\displaystyle{ H_4:\{0,1\}^l\to\{0,1\}^l }[/math].

В данном алгоритме пространства сообщений и шифротекстов представляют собой множества [math]\displaystyle{ \vartheta = \{0,1\}^l }[/math] и [math]\displaystyle{ C = G_1^* \times \{0,1\}^l \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, H_3, H_4 \rangle }[/math].

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

1. Для идентификаторов абонентов [math]\displaystyle{ ID_1, \ldots, ID_n \in \{0,1\}^* }[/math] Центр PKG вычисляет [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. Центр PKG вычисляет и передает абонентам по защищенному каналу закрытые ключи [math]\displaystyle{ d_{ID_1} = s_1Q_{ID_1}, \ldots, d_{ID_n} = s_nQ_{ID_n} }[/math], [math]\displaystyle{ d_{ID_i} \in G_1 }[/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{ \sigma \in \{0,1\}^l, l \in \mathbb{Z} }[/math].
3. Вычисляет [math]\displaystyle{ r = H_3(\sigma, M), r \in \mathbb{Z}_q^* }[/math].
4. Вычисляет шифротекст [math]\displaystyle{ C = \langle rP, \sigma \oplus H_2(g^r), M \oplus H_4(\sigma) \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, W \rangle }[/math] абонентом с идентификатором [math]\displaystyle{ ID_i }[/math] с помощью закрытого ключа [math]\displaystyle{ d_{ID_i} \in G_1^* }[/math] выполняются следующие процедуры.

1. Если [math]\displaystyle{ U\notin G_1^* }[/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})) = \sigma. }[/math]

1. Абонентом вычисляется [math]\displaystyle{ W \oplus H_4(\sigma) = M }[/math].
2. Абонентом вычисляется [math]\displaystyle{ r = H_3(\sigma, M), r \in \mathbb{Z}_q^* }[/math] и проверяется [math]\displaystyle{ U=rP }[/math].

Если равенство не выполняется, то шифротекст не принимается, противном случае полагается, что [math]\displaystyle{ M }[/math] — открытый текст.

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

Литература

• Косолапов Д. О. Построение многосторонних мультилинейных алгоритмов в условиях различных моделей безопасности. — 2010.