Предикативное шифрование

Предикативное шифрование (Шаблон:Lang-en) — схема шифрования, при которой существует функциональная зависимость между шифротекстом и закрытым ключом. Закрытый ключ, связанный с предикатом $F$, может быть использован для расшифрования текста, ассоциированного с атрибутом $I$, только в том случае, когда $F(I)=1$.

Предпосылки

Традиционная модель шифрования на открытом ключе недостаточно общая: отправитель шифрует сообщение на открытом ключе, и только владелец закрытого ключа, ассоциированного с открытым ключом, может расшифровать полученный текст и восстановить сообщение. Такой подход возможен только для связи вида точка — точка, когда зашифрованные данные предназначены для одного конкретного пользователя, который известен отправителю заранее. В других же задачах, в которых отправитель данных хочет установить некую политику, определяющую круг лиц, которым разрешён доступ к данным, данный подход не работает. На практике встречается достаточно много подобных задач, следовательно, требуется новый подход, который обеспечивает более универсальный контроль над зашифрованными данными. Предикативное шифрование является одним из таких подходов.

Определение

Схема предикативного шифрования для класса предикатов $F$ над множеством атрибутов $\mathrm{\Sigma }$ состоит из следующих 4-х алгоритмов:

• Создание открытого и «главного» закрытого ключей, $PK$ и $SK$ соответственно.
• Генерация закрытого ключа, связанного с конкретным предикатом $F$

$GenKey(SK,F)={\text{SK}}_{\mathrm{F}}$.

• Шифрование сообщения $M$ производится при помощи открытого ключа $PK$ и атрибута $I$, описывающего сообщение $M$

${\text{ENC}}_{\mathrm{p}\mathrm{k}}(I,M)=C$.

• Функция расшифрования возвращает исходное сообщение $M$ только в том случае, когда предикат $F$ и атрибут $I$ связаны между собой, а именно если:

• $F(I)=1,{\text{DEC}}_{{\text{sk}}_{\mathrm{f}}}(C)=M$
• $F(I)=0,{\text{DEC}}_{{\text{sk}}_{\mathrm{f}}}(C)=\mathrm{\varnothing }$.

Predicate-only Scheme

Описание схемы

В данной схеме шифротекст связан с некоторым вектором $\overrightarrow{x}$, а закрытый ключ — с вектором $\overrightarrow{v}$. В процессе расшифрования необходимо проверить, что скалярное произведение $\overrightarrow{x}\cdot \overrightarrow{v}=0modN$. В процессе проверки данного соотношения пользователь не должен получать никакой информации о векторе $\overrightarrow{x}$. Для этого используется билинейная группа $G$ порядка $N$, где $N$ — произведение трёх простых чисел. Более детально данная схема выглядит следующим образом:

