WikiSort.ru - Не сортированное

Схема Асмута — Блума — пороговая схема разделения секрета, построенная с использованием простых чисел. Позволяет разделить секрет (число) между ${\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 \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 Trans. Inf. Theory / F. Kschischang — IEEE, 1983. — Vol. 29, Iss. 2. — P. 208–210. — ISSN 0018-9448 — doi:10.1109/TIT.1983.1056651
  <a href='https://wikidata.org/wiki/Track:Q16194641'></a><a href='https://wikidata.org/wiki/Track:Q27915587'></a><a href='https://wikidata.org/wiki/Track:Q27915585'></a><a href='https://wikidata.org/wiki/Track:Q127793'></a><a href='https://wikidata.org/wiki/Track:Q27915584'></a>
• Шенец Н. Н. Об идеальных модулярных схемах разделения секрета в кольцах многочленов от нескольких переменных // Международный конгресс по информатике: информационные системы и технологии: материалы международного научного конгресса 31 окт. — Минск: БГУ, 2011. — Т. 1. Статьи факультета прикладной математики и информатики. — С. 169–173. — ISBN 978-985-518-563-6
  <a href='https://wikidata.org/wiki/Track:Q27915595'></a><a href='https://wikidata.org/wiki/Track:Q2280'></a><a href='https://wikidata.org/wiki/Track:Q27915590'></a><a href='https://wikidata.org/wiki/Track:Q27915597'></a>
• Stinson, D. R. Cryptography: theory and practice. — Chapman and Hall/CRC, 2005. — P. 512. — ISBN 978-1584885085.