MulFullIdent (MulFullIdent)

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

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

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

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

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

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

Протокол представлен этапами инициализации, получения закрытого ключа, шифрования и расшифрования. Пусть $k\in \mathbb {Z}$ — принимаемый алгоритмом на этапе инициализации параметр стойкости.

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

1. На основе $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}$.
2. Центром PKG случайным образом выбираются элементы $s_{1},\ldots ,s_{n}\in \mathbb {Z} _{q}^{*}$ и вычисляется набор открытых ключей $P_{pub_{1}}=s_{1}P,\ldots ,P_{pub_{n}}=s_{n}P\in G_{1}$.
3. Центром PKG выбираются криптографические хеш-функции $H_{1}\colon \{0,1\}^{*}\to G_{1}^{*}$ и $H_{2}\colon G_{2}\to \{0,1\}^{l}$ для некоторого $l\in \mathbb {Z}$, $H_{3}:\{0,1\}^{l}\times \{0,1\}^{l}\to \mathbb {Z} _{q}^{*}$ и $H_{4}:\{0,1\}^{l}\to \{0,1\}^{l}$.

В данном алгоритме пространства сообщений и шифротекстов представляют собой множества $\vartheta =\{0,1\}^{l}$ и $C=G_{1}^{*}\times \{0,1\}^{l}\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},H_{3},H_{4}\rangle$.

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

1. Для идентификаторов абонентов $ID_{1},\ldots ,ID_{n}\in \{0,1\}^{*}$ Центр PKG вычисляет $Q_{ID_{1}}=H_{1}(ID_{1})\in G_{1}^{*},\ldots ,Q_{ID_{n}}=H_{1}(ID_{n})\in G_{1}^{*}$.
2. Центр PKG вычисляет и передает абонентам по защищенному каналу закрытые ключи $d_{ID_{1}}=s_{1}Q_{ID_{1}},\ldots ,d_{ID_{n}}=s_{n}Q_{ID_{n}}$, $d_{ID_{i}}\in G_{1}$, где $s_{1},\ldots ,s_{n}$ — мастер-ключи.

Шифрование

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

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

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

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

1. Если $U\notin G_{1}^{*}$, то шифротекст не принимается. В противном случае, с помощью закрытого ключа $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}}))=\sigma .$

1. Абонентом вычисляется $W\oplus H_{4}(\sigma )=M$.
2. Абонентом вычисляется $r=H_{3}(\sigma ,M),r\in \mathbb {Z} _{q}^{*}$ и проверяется $U=rP$.

Если равенство не выполняется, то шифротекст не принимается, противном случае полагается, что $M$ — открытый текст.

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

Литература

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