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

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

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

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

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

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

В данном алгоритме пространства сообщений и шифротекстов представляют собой множества ${\displaystyle \vartheta =\{0,1\}^{l}}$ и ${\displaystyle C=G_{1}^{*}\times \{0,1\}^{l}\times \{0,1\}^{l}}$ соответственно, элементы ${\displaystyle s_{1},\ldots ,s_{n}\in \mathbb {Z} _{q}^{*}}$ являются мастер-ключами абонентов, а системными параметрами является набор ${\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 }$.

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

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

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

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

1. Если ${\displaystyle U\notin G_{1}^{*}}$, то шифротекст не принимается. В противном случае, с помощью закрытого ключа ${\displaystyle d_{ID_{i}}\in G_{1}^{*}}$ вычисляется

${\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 .}$

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

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

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

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