Схема Асмута — Блума

Схема Асмута — Блума — пороговая схема разделения секрета, построенная с использованием простых чисел. Позволяет разделить секрет (число) между $n$ сторонами таким образом, что его смогут восстановить любые $m$ участников.

Описание

Пусть $M$ — некоторый секрет, который требуется разделить. Выбирается простое число $p$, большее $M$. Выбирается $n$ взаимно простых друг с другом чисел $d_1,d_2,\dots ,d_n$, таких что:

• $\mathrm{\forall }i:d_i>p$
• $\mathrm{\forall }i:d_i<d_{i+1}$
• $d_1*d_2*\dots d_m>p*d_{n-m+2}*d_{n-m+3}*\dots *d_n$

Выбирается случайное число $r$ и вычисляется

$M^{\prime }=M+rp$

Вычисляются доли:

$k_i=M^{\prime }mod{d}_i$

Участникам раздаются $\{p,d_i,k_i\}$

Теперь, используя китайскую теорему об остатках, можно восстановить секрет $M$, имея $m$ и более долей.

Пример

Предположим, что нам нужно разделить секрет $M=2$ между четырьмя участниками таким образом, чтобы любые три из них могли этот секрет восстановить (а два участника — не могли бы). То есть нужно реализовать (3,4)-пороговую схему.

В качестве простого числа выберем $p=3$, в качестве взаимно простых — $11,13,17,19$. Проверяем, что:

• $\mathrm{\forall }i:d_i>p$

  $\mathrm{\forall }i:i\in \{11,13,17,19\},i>p=3$

• $d_1<d_2<d_3<d_4$

  $11<13<17<19$

• $d_1*d_2*\dots d_m>p*d_{n-m+2}*d_{n-m+3}*\dots *d_n$

  $d_1*d_2*d_3>p*d_3*d_4$

  $11*13*17>3*17*19$

Выбираем случайное число $r=51$ и вычисляем:

$M^{\prime }=M+rp=2+51*3=155$

Вычисляем доли:

$k_i=M^{\prime }mod{d}_i$

$k_1=155mod11=1$

$k_2=155mod13=12$

$k_3=155mod17=2$

$k_4=155mod19=3$

Теперь попробуем восстановить исходный секрет, имея на руках доли $\{3,11,1\}$, $\{3,13,12\}$, $\{3,17,2\}$. Составим систему уравнений:

$1=M^{\prime }mod11$

$12=M^{\prime }mod13$

$2=M^{\prime }mod17$

Мы можем восстановить $M^{\prime }$, используя китайскую теорему об остатках.

Зная $M^{\prime }$, мы восстанавливаем секрет.

$M\equiv M^{\prime }modp$

$M\equiv 155mod3\equiv 2$

В данном примере (так как 155<17*19) два участника спокойно восстановят секрет. M' должно быть больше произведения долей неавторизованных участников.

Обобщенная схема Асмута – Блума в кольце многочленов от нескольких переменных

Рассмотрим кольцо многочленов от нескольких переменных ${𝔽}_q[X]$, $X=(x_1,\cdots ,x_n)$ над полем Галуа ${𝔽}_q$. Пусть зафиксирован некоторый мономиальный порядок. Тогда приведение многочлена по модулю идеала определено однозначно. Пусть $I_1,I_2,\cdots ,I_t$ – нульмерные идеалы, а $s_1(X),s_2(X),\cdots ,s_t(X)\in {𝔽}_q[X]$ — некоторые многочлены. Тогда справедливо утверждение: система сравнений

$\{\begin{array}{cc}c(X)& \equiv s_1(X)mod{I}_1\\ c(X)& \equiv s_2(X)mod{I}_2\\ & ⋮\\ c(X)& \equiv s_t(X)mod{I}_t\end{array}$

либо несовместна, либо имеет единственное решение по модулю наименьшего общего кратного(НОК) идеалов $I_1,I_2,\cdots ,I_t$ . В случае, если идеалы попарно взаимно простые, т. е. $I_i+I_j=1,\mathrm{\forall }i\ne j$, имеем обобщенную китайскую теорему об остатках, причем решение системы всегда существует.

Рассмотрим сначала обобщение схемы Миньотта. Секретом будет некоторый многочлен $C(X)$ , участнику $i$ выдается модуль $I_i$ и частичный секрет $s_i(X)=C(X)mod{I}_i$ . Для реализации структуры доступа необходимо и достаточно, чтобы секрет $C(X)$ был приведенным по модулю НОК идеалов из любого разрешенного подмножества участников и не являлся таковым для запрещенных подмножеств.

В обобщенной схеме Асмута – Блума присутствует дополнительный модуль $I_0$ , а секретом является $s_i(X)=C(X)mod{I}_i$ . В этой схеме $C(X)$ называется промежуточным секретом.

Совершенность схемы

Схема разделения секрета называется совершенной, если запрещенное подмножество участников не получает никакой дополнительной информации о секрете, кроме априорной. Другими словами, распределение секрета остается равномерным и при наличии частичных секретов участников из запрещенного подмножества. Схема Асмута – Блума в отличие от схемы Миньотта может быть совершенной.

Для выработки критерия совершенности, исследуем схему Асмута – Блума в кольце ${𝔽}_q[X]$. Обозначим через $RT(I)$ множество мономов, приведенных по модулю $I$, а через $RP(I)$ – линейную оболочку $RT(I)$. Пусть также

$I^B=\text{HOK}[I_i,i\in B],M_2=\bigcap _{B\in \mathrm{\Gamma }}RT(I^B)$

– множество мономов, лежащих в пересечении $RT$ идеалов всех разрешенных подмножеств. Отметим, что промежуточный секрет $C(X)\in RP(M_2)$.

Теорема. Схема Асмута – Блума в кольце ${𝔽}_q[X]$ совершенна тогда и только тогда, когда выполнены следующие условия:

1) $I_0+I_i=1,\mathrm{\forall }i\in J$.

