MulBasicIdent

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

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

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

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

Группы $G_1$ и $G_2$ используются для дальнейшего построения мультилинейного отображения.

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

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

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

1. На основе $k$ Центром генерации закрытых ключей (PKG) вырабатывается простой порядок $q$ групп $G_1$ и $G_2$, $2n$-мультилинейное отображение $\mu :\underset{2n}{\underbrace{G_1\times G_1\times \dots \times G_1}}\to G_2$ и произвольный образующий элемент группы $P\in G_1$.
2. Центром PKG случайным образом выбираются элементы $s_1,\dots ,s_n\in {\mathbb{Z}}_q^{\ast }$ и вычисляется набор открытых ключей $P_{pu{b}_1}=s_{1}P,\dots ,P_{pu{b}_n}=s_{n}P$.
3. Центром PKG выбираются криптографические хеш-функции $H_1:\{0,1{\}}^{\ast }\to G_1^{\ast }$ и $H_2:G_2\to \{0,1{\}}^l$ для некоторого $l\in \mathbb{Z}$, где $\{0,1{\}}^{\ast }$ — множество двоичных векторов произвольной длины, а $\{0,1{\}}^l$ — множество двоичных векторов длины $l$.

В данном алгоритме пространства сообщений и шифротекстов представляют собой множества $\vartheta =\{0,1{\}}^l$ и $C=G_1^{\ast }\times \{0,1{\}}^l$ соответственно, элементы $s_1,\dots ,s_n\in {\mathbb{Z}}_q^{\ast }$ являются мастер-ключами абонентов, а системными параметрами является набор $⟨G_1,G_2,\mu ,l,P,P_{pu{b}_1},\dots ,P_{pu{b}_n},H_1,H_2⟩$.

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

Для идентификаторов абонентов $I{D}_1,\dots ,I{D}_n\in \{0,1{\}}^{\ast }$:

1. Центр вычисляет $Q_{I{D}_1}=H_1(I{D}_1)\in G_1^{\ast },\dots ,Q_{I{D}_n}=H_1(I{D}_n)\in G_1^{\ast }$.
2. Центр вычисляет закрытые ключи $d_{I{D}_1}=s_1{Q}_{I{D}_1},\dots ,d_{I{D}_n}=s_n{Q}_{I{D}_n}$, где $s_1,\dots ,s_n$ — мастер-ключи.

Шифрование

Для шифрования сообщения $M$ с помощью идентификаторов $I{D}_1,\dots ,I{D}_n\in \{0,1{\}}^{\ast }:$ абонент выполняет следующие операции:

1. Вычисляет $Q_{I{D}_1}=H_1(I{D}_1)\in G_1^{\ast },\dots ,Q_{I{D}_n}=H_1(I{D}_n)\in G_1^{\ast }$.
2. Выбирает случайный элемент $r\in {\mathbb{Z}}_q^{\ast }$.
3. Вычисляет шифротекст $C=⟨rP,M\oplus H_2(g^r)⟩$, где $g=\mu (Q_{I{D}_1},\dots ,Q_{I{D}_n},P_{pu{b}_1},\dots ,P_{pu{b}_n})\in G_2^{\ast }$.

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

Для расшифрования шифротекста $C=⟨U,V⟩$ абонентом с идентификатором $I{D}_i$ с помощью закрытого ключа $d_{I{D}_i}\in G_1^{\ast }$ вычисляется открытый текст следующим образом:

$V\oplus H_2(\mu (Q_{I{D}_1},\dots ,Q_{I{D}_{i-1}},d_{I{D}_i},Q_{I{D}_{i+1}},\dots ,Q_{I{D}_n},P_{pu{b}_1},\dots ,P_{pu{b}_{i-1}},U,P_{pu{b}_{i+1}},\dots ,P_{pu{b}_n}))=M$

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

Корректность алгоритма подтверждается выполнением следующего равенства, смысл которого сводится к подстановке в аргумент функции $H_2$ на этапе расшифрования выражений для закрытого ключа $d_{I{D}_i}=s_i{Q}_{I{D}_i}$ и элемента $U=rP$:

$\begin{array}{c}\mu (Q_{I{D}_1},\dots ,Q_{I{D}_{i-1}},d_{I{D}_i},Q_{I{D}_{i+1}},\dots ,Q_{I{D}_n},P_{pu{b}_1},\dots ,P_{pu{b}_{i-1}},U,P_{pu{b}_{i+1}},\dots ,P_{pu{b}_n})\\ =\mu (Q_{I{D}_1},\dots ,Q_{I{D}_n},P_{pu{b}_1},\dots ,P,\dots ,P_{pu{b}_n}{)}^{s_{i}r}\\ =\mu (Q_{I{D}_1},\dots ,Q_{I{D}_n},P_{pu{b}_1},\dots ,P_{pu{b}_n}{)}^r=g^r\\ \end{array}$

Так как $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,\dots ,q_m$ и отправляет их запросчику, где $q_i$ является:

1. Запросом закрытого ключа $⟨I{D_i}^{\prime }⟩$. В данном случае запросчик запускает процедуру генерации закрытого ключа ${d_i}^{\prime }\in G_1$, соответствующего открытому ключу $⟨I{D_i}^{\prime }⟩$, и передает ${d_i}^{\prime }\in G_1$ атакующему алгоритму.
2. Запросом расшифрования $⟨I{D_i}^{\prime },{C_i}^{\prime }⟩$. В данном случае запросчик запускает процедуру генерации закрытого ключа ${d_i}^{\prime }\in G_1$, соответствующего открытому ключу $⟨I{D_i}^{\prime }⟩$. Далее запускает процедуру расшифрования шифротекста ${C_i}^{\prime }$ с помощью ${d_i}^{\prime }$ и передает полученный открытый текст атакующему алгоритму.

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

После завершения этапа 1 атакующий алгоритм генерирует 2 открытых текста $M_0,M_1\in \vartheta$ равной длины и набор идентификаторов абонентов $I{D}_1,\dots ,I{D}_n$, для которых он проводит атаку, где $\vartheta$ — множество открытых текстов произвольной длины. Единственным ограничением является тот факт, что $I{D}_i\ne I{D_j}^{\prime }$ при $i=1,\dots ,n,j=1,\dots ,m$ во время этапа 1.

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

Запросчик случайно выбирает бит $b\in \{0,1\}$ и отправляет $C_b=Encrypt(params,I{D}_1,\dots ,I{D}_n,M_b)$ алгоритму.

Этап 2

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

1. Запросом закрытого ключа $⟨I{D_j}^{\prime }⟩$, где $I{D}_i\ne I{D_j}^{\prime }$ для $i=1,\dots ,n,j=m+1,\dots ,l$. Запросчик отвечает так же, как и во время этапа 1.
2. Запросом расшифрования $⟨I{D_j}^{\prime },{C_j}^{\prime }⟩$, где $⟨I{D_j}^{\prime },{C_j}^{\prime }⟩\ne ⟨I{D_i}^{\prime },{C_i}^{\prime }⟩$ для $i=1,\dots ,n,j=m+1,\dots ,l$. Запросчик отвечает так же, как и во время этапа 1.

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

Результат

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

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

Улучшение

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

Литература

• Шаблон:Статья
• Шаблон:Статья