Attribute-based Encryption

Attribute-based Encryption (рус. Шифрование на основе атрибутов, ABE-шифрование) — разновидность алгоритмов шифрования с открытым ключом, в которых закрытый ключ, применяемый пользователем для расшифрования данных, зависит от некоторых атрибутов пользователя (например, должность, место жительства, тип учётной записи). Идея ABE была впервые опубликована Amit Sahai и Brent Waters^[1] и была в дальнейшем развита в работах Vipul Goyal, Omkant Pandey, Amit Sahai и Brent Waters^[2].

Схема была предложена Sahai и Waters в 2005 году. В ней участвуют владелец данных (передающий данные), пользователь (принимающий данные) и третья сторона (доверенный центр), чья роль заключается в том, чтобы генерировать ключи для шифрования и расшифрования данных владельцами данных и пользователями.

Ключи (в частности, открытый ключ и универсальный ключ) генерируются по установленному полному набору атрибутов. Если к системе присоединится пользователь с новым атрибутом, атрибут будет добавлен к набору, а открытый и универсальный ключи будут сгенерированы заново.

Владелец данных шифрует данные при помощи открытого ключа и некоторого набора атрибутов.

Пользователь может расшифровать данные при помощи собственного закрытого ключа, который он получает от доверенного центра. Проверяется соответствие между атрибутами, которые составляют закрытый ключ пользователя, и атрибутами зашифрованных данных. Если число совпадающих атрибутов превышает установленный порог ${\displaystyle d}$, закрытый ключ пользователя сможет расшифровать данные. (Пусть, например, атрибуты шифрованных данных {«Кафедра радиотехники», «Преподаватель», «Студент»}, ${\displaystyle d=2}$. Чтобы пользователь смог расшифровать данные и получить к ним доступ, в наборе атрибутов, составляющих его закрытый ключ, должны присутствовать по крайней мере два из трёх атрибутов шифрованных данных).

Пусть ${\displaystyle \{P_{1},P_{2},...,P_{n}\}}$ — множество атрибутов. Набор ${\displaystyle \mathbb {A} \subseteq 2^{\{P_{1},P_{2},...,P_{n}\}}}$ называется монотонным, если:

${\displaystyle \forall B,C:B\in \mathbb {A} ,B\subseteq C\to C\in \mathbb {A} }$.

Структура доступа (монотонная структура доступа) — набор (монотонный набор) ${\displaystyle \mathbb {A} }$ непустых подмножеств ${\displaystyle \{P_{1},P_{2},...,P_{n}\}}$, то есть ${\displaystyle \mathbb {A} \subseteq 2^{\{P_{1},P_{2},...,P_{n}\}}\setminus \{\varnothing \}}$. Наборы атрибутов, которые входят в ${\displaystyle \mathbb {A} }$ — авторизованные наборы, пользователям с ними разрешён доступ к данным; наборы, которые не принадлежат ${\displaystyle \mathbb {A} }$ — неавторизованные наборы атрибутов.

Применение схемы шифрования на основе атрибутов в её первоначальном виде ограничено монотонными структурами доступа. В 2007 году было предложено обобщение^[3] схемы на случай немонотонных структур, однако оно не является эффективным^[4].

Структура доступа может быть представлена в виде дерева, в котором узлы-листья представляют собой атрибуты, а остальные узлы характеризуются своими дочерними вершинами и пороговыми значениями. Пусть, например, узел ${\displaystyle x}$ имеет ${\displaystyle num_{x}}$ дочерних вершин; его пороговое значение ${\displaystyle k_{x}}$, ${\displaystyle 0<k_{x}\leqslant num_{x}}$. Если пороговое значение этого узла ${\displaystyle k_{x}=1}$, то он представляет собой логический элемент «ИЛИ», поскольку для достижения порогового значения достаточно присутствия у пользователя одного из дочерних атрибутов. Если же пороговое значение ${\displaystyle k_{x}=num_{x}}$, то он, очевидно, реализует элемент «И».

Пусть ${\displaystyle G_{1}}$, ${\displaystyle G_{2}}$ — билинейные группы порядка ${\displaystyle p}$ (${\displaystyle p}$ — простое), ${\displaystyle g}$ — генератор группы ${\displaystyle G_{1}}$;

${\displaystyle e:G_{1}\times G_{2}\to G_{2}}$ — билинейное отображение;

${\displaystyle d}$ — пороговое значение.

Общая схема состоит из четырёх этапов, для каждого из которых существует соответствующий алгоритм.

Доверенный центр случайным образом выбирает ${\displaystyle t_{1},...,t_{n},y}$ из конечного поля ${\displaystyle Z_{q}}$ и вычисляет открытый ключ ${\displaystyle PK=(T_{1}=g^{t_{1}},...,T_{n}=g^{t_{n}},Y=e(g,g)^{y})}$, где ${\displaystyle g}$ — генератор некоторой билинейной группы ${\displaystyle G_{1}}$ порядка ${\displaystyle p}$ (${\displaystyle p}$ — простое). На этом этапе также генерируется универсальный ключ ${\displaystyle MK=(t_{1},...,t_{n},y)}$.

Доверенный центр генерирует закрытый ключ для каждого пользователя ${\displaystyle U}$; ${\displaystyle A_{U}}$ — набор атрибутов пользователя. Случайным образом выбирается полином ${\displaystyle q}$ степени ${\displaystyle d-1}$ такой, что выполняется ${\displaystyle q(0)=y}$. Закрытый ключ пользователя ${\displaystyle D=\{D_{i}=g^{\frac {q(i)}{t_{i}}}\}_{\forall i\in A_{U}}}$.