2) $\mathrm{\forall }A\notin \mathrm{\Gamma }:RT(I^A{I}_0)\subseteq M_2$.

Доказательство.

Необходимость. Пусть есть совершенная схема Асмута – Блума, но первое условие теоремы не выполнено, т. е. $\mathrm{\exists }{I}_i:I_i+I_0=D\ne 0$. Тогда множество возможных значений секрета для такого участника можно сузить: $c(X)\equiv s_i(X)modD$. Следовательно, схема несовершенна – получили противоречие.

Пусть первое условие выполнено, но не выполнено второе, т. е. существует запрещенное подмножество $A$ такое, что $RT(I^A{I}_0)\subset ̸M_2$. Иными словами, существует моном $m\in RT(I^A{I}_0)\mathrm{\setminus }{M}_2$. Рассмотрим многочлен

$g(X)=s^A(X)+(m-m({modI}^A))=s^A(X)+f_m(X),$

где $s^A(X)$ – общий частичный секрет, восстановленный участниками из подмножества $A$.

Заметим, что многочлен $f_m(X)$ тогда удовлетворяет следующим условиям:

1) $f_m(X)\in I^A$

2) $f_m(X)\in RP(I^A{I}_0)$

3) Содержит моном $m$.

Следовательно, $g(X)\in RP(I^A{I}_0)$. Положим $c^{\prime }=g(X)mod{I}_0$. Согласно китайской теореме об остатках, для системы

$\{\begin{array}{c}C(X)\equiv s^A(X)mod{I}^A\\ C(X)\equiv c^{\prime }(X)mod{I}_0\end{array}$

существует единственное решение в $RP(I^A{I}_0)$, но по построению этим решением является многочлен $g(X)$. С другой стороны, $m\in g(X)\notin RP(M_2)$, а значит, значение $c^{\prime }(X)$ для секрета невозможно – опять получили противоречие.

Достаточность. Пусть условия теоремы выполнены. Покажем, что секрет остается равномерно распределенным и при наличии частичных секретов из запрещенного подмножества. Рассмотрим произвольное запрещенное подмножество $A\notin \mathrm{\Gamma }$ и множество многочленов

$V=\{s^A(X)+f(X)|f(X)\in I^A,f(X)\in LP(M_2)\}$

— множество возможных значений промежуточного секрета.

Зафиксируем некоторое значение секрета $c^j(X)\in RP(I_0)$.Тогда существует единственный многочлен $g^j(X)\in LP(I^A{I}_0)$, такой, что согласно китайской теореме об остатках

$g^j(X)\equiv s^A(X)mod{I}^A$

$g^j(X)\equiv c^j(X)mod{I}_0$

Рассмотрим теперь 2 случая:

1) Если $RT(I^A{I}_0)=M_2$, то каждому значения секрета соответствует единственный промежуточный секрет из множества $V$, т.е. секрет остается равномерно распределенным при наличии частичных секретов из подмножества $A$.

2) Пусть тогда $RT(I^A{I}_0)\subset M_2$. Каждому многочлену $f(X)\in RP(M_2)$, содержащему хотя бы один моном из $M_2\setminus RT(I^A{I}_0)$, поставим в соответствие многочлен

$\bar{f}(X)=f(X)-f(X)modRT(I^A{I}_0)\ne 0$

Очевидно, что $\bar{f}(X)\in I^A{I}_0$. Тогда каждому значению секрета $c^j(X)\in RP(I_0)$ соответствует множество промежуточных секретов

$C^j=\{g^j(X),g^j(X)+\bar{f}(X)|\bar{f}(X)\in I^A{I}_0,\bar{f}(X)\in RP(M_2)\}\subset V$

Очевидно, что множества $C^j$ равномощные. Следовательно, в множестве $V$ для каждого значения секрета существует одинаковое число возможных значений промежуточного секрета, что влечет равномерное распределение секрета и при наличии частичных секретов из запрещенного подмножества.

Теорема доказана.

Литература

• Шаблон:Книга:Прикладная криптография
• Шаблон:Source
• Шаблон:Source
• Шаблон:Книга