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

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

История

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть задана монотонная структура доступа $A$ и $\Gamma _{min}$— множество минимальных квалифицированных подмножеств, соответствующее $A$. Пусть $\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)-пороговой схеме.

Пример:

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

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

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

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

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

Кумулятивный массив структуры доступа $A$ есть матрица размеров $n\times m$ $(C_{i,j}^{A})_{1\leq i\leq n,1\leq j\leq m}$, где $C_{i,j}^{A}={\begin{cases}0,&{\text{если }}i\in A_{j}\\1,&{\text{если }}i\not \in A_{j}\end{cases}}$ и обозначается как $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$, $\Gamma =\{\{1,2\},\{3,4\},\{1,2,3\},\{1,2,4\},\{1,3,4\},\{2,3,4\}\}$.

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

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

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

Доли секрета участников равны $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 \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 \Gamma$.

Для каждого $x\subset \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$

Пример:

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

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

${\begin{pmatrix}0&1&0\\1&0&1\\0&1&-1\\1&1&0\end{pmatrix}}$

$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};\qquad P_{2}\leftarrow s+r_{2};\qquad P_{3}\leftarrow r_{1}-r_{2};\qquad P_{4}\leftarrow s+r_{1}\qquad$

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

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

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

$(-1,1,1){\begin{pmatrix}0&1&0\\1&0&1\\0&1&-1\end{pmatrix}}=(1,0,0)$

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

$(-1,1){\begin{pmatrix}0&1&0\\1&1&0\end{pmatrix}}=(1,0,0)$

Применение

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