• Генерация открытого и закрытого ключей
  1. Выбираются простые числа $p,q,r$, группа $G$, такая что : $G=G_p\times G_q\times G_r$
  2. Выбирается билинейное отображение : $\hat{e}:G\times G\to G_t$
  3. Выбираются случайные числа: $R_{1,i},R_{2,i}\in G_r,h_{1,i},h_{2,i}\in G_p,i=\overline{1,n},R_0\in G_r$
  4. Открытым ключом является набор данных : $PK=(N,G,G_t,\hat{e},g_p,g_q,Q=g_q\cdot R_0,H_{1,i}=h_{1,i}\cdot R_{1,i}{H}_{2,i}=h_{2,i}\cdot R_{2,i},i=\overline{1,n}$
  5. Закрытый ключ : $SK=(p,q,r,g_q,h_{1,i},h_{2,i},i=\overline{1,n})$
• Генерация связанного закрытого ключа
  1. Пусть предикат описывается n-мерным вектором $\overrightarrow{v}$
  2. Выбираются случайные числа : $r_{1,i},r_{2,i}\in {\mathbb{Z}}_p,i=\overline{1,n},R_5\in G_r,f_1,f_2\in {\mathbb{Z}}_q,Q_6\in G_q$
  3. Связанным закрытым ключом является: $S{K}_{\overrightarrow{v}}=(K=R_5*Q_6*\prod _{i=1}^n{h}_{1,i}^{-r_{1,i}}\cdot h_{2,i}^{-r_{2,i}},K_{1,i}=g_p^{r_{1,i}}\cdot g_q^{f_1\cdot v_i},K_{2,i}=g_p^{r_{2,i}}\cdot g_q^{f_2\cdot v_i})$
• Шифрование
  1. Пусть, $\overrightarrow{x}=(x_1,...,x_n),x_i\in {\mathbb{Z}}_N$
  2. Выбираются случайные числа $s,\alpha ,\beta \in {\mathbb{Z}}_N,R_{3,i},R_{4,i}\in G_r$
  3. Тогда шифротекст $C=(C_0=g_p^s,C_{1,i}=H_{1,i}^s\cdot Q^{\alpha x_i}\cdot R_{3,i},C_{2,i}=H_{2,i}^s\cdot Q^{\beta x_i}\cdot R_{34,i})$
• Расшифрование

На выходе алгоритма расшифрования получится 1 только в том случае, если :

$\hat{e}(C_0,K)\cdot \prod _{i=1}^n\hat{e}(C_{1,i},K_{1,i})\cdot \hat{e}(C_{1,i},K_{1,i})=1$

Проверка корректности схемы

$\hat{e}(C_0,K)\cdot \prod _{i=1}^n\hat{e}(C_{1,i},K_{1,i})\cdot \hat{e}(C_{1,i},K_{1,i})=\hat{e}(g_p^s,R_5{Q}_6\prod _{i=1}^n{h}_{1,i}^{-r_{1,i}}\cdot h_{2,i}^{-r_{2,i}})\cdot$

$\cdot \prod _{i=1}^n\hat{e}(H_{1,i}^s\cdot Q^{\alpha x_i}\cdot R_{3,i},g_p^{r_{1,i}}\cdot g_q^{f_1\cdot v_i})\cdot \hat{e}(H_{2,i}^s\cdot Q^{\alpha x_i}\cdot R_{4,i},g_p^{r_{2,i}}\cdot g_q^{f_2\cdot v_i})=$

$=\hat{e}(g_p^s,\prod _{i=1}^n{h}_{1,i}^{-r_{1,i}}\cdot h_{2,i}^{-r_{2,i}})\cdot \prod _{i=1}^n\hat{e}(h_{1,i}^s\cdot g_q^{\alpha x_i},g_p^{r_{1,i}}\cdot g_p^{f_1\cdot v_i})\cdot \hat{e}(h_{2,i}^s\cdot g_q^{\alpha x_i},g_p^{r_{2,i}}\cdot g_q^{f_2\cdot v_i})=$

$=\prod _{i=1}^n\hat{e}(g_q,g_q{)}^{(\alpha f_1+\beta f_2)x_i{v}_i}=\hat{e}(g_q,g_q{)}^{(\alpha f_1+\beta f_{2}modq)\cdot (\overrightarrow{x},\overrightarrow{y})}$

Так как $(\overrightarrow{x},\overrightarrow{y})=0$ , то схема верна.

Примеры других схем

• ID-based encryption

Схема, в которой отрытым ключом пользователя может служить некоторая уникальная информация о пользователе, например его e-mail адрес.

• Hidden Vector Encryption

Схема, в которой предикаты и сообщения определяются векторами. Корректное расшифрование происходит, если данные векторы совпадают покомпонентно. То есть:

${\text{F}}_{\mathrm{(}{\mathrm{a}}_{\mathrm{1}}\mathrm{.}\mathrm{.}\mathrm{.}{\mathrm{a}}_{\mathrm{n}}\mathrm{)}}(i_{\mathrm{1}}...i_{\mathrm{n}})=1,i_{\mathrm{k}}=a_{\mathrm{k}}\mathrm{\forall }k$

• Схема, основанная на скалярном произведении (Inner Product Encryption)

Схема, в которой значение предиката определяется скалярным произведением атрибута и закрытого ключа, ассоциированного с этим предикатом.

${\text{F}}_{\mathrm{(}{\mathrm{a}}_{\mathrm{1}}\mathrm{.}\mathrm{.}\mathrm{.}{\mathrm{a}}_{\mathrm{n}}\mathrm{)}}(i_{\mathrm{1}}...i_{\mathrm{n}})=1,\sum _{i=1}^n{i}_{\mathrm{k}}*a_{\mathrm{k}}=0$

См. также

• Attribute-based Encryption
• ID-based encryption