Схемы разделения секрета для произвольных структур доступа

Схемы разделения секрета для произвольных структур доступа (англ. Secret sharing with generalized access structure) — схемы разделения секрета, которые позволяют задать произвольный набор групп участников (квалифицированных подмножеств), имеющих возможность восстановить секрет (структуру доступа).

История

В 1979 году израильский криптоаналитик Ади Шамир предложил пороговую схему разделения секрета между $n$ сторонами, обладающую следующими свойствами:

• Для восстановления секрета достаточно $k$ и больше сторон.
• Никакие $k-1$ и меньше сторон не смогут получить никакой информации о секрете.

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

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

Японские ученые Мицуро Ито, Акиро Саито и Такао Нишизеки первые начали изучать разделение секрета для произвольных структур доступа и в 1987 году предложили свою схему. Их мысль развили Джош Бенало и Джерри Лейхтер, предложив в 1988 году схему разделения для монотонных структур. В 1989 Эрнест Бриккелл предложил схему, в которой участникам раздаются не доли секрета, а их линейные комбинации.

Определение используемых терминов

Дилер — участник процедуры (протокола), который, зная секрет, вычисляет доли секрета и раздаёт эти доли остальным участникам.

Квалифицированное подмножество — множество участников группы, для которого разрешено восстановление секрета.

Примером, иллюстрирующим появление квалифицированных подмножеств, может служить разделение секрета между управленцами. В случае, если секрет может быть восстановлен либо всеми тремя управленцами, либо любым управленцем и любым вице-президентом, либо президентом в одиночку, квалифицированными подмножествами будут президент, вице-президент и управленец, или любые три управленца.

Структура доступа — перечисление квалифицированного и неквалифицированных подмножеств.

Пусть $A$ — множество участников группы, $n$ — количество участников группы, $2^{[n]}$ — множество, состоящее из всех возможных подмножеств участников группы. Пусть $\mathrm{\Gamma }$ — множество, состоящее из подмножеств участников, которым разрешено восстановление секрета (квалифицированные множества участников), $\mathrm{\Delta }$ — множество, состоящее из подмножеств участников, которые не могут восстановить секрет. Структура доступа обозначается как ($\mathrm{\Gamma }$,$\mathrm{\Delta }$).

Структура доступа называется монотонной, если все надмножества квалифицированных подмножеств также входят в $\mathrm{\Gamma }$, то есть $A\in \mathrm{\Gamma },A\subseteq B\subseteq P\Rightarrow B\in \mathrm{\Gamma }$

Предположим ($\mathrm{\Gamma }$,$\mathrm{\Delta }$) — структура доступа на $A$ . $B\in \mathrm{\Gamma }$называют минимальным квалифицированным подмножеством, если $C\in ̸\mathrm{\Gamma }$ всегда, когда $C\subset B$. Множество минимальных квалифицированных подмножеств $\mathrm{\Gamma }$ обозначается как ${\mathrm{\Gamma }}_{min}$ и называется базисом $\mathrm{\Gamma }$. Минимальное квалифицированное подмножество однозначно задает структуру доступа.

Схема Бенало-Лейхтера

Пусть задана монотонная структура доступа $A$ и ${\mathrm{\Gamma }}_{min}$— множество минимальных квалифицированных подмножеств, соответствующее $A$. Пусть ${\mathrm{\Gamma }}_{min}=\{A_1,A_2,...,A_m\}$ . Для каждого $A_i$ вычисляются доли секрета для участников этого подмножества $s_{i1},s_{i2},...,s_{i|A|}$ с помощью любой $(|A_i|,|A_i|)$ — пороговой схемы разделения секрета.

Доля секрета $s_{i,j}$ передается соответствующему участнику. В результате каждый участник получает набор долей секрета. Восстановление секрета происходит по выбранной (n, n)-пороговой схеме.

Пример:

${\mathrm{\Gamma }}_{min}=\{\{1,2,3\},\{1,4\},\{2,4\},\{3,4\}\}$

$A_1=\{1,2,3\}{A}_2=\{1,4\}{A}_3=\{2,4\}{A}_4=\{3,4\}$

Здесь, например, $P_4$ является вторым в $A_2,A_3,A_4$, поэтому он получает доли секрета $s_{2,2},s_{3,2},s_{4,2}$

Аналогично для остальных участников

$P_1\leftarrow s_{1,1},s_{2,1}{P}_2\leftarrow s_{1,2},s_{3,1}{P}_3\leftarrow s_{1,3},s_{4,1}$

Недостаток данной схемы — возрастающий объём долей секрета для каждого участника при увеличении ${\mathrm{\Gamma }}_{min}$.

Схема Ито-Саито-Нишизеки

Ито, Саито, Нишизеки представили так называемую технику кумулятивного массива для монотонной структуры доступа.

Пусть $A$ — монотонная структура доступа размером $n$ и пусть $A_1,...,A_m$ — соответствующие ей максимальные неквалифицированные подмножества участников.

