MulBasicIdent

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

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

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

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

Данный алгоритм решает задачу шифрования сообщения для ${\displaystyle n}$ абонентов с идентификаторами ${\displaystyle ID_{1},\ldots ,ID_{n}}$.^[1] Протокол состоит из этапов инициализации, получения закрытого ключа, шифрования и расшифрования. Пусть ${\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}$.
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 \{0,1\}^{*}}$ — множество двоичных векторов произвольной длины, а ${\displaystyle \{0,1\}^{l}}$ — множество двоичных векторов длины ${\displaystyle l}$.

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

Для идентификаторов абонентов ${\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 d_{ID_{1}}=s_{1}Q_{ID_{1}},\ldots ,d_{ID_{n}}=s_{n}Q_{ID_{n}}}$, где ${\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 r\in \mathbb {Z} _{q}^{*}}$.
3. Вычисляет шифротекст ${\displaystyle C=\langle rP,M\oplus H_{2}(g^{r})\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\rangle }$ абонентом с идентификатором ${\displaystyle ID_{i}}$ с помощью закрытого ключа ${\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}}))=M}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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