MulBasicIdent

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

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

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

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

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

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

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

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

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

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

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

Для расшифрования шифротекста $C=\langle U,V\rangle$ абонентом с идентификатором $ID_{i}$ с помощью закрытого ключа $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}}))=M$

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

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

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

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

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

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

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

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

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

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

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

Этап 1

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

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

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

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

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

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

Этап 2

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

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

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

Результат

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

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

Улучшение

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

Литература

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