Схема Миньотта

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

История[править | править вики-текст]

Впервые схема была предложена в 1982 году французским учёным Морисом Миньоттом в качестве одного из вариантов использования -пороговой схемы, описанной Ади Шамиром. Сам Шамир предлагал решение с применением интерполяции полинома на конечном поле, где секретом являлся сам полином. Миньотт же смог предоставить более простое решение, заложив в основу модулярный подход - секретом является некоторое число, а частичным секретом - его вычет по некоторому модулю. Доработанной схемой Миньотта является схема Асмута-Блума. В обеих схемах для восстановления секрета используется китайская теорема об остатках, формулировка которой определяет единственное решение (секрет)[1].

Схема разделения секрета[править | править вики-текст]

Китайская теорема об остатках[править | править вики-текст]

В основе схемы лежит использование китайской теоремы об остатках, которая позволяет пользователям, имеющим некоторую долю секрета, восстановить сам секрет, причём единственным образом. Существует несколько версий теоремы, назовём следующую общей: Пусть . Тогда система уравнений

имеет решения в тогда и только тогда, когда . Более того, если приведенная система имеет решения в , она имеет единственное решение в определяет наименьшее общее кратное . В случае, если , китайскую теорему об остатках называют стандартной[2].

Пороговые схемы разделения секрета[править | править вики-текст]

Допустим, имеется n пользователей, пронумерованных от до , и набор групп, где - все подгруппы группы . Фактически, -схема разделения секрета – это метод генерации секретов таких, что:

  • (корректность) Для любого , проблема нахождения при наличии всех «простая»
  • (безопасность) Для любого , проблема нахождения является «труднообрабатываемой»

будем называть структурой доступа, – секретом, а – тенями . Наборы элементов изназовём группами авторизации. В идеальной схеме разделения секрета тени любой группы, не являющейся группой авторизации, не даёт информации (с точки зрения теории информации) о секрете. Доказано, что в любой идеальной схеме разделения секрета размер каждой из теней должен быть не меньше размера самого секрета. Естественным является условие о том, что структура доступа должна быть монотонной, то есть: . Любая структура доступа хорошо описывается с помощью минимального набора групп авторизации: . Можно описать и структуру доступа, не обладающую свойствами авторизации: . Её хорошо описывает максимальный набор групп "неавторизации":

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

Стоит учесть также, что для -пороговых структур доступа.:

.

Все -схемы разделения секрета также назовём -пороговыми схемами разделения секрета[1].

Последовательность Миньотта[править | править вики-текст]

Пороговая схема разделения секрета Миньотта использует специальные последовательности чисел, названные последовательностями Миньотта. Пусть – целое, , и . -последовательность Миньотта – последовательность взаимно простых положительных таких, что Последнее утверждение также равносильно следующему: [1]

Алгоритм[править | править вики-текст]

Имея открытый ключ-последовательность Миньотта, схема работает так:

  1. Секрет выбирается, как случайное число такое, что , где . Другими словами, секрет должен находиться в промежутке между и
  2. Доли вычисляются, как , для всех
  3. Имея различных теней , можно получить секрет , используя стандартный вариант китайской теоремы об остатках – им будет единственное решение по модулю системы:

