Русская Википедия:MulBasicIdent
MulBasicIdent — базовый мультилинейный алгоритм шифрования на основе идентификационных данных.[1] Данный алгоритм является обобщением метода выработки общего ключа с помощью билинейных спариваний (BasicIdent), предложенного Дэном Боне и Мэтью К. Франклином в 2001 году.[2]
Параметры протокола
В протоколе используются следующие параметры и группы:
- <math>n</math> — число участвующих в генерации общего ключа сторон;
- <math>ID_i</math> — уникальное двоичное число (идентификатор) пользователя с номером <math>i</math>;
- <math>G_1</math> — аддитивная циклическая группа;
- <math>G_2</math> — мультипликативная циклическая группа.
Группы <math>G_1</math> и <math>G_2</math> используются для дальнейшего построения мультилинейного отображения.
Описание алгоритма
Данный алгоритм решает задачу шифрования сообщения для <math>n</math> абонентов с идентификаторами <math>ID_1, \ldots, ID_n</math>.[1] Протокол состоит из этапов инициализации, получения закрытого ключа, шифрования и расшифрования. Пусть <math>k \in \mathbb{Z}</math> — принимаемый алгоритмом на этапе инициализации параметр стойкости.
Инициализация
- На основе <math>k</math> Центром генерации закрытых ключей (PKG) вырабатывается простой порядок <math>q</math> групп <math>G_1</math> и <math>G_2</math>, <math>2n</math>-мультилинейное отображение <math>\mu \colon \underbrace{G_1 \times G_1 \times \ldots \times G_1}_{2n} \to G_2</math> и произвольный образующий элемент группы <math>P \in G_1</math>.
- Центром PKG случайным образом выбираются элементы <math>s_1, \ldots, s_n \in \mathbb{Z}_q^*</math> и вычисляется набор открытых ключей <math>P_{pub_1} = s_1 P, \ldots, P_{pub_n} = s_n P</math>.
- Центром PKG выбираются криптографические хеш-функции <math>H_1 \colon \{0,1\}^* \to G_1^*</math> и <math>H_2 \colon G_2 \to \{0,1\}^l</math> для некоторого <math>l \in \mathbb{Z}</math>, где <math>\{0,1\}^*</math> — множество двоичных векторов произвольной длины, а <math>\{0,1\}^l</math> — множество двоичных векторов длины <math>l</math>.
В данном алгоритме пространства сообщений и шифротекстов представляют собой множества <math>\vartheta = \{0,1\}^l</math> и <math>C = G_1^* \times \{0,1\}^l</math> соответственно, элементы <math>s_1, \ldots, s_n \in \mathbb{Z}_q^*</math> являются мастер-ключами абонентов, а системными параметрами является набор <math>\langle G_1, G_2, \mu, l, P, P_{pub_1}, \ldots, P_{pub_n}, H_1, H_2 \rangle</math>.
Получение закрытого ключа
Для идентификаторов абонентов <math>ID_1, \ldots, ID_n \in \{0,1\}^*</math>:
- Центр вычисляет <math>Q_{ID_1} = H_1(ID_1) \in G_1^*, \ldots, Q_{ID_n} = H_1(ID_n) \in G_1^*</math>.
- Центр вычисляет закрытые ключи <math>d_{ID_1} = s_1Q_{ID_1}, \ldots, d_{ID_n} = s_nQ_{ID_n} </math>, где <math>s_1, \ldots, s_n</math> — мастер-ключи.
Шифрование
Для шифрования сообщения <math>M</math> с помощью идентификаторов <math>ID_1, \ldots, ID_n \in \{0,1\}^*:</math> абонент выполняет следующие операции:
- Вычисляет <math>Q_{ID_1} = H_1(ID_1) \in G_1^*, \ldots, Q_{ID_n} = H_1(ID_n) \in G_1^*</math>.
- Выбирает случайный элемент <math>r \in \mathbb{Z}_q^*</math>.
- Вычисляет шифротекст <math>C = \langle rP, M \oplus H_2(g^r) \rangle</math>, где <math>g = \mu (Q_{ID_1}, \ldots, Q_{ID_n}, P_{pub_1}, \ldots, P_{pub_n}) \in G_2^*</math>.
Расшифрование
Для расшифрования шифротекста <math>C = \langle U, V \rangle</math> абонентом с идентификатором <math>ID_i</math> с помощью закрытого ключа <math>d_{ID_i} \in G_1^*</math> вычисляется открытый текст следующим образом:
- <math>
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 </math>
Корректность схемы
Корректность алгоритма подтверждается выполнением следующего равенства, смысл которого сводится к подстановке в аргумент функции <math>H_2</math> на этапе расшифрования выражений для закрытого ключа <math>d_{ID_i} = s_iQ_{ID_i}</math> и элемента <math>U = rP</math>:
- <math>
\begin{align} \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_ir} \\ = \mu(Q_{ID_1}, \ldots, Q_{ID_n}, P_{pub_1}, \ldots, P_{pub_n})^{r} = g^r \\ \end{align} </math>
Так как <math>V = M \oplus H_2(g^r)</math>, то на этапе расшифрования получаем <math>M \oplus H_2(g^r) \oplus H_2(g^r) = M</math>.
Криптографическая стойкость
Протокол является стойким при адаптивной атаке с выбором открытого текста и в предположении сложности мультилинейной проблемы Диффи-Хеллмана (MDH).[1]
Описание атаки на протокол
Модели безопасности широковещательного шифрования основаны на играх, проводимых злоумышленником (атакующим алгоритмом) с запросчиком (challenger).
Игра злоумышленника, проводящего атаку на алгоритм широковещательного шифрования, состоит из процедуры инициализации, 2-х этапов проведения запросов, постановки задачи и вывода результата.
Инициализация
Запросчик принимает параметр стойкости <math>k \in \mathbb{N}</math>, запускает процедуру инициализации алгоритма, передает атакующему алгоритму параметры <math>params</math> и сохраняет мастер-ключи <math>master-keys</math> в секрете. Определены <math>G_1</math> — аддитивная циклическая группа простого порядка <math>q</math> с образующим элементом <math>P</math>, и <math>G_2</math> — мультипликативная циклическая группа простого порядка <math>q</math>.
Этап 1
Атакующий алгоритм генерирует запросы <math>q_1, \ldots, q_m</math> и отправляет их запросчику, где <math>q_i</math> является:
- Запросом закрытого ключа <math>\langle ID_i'\rangle</math>. В данном случае запросчик запускает процедуру генерации закрытого ключа <math>d_i' \in G_1</math>, соответствующего открытому ключу <math>\langle ID_i'\rangle</math>, и передает <math>d_i' \in G_1</math> атакующему алгоритму.
- Запросом расшифрования <math>\langle ID_i', C_i'\rangle</math>. В данном случае запросчик запускает процедуру генерации закрытого ключа <math>d_i' \in G_1</math>, соответствующего открытому ключу <math>\langle ID_i'\rangle</math>. Далее запускает процедуру расшифрования шифротекста <math>C_i'</math> с помощью <math>d_i'</math> и передает полученный открытый текст атакующему алгоритму.
Данные запросы проводятся адаптивно, то есть каждый запрос <math>q_i</math> может зависеть от ответов на запросы <math>q_1, \ldots, q_{i-1}</math>.
После завершения этапа 1 атакующий алгоритм генерирует 2 открытых текста <math>M_0, M_1 \in \vartheta</math> равной длины и набор идентификаторов абонентов <math>ID_1, \ldots, ID_n</math>, для которых он проводит атаку, где <math>\vartheta</math> — множество открытых текстов произвольной длины. Единственным ограничением является тот факт, что <math>ID_i \neq ID_j'</math> при <math>i=1, \ldots, n, j=1, \ldots, m</math> во время этапа 1.
Постановка задачи
Запросчик случайно выбирает бит <math>b \in \{0,1\}</math> и отправляет <math>C_b=Encrypt(params, ID_1, \ldots, ID_n, M_b)</math> алгоритму.
Этап 2
Атакующий алгоритм генерирует и отправляет запросчику дополнительные запросы <math>q_{m+1}, \ldots, q_l</math>, где <math>q_i</math> является:
- Запросом закрытого ключа <math>\langle ID_j'\rangle</math>, где <math>ID_i \neq ID_j'</math> для <math>i=1, \ldots, n, j=m+1, \ldots, l</math>. Запросчик отвечает так же, как и во время этапа 1.
- Запросом расшифрования <math>\langle ID_j',C_j'\rangle</math>, где <math>\langle ID_j',C_j'\rangle \neq \langle ID_i',C_i'\rangle</math> для <math>i=1, \ldots, n, j=m+1, \ldots, l</math>. Запросчик отвечает так же, как и во время этапа 1.
Данные запросы могут проводиться адаптивно, как и во время этапа 1.
Результат
Атакующий алгоритм возвращает бит <math>b' \in \{0,1\}</math> и выигрывает игру, если <math>b = b'</math>.
Выигрышем при проведении атаки злоумышленника <math>A</math> на алгоритм <math>E</math> называется следующая функция параметра стойкости <math>k \in \mathbb{N}</math>: <math>Adv_{E,A}(k)=\left| Pr[b=b']-\frac{1}{2}\right|</math>, где <math>Pr[b=b']</math> — вероятность события, состоящего в совпадении значений битов <math>b</math> и <math>b'</math>.
Улучшение
На основе алгоритма MulBasicIdent с помощью метода Фуджисаки-Окамото построен полный алгоритм широковещательного шифрования на основе идентификационных данных MulFullIdent.
Примечания
Литература
