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

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

Описание

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

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

Выбирается случайное число <math>r</math> и вычисляется

<math>M' = M + r p </math>

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

<math>k_i = M' \mod d_i</math>

Участникам раздаются <math>\left\{p, d_i, k_i\right\}</math>

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

Пример

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

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

• <math>\forall i:d_i > p</math>

  <math>\forall i: i \in \{11, 13, 17, 19\}, i > p = 3</math>

• <math>d_1 < d_2 < d_3 < d_4</math>

  <math>11 < 13 < 17 < 19</math>

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

  <math>d_1 * d_2 * d_3 > p * d_3 * d_4</math>

  <math>11 * 13 * 17 > 3 * 17 * 19</math>

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

<math>M' = M + r p = 2 + 51 * 3 = 155</math>

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

<math>k_i = M' \mod d_i</math>

<math>k_1 = 155 \mod 11 = 1</math>

<math>k_2 = 155 \mod 13 = 12</math>

<math>k_3 = 155 \mod 17 = 2</math>

<math>k_4 = 155 \mod 19 = 3</math>

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

<math>1 = M' \mod 11</math>

<math>12 = M' \mod 13</math>

<math> 2 = M' \mod 17</math>

Мы можем восстановить <math>M'</math>, используя китайскую теорему об остатках.

Зная <math>M'</math>, мы восстанавливаем секрет.

<math>M \equiv M' \mod p</math>

<math>M \equiv 155 \mod 3 \equiv 2 </math>

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

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

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

<math>\begin{cases}

c (X) & \equiv s_1 (X) \ \bmod \ I_1 \\ c (X) & \equiv s_2 (X) \ \bmod \ I_2 \\ & \vdots \\ c (X) & \equiv s_t (X) \ \bmod \ I_t \\ \end{cases}</math>

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

Рассмотрим сначала обобщение схемы Миньотта. Секретом будет некоторый многочлен <math>C(X)</math> , участнику <math>i</math> выдается модуль <math>I_i</math> и частичный секрет <math>s_i (X) = C (X)\ \bmod \ I_i</math> . Для реализации структуры доступа необходимо и достаточно, чтобы секрет <math>C(X)</math> был приведенным по модулю НОК идеалов из любого разрешенного подмножества участников и не являлся таковым для запрещенных подмножеств.

В обобщенной схеме Асмута – Блума присутствует дополнительный модуль <math>I_0</math> , а секретом является <math>s_i (X) = C (X)\ \bmod \ I_i</math> . В этой схеме <math>C(X)</math> называется промежуточным секретом.

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

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

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

<math>I^B=\mbox{HOK}[I_i,i\in B], \ M_2=\bigcap_{B\in \Gamma}RT(I^B)</math>

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

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

1) <math>I_0 + I_i =1, \forall i \in J</math>.

2) <math>\forall A \notin \Gamma :RT(I^A I_0) \subseteq M_2</math>.

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

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

Пусть первое условие выполнено, но не выполнено второе, т. е. существует запрещенное подмножество <math>A</math> такое, что <math>RT(I^A I_0) \not\subset M_2</math>. Иными словами, существует моном <math>m\in RT(I^A I_0)\backslash M_2</math>. Рассмотрим многочлен

<math>g(X)=s^A(X)+(m-m(\bmod I^A))=s^A(X)+f_m(X),</math>

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

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

1) <math>f_m(X) \in I^A</math>

2) <math>f_m(X) \in RP(I^A I_0)</math>

3) Содержит моном <math>m</math>.

Следовательно, <math>g(X) \in RP(I^A I_0)</math>. Положим <math>c'=g(X) \ \bmod \ I_0</math>. Согласно китайской теореме об остатках, для системы

<math>\begin{cases}

C (X) \equiv s^A (X) \ \bmod \ I^A \\ C (X) \equiv c' (X) \ \bmod \ I_0 \\ \end{cases}</math>

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

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

<math>V= \{ s^A(X)+f(X)|f(X) \in I^A, f(X) \in LP(M_2) \} </math>

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

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

<math>g^j(X) \equiv s^A(X) \ \bmod \ I^A</math>

<math>g^j(X) \equiv c^j(X) \ \bmod \ I_0</math>

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

1) Если <math>RT(I^A I_0)=M_2</math>, то каждому значения секрета соответствует единственный промежуточный секрет из множества <math>V</math>, т.е. секрет остается равномерно распределенным при наличии частичных секретов из подмножества <math>A</math>.

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

<math>\overline{f}(X) = f(X) - f(X)\ \bmod \ RT(I^A I_0) \ne 0</math>

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

<math>C^j=\{g^j(X),g^j(X)+\overline{f}(X)|\overline{f}(X) \in I^A I_0,\overline{f}(X) \in RP(M_2)\} \subset V</math>

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

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

Литература

• Шнайер Б. Схема Асмута-Блума // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — С. 589—590. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.
• C. Asmuth, J. Bloom A modular approach to key safeguarding // Information Theory, IEEE Transactions on. — 1983. — Т. 29, вып. 2. — ISSN [www.sigla.ru/table.jsp?f=8&t=3&v0=0018-9448&f=1003&t=1&v1=&f=4&t=2&v2=&f=21&t=3&v3=&f=1016&t=3&v4=&f=1016&t=3&v5=&bf=4&b=&d=0&ys=&ye=&lng=&ft=&mt=&dt=&vol=&pt=&iss=&ps=&pe=&tr=&tro=&cc=UNION&i=1&v=tagged&s=0&ss=0&st=0&i18n=ru&rlf=&psz=20&bs=20&ce=hJfuypee8JzzufeGmImYYIpZKRJeeOeeWGJIZRrRRrdmtdeee88NJJJJpeeefTJ3peKJJ3UWWPtzzzzzzzzzzzzzzzzzbzzvzzpy5zzjzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzztzzzzzzzbzzzzzzzzzzzzzzzzzzzzzzzzzzzvzzzzzzyeyTjkDnyHzTuueKZePz9decyzzLzzzL*.c8.NzrGJJvufeeeeeJheeyzjeeeeJh*peeeeKJJJJJJJJJJmjHvOJJJJJJJJJfeeeieeeeSJJJJJSJJJ3TeIJJJJ3..E.UEAcyhxD.eeeeeuzzzLJJJJ5.e8JJJheeeeeeeeeeeeyeeK3JJJJJJJJ*s7defeeeeeeeeeeeeeeeeeeeeeeeeeSJJJJJJJJZIJJzzz1..6LJJJJJJtJJZ4....EK*&debug=false 0018-9448].
• Шенец, Н. Н. [elib.bsu.by/handle/123456789/9565 Об идеальных модулярных схемах разделения секрета в кольцах многочленов от нескольких переменных] // БГУ. — 2011. — ISBN 978-985-518-563-6.
• Stinson, D. R. Cryptography: theory and practice. — Chapman and Hall/CRC, 2005. — P. 512. — ISBN 978-1584885085.