Кумулятивный массив структуры доступа $A$ есть матрица размеров $n\times m$ $(C_{i,j}^A{)}_{1\le i\le n,1\le j\le m}$, где $C_{i,j}^A=\{\begin{array}{cc}0,& \text{если }i\in A_j\\ 1,& \text{если }i\in ̸A_j\end{array}$ и обозначается как $C^A$. То есть столбцы матрицы отвечают неквалифицированным подмножествам, а значение по строкам внутри столбца будет единицей, если элемент не входит в данное подмножество.

В данной схеме можно использовать любую $(m,m)$ — пороговую схему разделения секрета с секретом $S$ и соответствующими долями $s_1,...,s_m$

Доли $I_1,...,I_n$ соответствующие секрету $S$ будут определятся как множество $s_j$: $I_i=\{s_j|C_{i,j}^A=1\}$

Восстановление секрета происходит по выбранной $(m,m)$ — пороговой схеме.

Сложность реализации данной схемы, достигнутая в 2016 году составляет $O(n)$.

Пример:

Пусть $n=4$, $\mathrm{\Gamma }=\{\{1,2\},\{3,4\},\{1,2,3\},\{1,2,4\},\{1,3,4\},\{2,3,4\}\}$.

Соответствующее $A$ множество минимальных квалифицированных подмножеств ${\mathrm{\Gamma }}_{min}=\{\{1,2\},\{3,4\}\}$

В этом случае ${\mathrm{\Delta }}_{max}=\{\{1,3\},\{1,4\},\{2,3\},\{2,4\}\}$ и $m=4$.

Кумулятивный массив структуры доступа $A$ имеет вид $C^A=\left(\begin{array}{cccc}0& 0& 1& 1\\ 1& 1& 0& 0\\ 0& 1& 0& 1\\ 1& 0& 1& 0\end{array}\right)$

Доли секрета участников равны $I_1=\{s_3,s_4\};I_2=\{s_1,s_2\};I_3=\{s_2,s_4\};I_4=\{s_1,s_3\}$

Восстановление секрета аналогично восстановлению секрета в $(4,4)$ — пороговой схеме Шамира.

Линейная схема разделения секрета Брикелла

Для структуры доступа $A$ и набора участников $P=\{P_1,...,P_n\}$ составляется матрица $M$ размера $n\times m$ , в которой строка $M[i]$ длины $m$ ассоциируется с участником $i$. Для подмножества участников $x\subset \mathrm{\Gamma }$, которому соответствует набор строк матрицы $M$ — $M_x$, должно выполняться условие, что вектор $(1,0,...,0)$ принадлежит линейной оболочке, натянутой на $M_x$.

Дилер выбирает вектор $r=(r_0,...,r_m)$, где разделяемый секрет $s=r_0$. Доля секрета участника $i$: $s_i=M[i]r$

Восстановление секрета.

Выбирается вектор $\alpha$, длины $m$, ${\alpha }_x$ — вектор, составленный из координат $\alpha$, соответствующих набору участников $x\subset \mathrm{\Gamma }$.

Для каждого $x\subset \mathrm{\Gamma }$ должно выполняться условие: ${\alpha }_x{M}_x=(1,0,....,0)$. Тогда секрет можно восстановить по формуле:

$\sum _{i\in x}{s}_i{\alpha }_i=\sum _{i\in x}(M[i]r){\alpha }_i=(\sum _{i\in x}{\alpha }_{i}M[i])r=(1,0,...,0)r=s$

Пример:

Множество минимальных квалифицированных подмножество $\mathrm{\Gamma }=\{\{1,2,3\},\{1,4\}\}$.

Подходящая матрица:

$\left(\begin{array}{ccc}0& 1& 0\\ 1& 0& 1\\ 0& 1& -1\\ 1& 1& 0\end{array}\right)$

$M$ удовлетворяет требованию схемы:

Для $\{1,2,3\}$: $(1,0,0)=-(0,1,0)+(1,0,1)+(0,1,-1)$

Для $\{1,4\}$: $(1,0,0)=-(0,1,0)+(1,1,0)$

Доли секрета каждого участника:

$P_1\leftarrow r_1;P_2\leftarrow s+r_2;P_3\leftarrow r_1-r_2;P_4\leftarrow s+r_1$

Восстановление секрета:

Для восстановления секрета выбирается $\alpha =(-1,1,1,1)$

Тогда для $x=\{1,2,3\}$: ${\alpha }_x=(-1,1,1)$

$(-1,1,1)\left(\begin{array}{ccc}0& 1& 0\\ 1& 0& 1\\ 0& 1& -1\end{array}\right)=(1,0,0)$

А для $x=\{1,4\}$: ${\alpha }_x=(-1,1)$

$(-1,1)\left(\begin{array}{ccc}0& 1& 0\\ 1& 1& 0\end{array}\right)=(1,0,0)$

Применение

Данные схемы применяются в протоколах условного раскрытия секрета (англ. conditional disclosure of secrets, CDS), безопасных распределенных вычислениях, задачах распределения ключей и схемах аутентификации нескольких приемников.