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

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

Описание

Пусть — некоторый секрет, который требуется разделить. Выбирается простое число , большее . Выбирается взаимно простых друг с другом чисел , таких что:

Выбирается случайное число и вычисляется

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

Участникам раздаются

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

Пример

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

В качестве простого числа выберем , в качестве взаимно простых — . Проверяем, что:

Выбираем случайное число и вычисляем:

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

Теперь попробуем восстановить исходный секрет, имея на руках доли , , . Составим систему уравнений:

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

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

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

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

Рассмотрим кольцо многочленов от нескольких переменных , над полем Галуа . Пусть зафиксирован некоторый мономиальный порядок. Тогда приведение многочлена по модулю идеала определено однозначно. Пусть – нульмерные идеалы, а — некоторые многочлены. Тогда справедливо утверждение: система сравнений

либо несовместна, либо имеет единственное решение по модулю наименьшего общего кратного(НОК) идеалов . В случае, если идеалы попарно взаимно простые, т. е. , имеем обобщенную китайскую теорему об остатках, причем решение системы всегда существует.

Рассмотрим сначала обобщение схемы Миньотта. Секретом будет некоторый многочлен , участнику выдается модуль и частичный секрет . Для реализации структуры доступа необходимо и достаточно, чтобы секрет был приведенным по модулю НОК идеалов из любого разрешенного подмножества участников и не являлся таковым для запрещенных подмножеств.

В обобщенной схеме Асмута – Блума присутствует дополнительный модуль , а секретом является . В этой схеме называется промежуточным секретом.

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

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

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

– множество мономов, лежащих в пересечении идеалов всех разрешенных подмножеств. Отметим, что промежуточный секрет .

Теорема. Схема Асмута – Блума в кольце совершенна тогда и только тогда, когда выполнены следующие условия:

1) .
2) .

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

Необходимость. Пусть есть совершенная схема Асмута – Блума, но первое условие теоремы не выполнено, т. е. . Тогда множество возможных значений секрета для такого участника можно сузить: . Следовательно, схема несовершенна – получили противоречие.

Пусть первое условие выполнено, но не выполнено второе, т. е. существует запрещенное подмножество такое, что . Иными словами, существует моном . Рассмотрим многочлен

где – общий частичный секрет, восстановленный участниками из подмножества .

Заметим, что многочлен тогда удовлетворяет следующим условиям:

1)
2)
3) Содержит моном .

Следовательно, . Положим . Согласно китайской теореме об остатках, для системы

существует единственное решение в , но по построению этим решением является многочлен . С другой стороны, , а значит, значение для секрета невозможно – опять получили противоречие.

Достаточность. Пусть условия теоремы выполнены. Покажем, что секрет остается равномерно распределенным и при наличии частичных секретов из запрещенного подмножества. Рассмотрим произвольное запрещенное подмножество и множество многочленов

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

Зафиксируем некоторое значение секрета .Тогда существует единственный многочлен , такой, что согласно китайской теореме об остатках

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

1) Если , то каждому значения секрета соответствует единственный промежуточный секрет из множества , т.е. секрет остается равномерно распределенным при наличии частичных секретов из подмножества .

2) Пусть тогда . Каждому многочлену , содержащему хотя бы один моном из , поставим в соответствие многочлен

Очевидно, что . Тогда каждому значению секрета соответствует множество промежуточных секретов

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

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

Литература

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.