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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример:

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

${\displaystyle A_{1}=\{1,2,3\}\ \ \ \ \ A_{2}=\{1,4\}\ \ \ \ \ A_{3}=\{2,4\}\ \ \ \ \ A_{4}=\{3,4\}}$

Здесь, например, ${\displaystyle P_{4}}$ является вторым в ${\displaystyle A_{2},A_{3},A_{4}}$, поэтому он получает доли секрета ${\displaystyle s_{2,2},s_{3,2},s_{4,2}}$

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

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

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

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

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

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

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

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

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

Сложность реализации данной схемы, достигнутая в 2016 году составляет ${\displaystyle O(n)}$.^[7]

Пример:

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

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

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

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

Доли секрета участников равны ${\displaystyle I_{1}=\{s_{3},s_{4}\};\ \ I_{2}=\{s_{1},s_{2}\};\ \ I_{3}=\{s_{2},s_{4}\};\ \ I_{4}=\{s_{1},s_{3}\}}$

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

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

Дилер выбирает вектор ${\displaystyle r=(r_{0},...,r_{m})}$, где разделяемый секрет ${\displaystyle s=r_{0}}$. Доля секрета участника ${\displaystyle i}$: ${\displaystyle s_{i}=M[i]r}$

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

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

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

${\displaystyle \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}$^[4]

Пример:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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