Владелец данных шифрует сообщение ${\displaystyle M\in G_{2}}$ с использованием набора атрибутов ${\displaystyle A_{C}T}$ и случайно выбранного числа ${\displaystyle s\in Z_{q}}$: ${\displaystyle CT=(A_{CT},E=MY^{s}=e(g,g)^{ys},\{E_{i}=g^{t_{i}s}\}_{\forall i\in A_{U}})}$

${\displaystyle }$

Если ${\displaystyle \left|A_{U}\cap A_{C}T\right|\geqslant d}$, из ${\displaystyle i\in A_{U}\cap A_{C}T}$ выбирается ${\displaystyle d}$ атрибутов для вычисления значений ${\displaystyle e(E_{i},D_{i})=e(g,g)^{q(i)s}}$, ${\displaystyle Y^{s}=e(g,g)^{q(0)s}=e(g,g)ys}$.

Исходное сообщение ${\displaystyle M={\frac {E}{Y^{s}}}}$.

Закрытые ключи в такой схеме генерируются по принципу разделения секрета: части секрета y включаются в компоненты ${\displaystyle D_{i}}$ закрытого ключа пользователя; закрытому ключу соответствует случайный полином ${\displaystyle q(i)}$. В результате соединения нескольких закрытых ключей нельзя получить новый закрытый ключ, что предотвращает возможность атаки в результате сговора пользователей.

В 2006 году в работе Goyal^[2] была предложена схема ABE-шифрования с правилом доступа на основе закрытого ключа (Key-policy Attribute-based Encryption). В ней шифрованные данные описываются набором атрибутов, а правило доступа к данным содержится в закрытом ключе пользователя. Если набор атрибутов данных соответствует структуре доступа в закрытом ключе пользователя, данные могут быть расшифрованы. Например, данные зашифрованы с атрибутами {«Кафедра радиотехники» ${\displaystyle \wedge }$ «Студент»}, а закрытый ключ пользователя соответствует структуре доступа {«Кафедра радиотехники» ${\displaystyle \wedge }$ («Преподаватель» ${\displaystyle \vee }$ «Студент»)}. Атрибуты зашифрованных данных соответствуют структуре доступа закрытого ключа пользователя, поэтому пользователь сможет расшифровать данные.

Алгоритм шифрования отличается от первоначальной версии ABE на этапах генерации закрытых ключей и, соответственно, расшифрования: закрытый ключ пользователя генерируется соответственно необходимой структуре доступа. При разделении секрета для вершин от корня до каждой конечной вершины x выбирается полином ${\displaystyle q_{x}}$ такой, что ${\displaystyle q_{x}(0)=q_{parent(x)}(index(x))}$, где ${\displaystyle parent(x)}$ — узел-родитель по отношению к ${\displaystyle x}$, а ${\displaystyle index(x)}$ — номер вершины ${\displaystyle x}$ среди вершин, принадлежащих тому же родителю. Таким образом, ${\displaystyle q_{r}(0)}$ соответствует универсальному ключу ${\displaystyle y}$, который распределяется по листьям дерева, соответствующим компонентам закрытого ключа.

В 2007 году Bethencourt и др. предложили в своей работе^[5] схему ABE-шифрования с правилом доступа на основе шифротекста. Контроль доступа производится схожим с CK-ABE образом, однако правило доступа к данным содержится не в закрытом ключе пользователя, а в самих шифрованных данных (шифротексте); закрытый ключ пользователя в то же время соответствует набору атрибутов. Если атрибуты, которые содержатся в закрытом ключе пользователя, соответствуют структуре доступа шифротекста, пользователь может расшифровать данные. Если, например, структура доступа, содержащаяся в данных: {«Кафедра радиотехники» ${\displaystyle \wedge }$ («Преподаватель» ${\displaystyle \vee }$ «Студент»)}, а набор атрибутов в закрытом ключе пользователя: {«Кафедра радиотехники» ${\displaystyle \wedge }$ «Преподаватель»}, пользователь сможет получить доступ к данным.

Изначально в схемах шифрования на основе атрибутов на структуры доступа накладывалось ограничения, а именно подразумевалась монотонность этих структур. Дерево, соответствующее структуре, могло содержать логические элементы «И», «ИЛИ», но не логический элемент «НЕ», что накладывало некоторые ограничения на возможные правила доступа.

Например, если преподаватель кафедры радиотехники хочет разделить некоторые данные со студентами, но не выпускниками, структура доступа должна выглядеть как {«Кафедра радиотехники»${\displaystyle \wedge }$ «Студент»${\displaystyle \wedge }$ «НЕ_Выпускник»}.

Способ расширения алгоритма на случай немонотонных структур доступа было предложено в 2007 году в работе Ostrovsky и др.^[3]. В пространство атрибутов вместе с каждым элементом добавляется его отрицание; таким образом, общее количество возможных атрибутов увеличивается вдвое по сравнению с классической схемой. В остальном принцип работы алгоритма остается прежним.

Такая схема имеет значительные недостатки. Если в структуре доступа предполагается явным образом указать отрицание всех атрибутов, по которым не предполагается открывать доступ к данным, то в результате в шифротексте может содержаться большое количество отрицаний атрибутов, которые не имеют практического значения для расшифрования данных; в результате размер шифротекста сильно увеличивается. Кроме того, после шифрования данных в системе могут появиться новые атрибуты, и шифрование придётся производить заново.

• Предикативное шифрование
• ID-based encryption