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

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

Описание

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

• $\forall i:d_{i}>p$
• $\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'=M+rp$

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

$k_{i}=M'\mod d_{i}$

Участникам раздаются $\left\{p,d_{i},k_{i}\right\}$

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

Пример

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

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

• $\forall i:d_{i}>p$

  $\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'=M+rp=2+51*3=155$

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

$k_{i}=M'\mod d_{i}$

$k_{1}=155\mod 11=1$

$k_{2}=155\mod 13=12$

$k_{3}=155\mod 17=2$

$k_{4}=155\mod 19=3$

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

$1=M'\mod 11$

$12=M'\mod 13$

$2=M'\mod 17$

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

Зная $M'$, мы восстанавливаем секрет.

$M\equiv M'\mod p$

$M\equiv 155\mod 3\equiv 2$

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

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

Рассмотрим кольцо многочленов от нескольких переменных $\mathbb {F} _{q}[X]$, $X=(x_{1},\cdots ,x_{n})$ над полем Галуа $\mathbb {F} _{q}$. Пусть зафиксирован некоторый мономиальный порядок. Тогда приведение многочлена по модулю идеала определено однозначно. Пусть $I_{1},I_{2},\cdots ,I_{t}$ – нульмерные идеалы, а $s_{1}(X),s_{2}(X),\cdots ,s_{t}(X)\in \mathbb {F} _{q}[X]$ — некоторые многочлены. Тогда справедливо утверждение: система сравнений

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

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

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

В обобщенной схеме Асмута – Блума присутствует дополнительный модуль $I_{0}$ , а секретом является $s_{i}(X)=C(X)\ {\bmod {\ }}I_{i}$ . В этой схеме $C(X)$ называется промежуточным секретом.

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

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

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

$I^{B}={\mbox{HOK}}[I_{i},i\in B],\ M_{2}=\bigcap _{B\in \Gamma }RT(I^{B})$

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

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

1) $I_{0}+I_{i}=1,\forall i\in J$.

2) $\forall A\notin \Gamma :RT(I^{A}I_{0})\subseteq M_{2}$.

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

Необходимость. Пусть есть совершенная схема Асмута – Блума, но первое условие теоремы не выполнено, т. е. $\exists I_{i}:I_{i}+I_{0}=D\neq 0$. Тогда множество возможных значений секрета для такого участника можно сузить: $c(X)\equiv s_{i}(X)\ {\bmod {\ }}D$. Следовательно, схема несовершенна – получили противоречие.

Пусть первое условие выполнено, но не выполнено второе, т. е. существует запрещенное подмножество $A$ такое, что $RT(I^{A}I_{0})\not \subset M_{2}$. Иными словами, существует моном $m\in RT(I^{A}I_{0})\backslash M_{2}$. Рассмотрим многочлен

$g(X)=s^{A}(X)+(m-m({\bmod {I}}^{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'=g(X)\ {\bmod {\ }}I_{0}$. Согласно китайской теореме об остатках, для системы

${\begin{cases}C(X)\equiv s^{A}(X)\ {\bmod {\ }}I^{A}\\C(X)\equiv c'(X)\ {\bmod {\ }}I_{0}\\\end{cases}}$

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

Достаточность. Пусть условия теоремы выполнены. Покажем, что секрет остается равномерно распределенным и при наличии частичных секретов из запрещенного подмножества. Рассмотрим произвольное запрещенное подмножество $A\notin \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)\ {\bmod {\ }}I^{A}$

$g^{j}(X)\equiv c^{j}(X)\ {\bmod {\ }}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})$, поставим в соответствие многочлен

${\overline {f}}(X)=f(X)-f(X)\ {\bmod {\ }}RT(I^{A}I_{0})\neq 0$

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

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

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

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

Литература

• Шнайер Б. Схема Асмута-Блума // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — С. 589—590. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.
• Asmuth C., Bloom J. A modular approach to key safeguarding (англ.) // IEEE Transactions on Information Theory / F. Kschischang — IEEE, 1983. — Vol. 29, Iss. 2. — P. 208—210. — ISSN 0018-9448; 1557-9654 — doi:10.1109/TIT.1983.1056651
• Шенец Н. Н. Об идеальных модулярных схемах разделения секрета в кольцах многочленов от нескольких переменных // Международный конгресс по информатике: информационные системы и технологии: материалы международного научного конгресса 31 окт. — Минск: БГУ, 2011. — Т. 1. Статьи факультета прикладной математики и информатики. — С. 169—173. — ISBN 978-985-518-563-6
• Stinson, D. R. Cryptography: theory and practice. — Chapman and Hall/CRC, 2005. — P. 512. — ISBN 978-1584885085.