Схема Асмута — Блума — пороговая схема разделения секрета , построенная с использованием простых чисел . Позволяет разделить секрет (число) между ${\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 .
• , (англ.) // / — IEEE , 1983. — Vol. 29, Iss. 2. — P. 208—210. — ISSN ; —
• // : материалы международного научного конгресса 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 .