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

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

Предпосылки

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

Определение

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

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

G e n K e y ( S K , F ) = SK F {displaystyle GenKey(SK,F)={mbox{SK}}_{mathrm {F} }} .

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

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

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

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

Predicate-only Scheme

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

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

Генерация открытого и закрытого ключей
Выбираются простые числа p , q , r {displaystyle p,q,r} , группа G {displaystyle G} , такая что : G = G p × G q × G r {displaystyle G=G_{p} imes G_{q} imes G_{r}}
Выбирается билинейное отображение : e ^ : G × G → G t {displaystyle {hat {e}}colon G imes G o G_{t}}
Выбираются случайные числа: R 1 , i , R 2 , i ∈ G r , h 1 , i , h 2 , i ∈ G p , i = 1 , n ¯ , R 0 ∈ G r {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}}
Открытым ключом является набор данных : P K = ( N , G , G t , e ^ , g p , g q , Q = g q ⋅ R 0 , H 1 , i = h 1 , i ⋅ R 1 , i H 2 , i = h 2 , i ⋅ R 2 , i , i = 1 , n ¯ {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}}}
Закрытый ключ : S K = ( p , q , r , g q , h 1 , i , h 2 , i , i = 1 , n ¯ ) {displaystyle SK=(p,q,r,g_{q},h_{1,i},h_{2,i},i={overline {1,n}})}
Генерация связанного закрытого ключа
Пусть предикат описывается n-мерным вектором v → {displaystyle {vec {v}}}
Выбираются случайные числа : r 1 , i , r 2 , i ∈ Z p , i = 1 , n ¯ , R 5 ∈ G r , f 1 , f 2 ∈ Z q , Q 6 ∈ G q {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}}
Связанным закрытым ключом является: S K v → = ( K = R 5 ∗ Q 6 ∗ ∏ i = 1 n h 1 , i − r 1 , i ⋅ h 2 , i − r 2 , i , K 1 , i = g p r 1 , i ⋅ g q f 1 ⋅ v i , K 2 , i = g p r 2 , i ⋅ g q f 2 ⋅ v i ) {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}})}
Шифрование
Пусть, x → = ( x 1 , . . . , x n ) , x i ∈ Z N {displaystyle {vec {x}}=(x_{1},...,x_{n}),x_{i}in mathbb {Z} _{N}}
Выбираются случайные числа s , α , β ∈ Z N , R 3 , i , R 4 , i ∈ G r {displaystyle s,alpha ,eta in mathbb {Z} _{N},R_{3,i},R_{4,i}in G_{r}}
Тогда шифротекст C = ( C 0 = g p s , C 1 , i = H 1 , i s ⋅ Q α x i ⋅ R 3 , i , C 2 , i = H 2 , i s ⋅ Q β x i ⋅ R 34 , i ) {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^{eta x_{i}}cdot R_{34,i})}
Расшифрование

На выходе алгоритма расшифрования получится 1 только в том случае, если : e ^ ( C 0 , K ) ⋅ ∏ i = 1 n e ^ ( C 1 , i , K 1 , i ) ⋅ 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})}=1}

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

e ^ ( C 0 , K ) ⋅ ∏ i = 1 n e ^ ( C 1 , i , K 1 , i ) ⋅ e ^ ( C 1 , i , K 1 , i ) = e ^ ( g p s , R 5 Q 6 ∏ i = 1 n h 1 , i − r 1 , i ⋅ h 2 , i − r 2 , i ) ⋅ {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 } ⋅ ∏ i = 1 n e ^ ( H 1 , i s ⋅ Q α x i ⋅ R 3 , i , g p r 1 , i ⋅ g q f 1 ⋅ v i ) ⋅ e ^ ( H 2 , i s ⋅ Q α x i ⋅ R 4 , i , g p r 2 , i ⋅ g q f 2 ⋅ v i ) = {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}})}=} = e ^ ( g p s , ∏ i = 1 n h 1 , i − r 1 , i ⋅ h 2 , i − r 2 , i ) ⋅ ∏ i = 1 n e ^ ( h 1 , i s ⋅ g q α x i , g p r 1 , i ⋅ g p f 1 ⋅ v i ) ⋅ e ^ ( h 2 , i s ⋅ g q α x i , g p r 2 , i ⋅ g q f 2 ⋅ 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}})}=} = ∏ i = 1 n e ^ ( g q , g q ) ( α f 1 + β f 2 ) x i v i = e ^ ( g q , g q ) ( α f 1 + β f 2 m o d q ) ⋅ ( x → , y → ) {displaystyle =prod _{i=1}^{n}{{hat {e}}(g_{q},g_{q})^{(alpha f_{1}+eta f_{2})x_{i}v_{i}}}={hat {e}}({g_{q},g_{q})^{(alpha f_{1}+eta f_{2};mod;q)cdot ({vec {x}},{vec {y}})}}}

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

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

ID-based encryption

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

Hidden Vector Encryption

Схема, в которой предикаты и сообщения определяются векторами. Корректное расшифрование происходит, если данные векторы совпадают покомпонентно. То есть: F ( a 1 . . . a n ) ( i 1 . . . i n ) = 1 , i k = a k ∀ k {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}

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

Схема, в которой значение предиката определяется скалярным произведением атрибута и закрытого ключа, ассоциированного с этим предикатом. F ( a 1 . . . a n ) ( i 1 . . . i n ) = 1 , ∑ i = 1 n i k ∗ a k = 0 {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}