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

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

ИсторияПравить

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

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

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

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

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

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

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

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

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

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

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

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

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

Схема Бенало-ЛейхтераПравить

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

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

Пример:

${\mathrm{\Gamma <!--\; \Gamma \; -->}}_{min}=\{\{1,2,3\},\{1,4\},\{2,4\},\{3,4\}\}$$\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\}$$A_{1}=\{1,2,3\}\ \ \ \ \ A_{2}=\{1,4\}\ \ \ \ \ A_{3}=\{2,4\}\ \ \ \ \ A_{4}=\{3,4\}$ 

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

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

$P_1\leftarrow <!--\; \leftarrow \; -->s_{1,1},s_{2,1}{P}_2\leftarrow <!--\; \leftarrow \; -->s_{1,2},s_{3,1}{P}_3\leftarrow <!--\; \leftarrow \; -->s_{1,3},s_{4,1}$$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 <!--\; \Gamma \; -->}}_{min}$$\Gamma _{min}$ .

Схема Ито-Саито-НишизекиПравить

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

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

Кумулятивный массив структуры доступа $A$$A$  есть матрица размеров $n\times <!--\; \times \; -->m$$n\times m$  $(C_{i,j}^A{)}_{1\le <!--\; \le \; -->i\le <!--\; \le \; -->n,1\le <!--\; \le \; -->j\le <!--\; \le \; -->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$$C^{A}$ . То есть столбцы матрицы отвечают неквалифицированным подмножествам, а значение по строкам внутри столбца будет единицей, если элемент не входит в данное подмножество.

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

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

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

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

Пример:

Пусть $n=4$$n=4$ , $\mathrm{\Gamma <!--\; \Gamma \; -->}=\{\{1,2\},\{3,4\},\{1,2,3\},\{1,2,4\},\{1,3,4\},\{2,3,4\}\}$$\Gamma =\{\{1,2\},\{3,4\},\{1,2,3\},\{1,2,4\},\{1,3,4\},\{2,3,4\}\}$ .

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

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

Кумулятивный массив структуры доступа $A$$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\}$$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)$$(4,4)$  — пороговой схеме Шамира.

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

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

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

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

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

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

$\underset{i\in <!--\; \in \; -->x}{\sum <!--\; \sum \; -->}{s}_i{\mathrm{\alpha <!--\; \alpha \; -->}}_i=\underset{i\in <!--\; \in \; -->x}{\sum <!--\; \sum \; -->}(M[i]r){\mathrm{\alpha <!--\; \alpha \; -->}}_i=(\underset{i\in <!--\; \in \; -->x}{\sum <!--\; \sum \; -->}{\mathrm{\alpha <!--\; \alpha \; -->}}_{i}M[i])r=(1,0,...,0)r=s$$\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 <!--\; \Gamma \; -->}=\{\{1,2,3\},\{1,4\}\}$$\Gamma =\{\{1,2,3\},\{1,4\}\}$ .

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

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

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

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

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

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

$P_1\leftarrow <!--\; \leftarrow \; -->r_1;P_2\leftarrow <!--\; \leftarrow \; -->s+r_2;P_3\leftarrow <!--\; \leftarrow \; -->r_1-<!--\; -\; -->r_2;P_4\leftarrow <!--\; \leftarrow \; -->s+r_1$$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$ 

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

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

Тогда для $x=\{1,2,3\}$$x=\{1,2,3\}$ : ${\mathrm{\alpha <!--\; \alpha \; -->}}_x=(-<!--\; -\; -->1,1,1)$$\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\}$$x=\{1,4\}$ : ${\mathrm{\alpha <!--\; \alpha \; -->}}_x=(-<!--\; -\; -->1,1)$$\alpha _{x}=(-1,1)$ 

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

ПрименениеПравить

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