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

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

Предпосылки

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

Определение

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

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

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

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

${\mbox{ENC}}_{\mathrm {pk} }(I,M)=C$.

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

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

Predicate-only Scheme

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

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

• Генерация открытого и закрытого ключей
  1. Выбираются простые числа $p,q,r$, группа $G$, такая что : $G=G_{p}\times G_{q}\times G_{r}$
  2. Выбирается билинейное отображение : ${\hat {e}}\colon 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-мерным вектором ${\vec {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. Связанным закрытым ключом является: $SK_{\vec {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. Пусть, ${\vec {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}\;mod\;q)\cdot ({\vec {x}},{\vec {y}})}}$

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

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

• ID-based encryption

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

• Hidden Vector Encryption

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

${\mbox{F}}_{\mathrm {({a}_{\mathrm {1} }...{a}_{\mathrm {n} })} }({i}_{\mathrm {1} }...{i}_{\mathrm {n} })=1,{i}_{\mathrm {k} }={a}_{\mathrm {k} }\forall k$

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

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

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

См. также

• Attribute-based Encryption
• ID-based encryption