Attribute-based Encryption

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

Общая схема Attribute-based Encryption

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

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

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

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

Структуры доступа

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

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

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

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

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

Описание алгоритма

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

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

$d$ — пороговое значение.

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

Генерация открытого ключа и универсального ключа

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

Генерация закрытых ключей

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

Шифрование

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

${\displaystyle }$

Расшифрование

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

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

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

Key-policy Attribute-based Encryption (ABE-шифрование с правилом доступа на основе закрытого ключа)

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

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

Ciphertext-policy Attribute-based Encryption (ABE-шифрование с правилом доступа на основе шифротекста)

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

Схема ABE c немонотонными структурами доступа

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

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

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

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

См. также

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