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

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

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

• ${\displaystyle \forall i:d_{i}>p}$
• ${\displaystyle \forall i:d_{i}<d_{i+1}}$
• ${\displaystyle d_{1}*d_{2}*\dots d_{m}>p*d_{n-m+2}*d_{n-m+3}*\dots *d_{n}}$

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

${\displaystyle M'=M+rp}$

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

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

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

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

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

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

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

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

• ${\displaystyle d_{1}<d_{2}<d_{3}<d_{4}}$

  ${\displaystyle 11<13<17<19}$

• ${\displaystyle d_{1}*d_{2}*\dots d_{m}>p*d_{n-m+2}*d_{n-m+3}*\dots *d_{n}}$

  ${\displaystyle d_{1}*d_{2}*d_{3}>p*d_{3}*d_{4}}$

  ${\displaystyle 11*13*17>3*17*19}$

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

${\displaystyle M'=M+rp=2+51*3=155}$

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

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

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

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

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

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

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

${\displaystyle 1=M'\mod 11}$

${\displaystyle 12=M'\mod 13}$

${\displaystyle 2=M'\mod 17}$

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

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

${\displaystyle M\equiv M'\mod p}$

${\displaystyle M\equiv 155\mod 3\equiv 2}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle g(X)=s^{A}(X)+(m-m({\bmod {I}}^{A}))=s^{A}(X)+f_{m}(X),}$

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

Заметим, что многочлен ${\displaystyle f_{m}(X)}$ тогда удовлетворяет следующим условиям:

1) ${\displaystyle f_{m}(X)\in I^{A}}$

2) ${\displaystyle f_{m}(X)\in RP(I^{A}I_{0})}$

3) Содержит моном ${\displaystyle m}$.

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

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

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

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

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

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

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

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

${\displaystyle g^{j}(X)\equiv c^{j}(X)\ {\bmod {\ }}I_{0}}$

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

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

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

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

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

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

Очевидно, что множества ${\displaystyle C^{j}}$ равномощные. Следовательно, в множестве ${\displaystyle 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.