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

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

Описание

Пусть нужно разделить секрет $M$ между $n$ сторонами ($n \geq 2$) таким образом, чтобы любые $k$ сторон ($2 \leq k \leq n$) могли восстановить секрет, а любые $k-1$ этой возможности не имели. То есть нужно построить (k, n)-пороговую схему разделения секрета.

Построим последовательность натуральных чисел (назовём её (k,n)-последовательностью Миньотта) $d_1 < d_2 < \dots < d_n$ таким образом, что:

• любые два числа последовательности взаимно простые, т.е. $\forall i \neq j: \left(d_i, d_j\right) = 1$
• $d_1 * d_2 * \dots * d_m > d_{n-k+2} * \dots * d_n$

Теперь можно разделить секрет $M$, который должен находится в промежутке между $d_1 * d_2 * \dots * d_m$ и $d_{n-k+2} * \dots * d_n$ (от этого недостатка избавлена схема Схема Асмута — Блума).

Долями являются остатки от деления секрета $M$ на $d_1, d_2, \dots, d_n$.

Литература

• M. Mignotte How to Share a Secret (англ.) // Lecture Notes in Computer Science. — 1983. — Т. 149. — С. 371—375. — DOI:10.1007/3-540-39466-4_27