Секретом является решение приведенной выше системы, более того, лежит в пределах , т.к. . С другой стороны, имея всего различных теней , можно сказать, что , где – единственное решение по модулю исходной системы (в данном случае: .[1] Для того, чтобы получить приемлемый уровень безопасности, должны быть использованы последовательности Миньотта с большим значением [3] Очевидно, что схема Миньотта не обладает значительной криптографической стойкостью, однако может оказаться удобной в приложениях, где компактность теней является решающим фактором.

Пример[править | править вики-текст]

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

  • Выбираем последовательность Миньотта .
  • Вычисляем для данной последовательности , .
  • Выбираем такое, что , например, .
  • Вычисляем доли: :
  • Для восстановления секрета решим систему уравнений для теней (предположим, секрет восстанавливают участники 1-5):

.

Из формулировки китайской теоремы об остатках знаем, что решение будет единственным.

Модификации схемы Миньотта[править | править вики-текст]

Обобщённая последовательность Миньотта[править | править вики-текст]

Для данной пороговой схемы элементы последовательности не обязательно являются взаимно простыми. Пусть – целое, . Обобщённой -последовательностью Миньотта называют такую последовательность положительных целых чисел, что . Нетрудно видеть, что любая -последовательность Миньотта является обобщённой -последовательностью Миньотта. Более того, если умножить каждый элемент обобщённой последовательности на фиксированный элемент , также получим обобщённую -последовательность Миньотта. Расширенная схема Миньотта работает так же, как и обыкновенная для и .В данном случае для нахождения секрета необходимо использовать обобщённый вариант китайской теоремы об остатках.[4]

Взвешенное разделение секрета[править | править вики-текст]

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

Пусть - секрет, где - веса теней пользователей. Сгенерируем -последовательность Миньотта, где . Тогда , где - произвольное разбиение множества такое, что

Можно заметить, что существует однозначное соответствие между размером и весом тени: например, бит — это тень весом 1, тень весом будет весить битов. Реализация схемы Миньотта со взвешенным разделением секрета не является целесообразной, так как генерация последовательности Миньотта и взвешенной пороговой структуры доступа является трудо- и ресурсоемкой задачей. Существуют более простые и эффективные схемы со взвешенным разделением секрета, в которых также устранена зависимость между весом и размером тени.[5]

Аналогичные схемы[править | править вики-текст]

  • Схема Асмута-Блума[6], также основанная на китайской теореме об остатках, была впервые представлена в 1983 году. Основное отличие состоит в том, что вместо последовательности Миньотта, требующей генерации, необходимо выбрать простое число, связанную с ним последовательность из взаимно простых чисел, а также некоторое случайное число, с помощью которого шифруется секрет, и уже на основе зашифрованного секрета вычисляются тени. В схема Асмута-Блума отсутствуют некоторые недостатки, присущие схеме Миньотта:
  1. Нет ограничения на область, в которой можно выбирать секрет
  2. Набор из менее, чем теней пользователей не даёт никакой информации о секрете
  1. Предполагаем, что раскрытый вес равен , а -длина используемых чисел в битах. Также полагаем, что . Стоит отметить, что в реальных схемах .
  2. Секрет в таком случае выберем длиной битов (если он меньше, дополним его, например, путём повторения битов секрета или добавления случайных битов).
  3. Для пользователя , обладающего весом его доли , выберем простое число длиной битов и такое, что . Простые числа выбраны в данном случае для упрощения работы алгоритма, для корректной работы схемы достаточно выбора попарно взаимно простых чисел.
  4. Вычислим и определим долю пользователя , как .
  5. При восстановлении секрета любой коллектив пользователей такой, что может составить систему уравнений:

и вычислить S, применив китайскую теорему об остатках. Так как размер составляет битов, размер произведения модулей состоит из, по меньшей мере, , можно видеть, что , пока . Именно это позволяет вычислить секрет единственным образом. Можно ослабить условие на сумму весов долей до , тогда в случае длина составляет, как минимум, , поэтому необходимо ограничить до битов. Если же это невозможно, можно сохранить работоспособность схемы, введя дополнительный элемент, модуль которого - наименьшее простое число из битов, доля элемента - . Этот элемент можно использовать, как дополнительное уравнение в приведенной выше системе, в таком случае , поэтому секрет можно будет восстановить единственным образом. В данной схеме устранён один из главных недостатков обыкновенной схемы с разделением взвешенного секрета - любую долю можно описать точкой , причём эта точка не обладает зависимостью между собственным весом и размером.


Данную схему можно также изменить для работы с несколькими секретами. Допустим, необходимо разделить секреты , каждый секрет состоит из битов. Сложим секреты вместе, получив один секрет длиной битов. Необходимо рассмотреть три случая:

  1. : Добавим случайных битов, до размера
  2. : Ничего не делаем
  3. : Введём дополнительный элемент с весом [5]

Производительность схемы[править | править вики-текст]

График производительности классической и доработанной схем Миньотта с долями равного веса.
График производительности для долей разного веса.

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

  • Генерация последовательности Миньотта состоит из нескольких этапов:
  1. Генерация попарно взаимно простых . Преобладающей операцией является нахождение НОК, сложность её составляет . Для каждого нового сгенерированного числа необходимо проверить, является ли оно попарно взаимно простым с каждый из предыдущих элементов, поэтому для генерации попарно взаимно простых чисел сложность составляет .
  2. Их сортировка, её сложность составляет .
  3. Проверка условия . Сложность перемножения двух чисел длиной битов и битов составляет . Сложность проверки составит .

Таким образом, общая сложность генерации последовательности Миньотта составляет .

  • Для генерации модуля пользователю с весом необходимо перемножить чисел размера . Сложность генерации модулей составит . Таким образом, общая сложность генерации модулей также составляет .

Схема не обладает хорошей производительностью, так как возможно модифицировать её и тем самым избавиться от необходимости генерации последовательностей Миньотта. На графиках приведены результаты анализа производительности схемы, основанной на схеме Миньотта со взвешенном разделением секрета и самой схемы. Для построения графика была выбрана -пороговая схема с одним секретом, и соответственно[5].

Недостатки схемы[править | править вики-текст]

  • Не обладает криптографической стойкостью, так как даже неполное множество пользователей может предоставить некоторую информацию о секрет.
  • Не является простой в принципиальном плане или при реализации. Генерация последовательностей Миньотта и пороговых структур доступа является трудным и ресурсоемким процессом.
  • Существует ограничение на область значений, в которой можно выбирать секрет: должен находится в промежутке между и . Знание этого факта также даёт дополнительную информацию злоумышленнику.
  • Для обеспечение хорошей криптостойкости необходима генерация больших значений , что также является ресурсоемкой задачей.
  • Злоумышленник может обмануть пользователей схемы, подменив секрет.

Схемы поведения злоумышленников[править | править вики-текст]

выбор
выбор
выбор

Можно выделить две схемы, описывающих поведение злоумышленников в пороговых схемах: модель CDV, в которой злоумышленники знают секрет и пытаются передать другим участникам ложные данные, и модель OKS, в которой злоумышленники не знают секрета заранее. В обыкновенной схеме Миньотта один злоумышленник всегда может обмануть пользователей в модели CDV и с большой вероятностью - в модели OKS. Допустим, участники разделили секрет, и пользователь решает сжульничать. Следовательно, он должен изменить свою тень на так, чтобы . Пусть . Используя китайскую теорему об остатках, получим , то есть, представим в виде . Так как последовательность Миньотта известна, можно найти . Можно выбрать , откуда

В модели CDV злоумышленник знает секрет, поэтому используя выражение он может удостовериться в том, что (рис.1), существование гарантировано, если участников не могут определить секрет. Следовательно, злоумышленник может обмануть участников схемы с вероятностью 1. Более того, в этой модели злоумышленник может контролировать значение , вычисляя напрямую из : , где

В модели OKS, так как злоумышленник не знает секрет, он не может проверить истинность неравенств и . В таком случае он всегда может использовать . Единственный вариант, при котором обман может быть раскрыт - , откуда (рис.2) или (рис.3). Следовательно, вероятность успешного обмана составляет [7]

Пример[править | править вики-текст]

Пусть . Тогда для секрета будут сгенерированы тени . Допустим, участники 1,2,3 объединили свои доли, и участник 1 хочет сжульничать. Тогда он вычисляет и изменяет свою долю так, что . В таком случае, после решения системы уравнений участники восстановят неверный секрет , также находящийся между и . При этом пользователь 1 может получить настоящий секрет: [7]

Модификация схемы[править | править вики-текст]

Для того, чтобы избежать подобных махинаций, можно сделать следующее:

  • Вводится дилер, генерирующий -последовательность Миньотта . Также дилер генерирует различных простых таких, что: является достаточно большим. Секрет выбирается так, что . Долями являются . Процесс восстановления секрета проходит так же, как и в стандартной схеме Миньотта. После того, как секрет восстановлен, любой участник может определить обман путём сравнения с данными, переданными дилером. Таким образом, злоумышленник может обмануть участника с вероятностью [7]

Примечания[править | править вики-текст]

  1. 1 2 3 4 Maurice Mignotte, 1983, pp.371-375
  2. General Secret Sharing Based on the Chinese Remainder Theorem (англ.). Electronic Notes in Theoretical Computer Science (2007). Проверено 18 ноября 2013.
  3. Evangelos Kranakis, 1986, p. 9
  4. A generalization of Mignotte’s secret sharing scheme (англ.). Proceedings of the 6th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (2004). Проверено 12 декабря 2013.
  5. 1 2 3 A New Approach to Weighted Multi-Secret Sharing (англ.). Electronic Notes in Theoretical Computer Science (2011). Проверено 18 ноября 2013.

  6. C. A. Asmuth and J. Bloom, 1986, pp. 208-210
  7. 1 2 3 Cheating Detection and Cheater Identification in CRT-based Secret Sharing Schemes (англ.). “Al. I. Cuza” University Iasi, Romania (2009). Проверено 18 ноября 2013.

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]