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

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

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

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

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

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

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

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

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

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

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

• Генерация открытого и закрытого ключей
  1. Выбираются простые числа ${\displaystyle p,q,r}$, группа ${\displaystyle G}$, такая что : ${\displaystyle G=G_{p}\times G_{q}\times G_{r}}$
  2. Выбирается билинейное отображение : ${\displaystyle {\hat {e}}\colon G\times G\to G_{t}}$
  3. Выбираются случайные числа: ${\displaystyle 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. Открытым ключом является набор данных : ${\displaystyle 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. Закрытый ключ : ${\displaystyle SK=(p,q,r,g_{q},h_{1,i},h_{2,i},i={\overline {1,n}})}$
• Генерация связанного закрытого ключа
  1. Пусть предикат описывается n-мерным вектором ${\displaystyle {\vec {v}}}$
  2. Выбираются случайные числа : ${\displaystyle 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. Связанным закрытым ключом является: ${\displaystyle 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. Пусть, ${\displaystyle {\vec {x}}=(x_{1},...,x_{n}),x_{i}\in \mathbb {Z} _{N}}$
  2. Выбираются случайные числа ${\displaystyle s,\alpha ,\beta \in \mathbb {Z} _{N},R_{3,i},R_{4,i}\in G_{r}}$
  3. Тогда шифротекст ${\displaystyle 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 только в том случае, если :

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

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

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

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

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

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

• ID-based encryption

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

• Hidden Vector Encryption

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

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

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

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

${\displaystyle {\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}$^[2]

• Attribute-based Encryption
• ID-based encryption