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

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

История

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

Схема разделения секрета

Китайская теорема об остатках

Основная статья: Китайская теорема об остатках

В основе схемы лежит использование китайской теоремы об остатках, которая позволяет пользователям, имеющим некоторую долю секрета, восстановить сам секрет, причём единственным образом. Существует несколько версий теоремы, назовём следующую общей: Пусть $k\geqslant 2,m_{1},\dots ,m_{k}\geqslant 2,b_{1},\dots ,b_{k}\in \mathbb {Z}$. Тогда система уравнений

${\begin{cases}x\equiv b_{1}\mod m_{1}\\\vdots \\x\equiv b_{k}\mod m_{k}\end{cases}}$ имеет решения в $\mathbb {Z}$ тогда и только тогда, когда $b_{i}\equiv b_{j}\mod (m_{i},m_{j})\forall 1\leqslant i,j\leqslant k$. Более того, если приведенная система имеет решения в $\mathbb {Z}$, она имеет единственное решение в $\mathbb {Z} _{[m_{1},\dots ,m_{k}]},[m_{1},\dots ,m_{k}]$ определяет наименьшее общее кратное $m_{1},\dots ,m_{k}$. В случае, если $(m_{i},m_{j})=1\forall 1\leqslant i<j\leqslant k$, китайскую теорему об остатках называют стандартной.

Пороговые схемы разделения секрета

Допустим, имеется n пользователей, пронумерованных от $1$ до $n$, и набор групп${\mathcal {A}}\subseteq P({1,2,\dots ,n})$, где $P({1,2,\dots ,n})$ - все подгруппы группы $\{1,2,\dots ,n\}$. Фактически, ${\mathcal {A}}$-схема разделения секрета – это метод генерации секретов $(S,(I_{1},\dots ,I_{n}))$ таких, что:

• (корректность) Для любого $A\in {\mathcal {A}}$, проблема нахождения $S$ при наличии всех $I$ «простая»
• (безопасность) Для любого $A\in P({1,2,\dots ,n})\setminus {\mathcal {A}}$, проблема нахождения $S$ является «труднообрабатываемой»

${\mathcal {A}}$ будем называть структурой доступа, $S$ – секретом, а $I_{1},\dots ,I_{n}$ – тенями $S$. Наборы элементов из$A$назовём группами авторизации. В идеальной схеме разделения секрета тени любой группы, не являющейся группой авторизации, не даёт информации (с точки зрения теории информации) о секрете. Доказано, что в любой идеальной схеме разделения секрета размер каждой из теней должен быть не меньше размера самого секрета. Естественным является условие о том, что структура доступа ${\mathcal {A}}$ должна быть монотонной, то есть: $(\forall B\in P(\{1,2,\dots ,n\}))((\exists A\in {\mathcal {A}})(A\subseteq B)\Rightarrow B\in {\mathcal {A}})$. Любая структура доступа ${\mathcal {A}}$ хорошо описывается с помощью минимального набора групп авторизации: ${\mathcal {A}}_{min}=\{A\in {\mathcal {A}}\mid (\forall B\in {\mathcal {A}}\setminus \{A\})(\neg B\subseteq A)\}$. Можно описать и структуру доступа, не обладающую свойствами авторизации: ${\bar {\mathcal {A}}}=P(\{1,2,\dots ,n\})\setminus {\mathcal {A}}$. Её хорошо описывает максимальный набор групп "неавторизации":${\bar {\mathcal {A}}}_{max}=\{A\in {\bar {\mathcal {A}}}\mid (\forall B\in {\bar {\mathcal {A}}}\setminus \{A\})(\neg A\subseteq B)\}$

В первых схемах разделения секрета только количество участников являлось важным при восстановлении секрета. Такие схемы были названы пороговыми схемами разделения секрета. Пусть $n\geqslant 2,2\leqslant k\leqslant n$, тогда структура доступа ${\mathcal {A}}=\{A\in P({1,2,\dots ,n})\mid |A|\geqslant k\}$ называется $(k,n)$-пороговой структурой доступа.

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

${\bar {\mathcal {A}}}=\{A\in P(\{1,2,\dots ,n\})\mid |A|\leqslant k-1\}$

${\mathcal {A}}_{min}=\{A\in P(\{1,2,\dots ,n\})\mid |A|=k\}$

${\bar {\mathcal {A}}}_{max}=\{A\in P(\{1,2,\dots ,n\})\mid |A|=k-1\}$.

Все $A$-схемы разделения секрета также назовём $(k,n)$-пороговыми схемами разделения секрета.

Последовательность Миньотта

Пороговая схема разделения секрета Миньотта использует специальные последовательности чисел, названные последовательностями Миньотта. Пусть $n$ – целое, $n\geqslant 2$, и $2\leqslant k\leqslant n$. $(k,n)$-последовательность Миньотта – последовательность взаимно простых положительных $p_{1}<p_{2}<\dots <p_{n}$ таких, что $\prod _{i=0}^{k-2}p_{n-i}<\prod _{i=1}^{k}p_{i}$ Последнее утверждение также равносильно следующему: $\max _{1\leqslant i_{1}<\dots <i_{k-1}\leqslant n}(p_{i_{1}}\dots p_{i_{k-1}})<\min _{1\leqslant i_{1}<\dots <i_{k}\leqslant n}(p_{i_{1}}\dots p_{i_{k}})$

Алгоритм

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

1. Секрет $S$ выбирается, как случайное число такое, что $\beta <S<\alpha$, где $\alpha =\prod _{i=1}^{k}p_{i},\beta =\prod _{i=0}^{k-2}p_{n-i}$. Другими словами, секрет должен находиться в промежутке между $p_{1}*p_{2}*\dots *p_{k}$ и $p_{n-k+2}*\dots *p_{n}$
2. Доли вычисляются, как $I_{i}=S\mod p_{i}$, для всех $1\leqslant i\leqslant n$
3. Имея $k$ различных теней $I_{i_{1}},\dots ,I_{i_{k}}$, можно получить секрет $S$, используя стандартный вариант китайской теоремы об остатках – им будет единственное решение по модулю $p_{i_{1}}\dots p_{i_{k}}$ системы:

${\begin{cases}x\equiv I_{i_{1}}\mod p_{i_{1}}\\\vdots \\x\equiv I_{i_{k}}\mod p_{i_{k}}\end{cases}}$ Секретом является решение приведенной выше системы, более того, $S$ лежит в пределах $Z_{{p_{i_{1}}},\dots ,p_{i_{k}}}$, т.к. $S<\alpha$. С другой стороны, имея всего $k-1$ различных теней $I_{i_{1}},\dots ,I_{i_{k-1}}$, можно сказать, что $S\equiv x_{0}\mod p_{i_{1}}\dots p_{i_{k-1}}$, где $x_{0}$ – единственное решение по модулю $p_{i_{1}}\dots p_{i_{k-1}}$ исходной системы (в данном случае: $S>\beta \geqslant p_{i_{1}}\dots p_{i_{k-1}}>x_{0}$. Для того, чтобы получить приемлемый уровень безопасности, должны быть использованы $(k,n)$ последовательности Миньотта с большим значением ${\dfrac {\alpha -\beta }{\beta }}$ Очевидно, что схема Миньотта не обладает значительной криптографической стойкостью, однако может оказаться удобной в приложениях, где компактность теней является решающим фактором.

Пример

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

• Выбираем последовательность Миньотта $p_{1}=5,p_{2}=7,p_{3}=11,p_{4}=13,p_{5}=17,p_{6}=19$.
• Вычисляем для данной последовательности $\alpha =p_{1}*p_{2}*p_{3}*p_{4}*p_{5}=85085$, $\beta =p_{3}*p_{4}*p_{5}*p_{6}=46189$.
• Выбираем $S$ такое, что $\beta <S<\alpha$, например, $S=50000$.
• Вычисляем доли: $I_{i}=S\mod p_{i}$: $I_{1}=50000\mod 5=0,I_{2}=50000\mod 7=6,I_{3}=50000\mod 11=5,I_{4}=50000\mod 13=2,I_{5}=50000\mod 17=3,I_{6}=50000\mod 19=11$
• Для восстановления секрета решим систему уравнений для $k$ теней (предположим, секрет восстанавливают участники 1-5):

${\begin{cases}x\equiv 0\mod 5\\x\equiv 6\mod 7\\x\equiv 5\mod 11\\x\equiv 2\mod 13\\x\equiv 3\mod 17\end{cases}}$.

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

Модификации схемы Миньотта

Обобщённая последовательность Миньотта

Для данной пороговой схемы элементы последовательности не обязательно являются взаимно простыми. Пусть $n$ – целое, $n\geqslant 2,2\leqslant k\leqslant n$. Обобщённой $(k,n)$-последовательностью Миньотта называют такую последовательность $p_{1},\dots ,p_{n}$ положительных целых чисел, что $\max _{1\leqslant i_{1}<\dots <i_{k-1}\leqslant n}([p_{i_{1}},\dots ,p_{i_{k-1}}])<\min _{1\leqslant i_{1}<\dots <i_{k}\leqslant n}([p_{i_{1}},\dots ,p_{i_{k}}])$. Нетрудно видеть, что любая $(k,n)$-последовательность Миньотта является обобщённой $(k,n)$-последовательностью Миньотта. Более того, если умножить каждый элемент обобщённой последовательности на фиксированный элемент $\delta \in Z,(\delta ,p_{1},\dots ,p_{n})=1$, также получим обобщённую $(k,n)$-последовательность Миньотта. Расширенная схема Миньотта работает так же, как и обыкновенная для $\alpha =\min _{1\leqslant i_{1}<\dots <i_{k}\leqslant n}([p_{i_{1}},\dots ,p_{i_{k}}])$ и $\beta =\max _{1\leqslant i_{1}<\dots <i_{k-1}\leqslant n}([p_{i_{1}},\dots ,p_{i_{k-1}}])$.В данном случае для нахождения секрета необходимо использовать обобщённый вариант китайской теоремы об остатках.

Взвешенное разделение секрета

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

Пусть $S(k,n,N,P)$ - секрет, где $P=(p_{1},\dots ,p_{N})$ - веса теней пользователей. Сгенерируем $(k,W)$-последовательность Миньотта, где $W=\sum _{i=1}^{n}p_{i}$. Тогда $P_{i}=[\{P_{j}^{\prime }\mid j\in P_{a_{j}}\}]\forall 1\leqslant i\leqslant N$, где $P_{a_{1}},\dots ,P_{a_{N}}$ - произвольное разбиение множества $\{1,2,\dots ,W\}$ такое, что $|P_{a_{i}}|=p_{i}\forall 1\leqslant i\leqslant N$

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

Аналогичные схемы

• Схема Асмута-Блума, также основанная на китайской теореме об остатках, была впервые представлена в 1983 году. Основное отличие состоит в том, что вместо последовательности Миньотта, требующей генерации, необходимо выбрать простое число, связанную с ним последовательность из $n$ взаимно простых чисел, а также некоторое случайное число, с помощью которого шифруется секрет, и уже на основе зашифрованного секрета вычисляются тени. В схема Асмута-Блума отсутствуют некоторые недостатки, присущие схеме Миньотта:

1. Нет ограничения на область, в которой можно выбирать секрет
2. Набор из менее, чем $k$ теней пользователей не даёт никакой информации о секрете

• Существует несколько схем с разделением взвешенного секрета, основанных на схеме Миньотта. В качестве примера приведём схему, опубликованную в совместной работе Индианского университета и университета Пердью

1. Предполагаем, что раскрытый вес равен $w$, а $n$-длина используемых чисел в битах. Также полагаем, что $w<n$. Стоит отметить, что в реальных схемах $w\ll n$.
2. Секрет $S$ в таком случае выберем длиной $w*n$ битов (если он меньше, дополним его, например, путём повторения битов секрета или добавления случайных битов).
3. Для пользователя $U_{i}$, обладающего весом его доли $p_{i}$, выберем простое число $P_{i}$ длиной $p_{i}*n$ битов и такое, что $p_{i}<w$. Простые числа выбраны в данном случае для упрощения работы алгоритма, для корректной работы схемы достаточно выбора попарно взаимно простых чисел.
4. Вычислим $r_{i}=S\mod P_{i}$ и определим долю пользователя $U_{i}$, как $s_{i}=\{(r_{i},p_{i})\}$.
5. При восстановлении секрета любой коллектив пользователей $U_{i_{1}},U_{i_{2}},\dots ,U_{i_{l}}$ такой, что $p_{i_{1}}+p_{i_{2}}+\dots +p_{i_{l}}>w$ может составить систему уравнений:

${\begin{cases}S\equiv r_{i_{1}}\mod P_{i_{1}}\\S\equiv r_{i_{2}}\mod P_{i_{2}}\\\vdots \\S\equiv r_{i_{l}}\mod P_{i_{l}}\\\end{cases}}$ и вычислить S, применив китайскую теорему об остатках. Так как размер $S$ составляет $w*n$ битов, размер произведения модулей ${\hat {P}}=P_{i_{1}}*P_{i_{2}}*\dots *P_{i_{n}}$ состоит из, по меньшей мере, $(p_{i_{1}}+p_{i_{2}}+\dots +p_{i_{l}})*n-l$, можно видеть, что ${\hat {P}}>S$, пока $w<n$. Именно это позволяет вычислить секрет $S$ единственным образом. Можно ослабить условие на сумму весов долей до $p_{i_{1}}+p_{i_{2}}+\dots +p_{i_{l}}\geqslant w$, тогда в случае $p_{i_{1}}+p_{i_{2}}+\dots +p_{i_{l}}=w$ длина ${\hat {P}}$ составляет, как минимум, $w*n-w+1$, поэтому необходимо ограничить $S$ до $w*n-w$ битов. Если же это невозможно, можно сохранить работоспособность схемы, введя дополнительный элемент, модуль которого $H_{P}$ - наименьшее простое число из $w$ битов, доля элемента - $H_{s}=S\mod H_{P}$. Этот элемент можно использовать, как дополнительное уравнение в приведенной выше системе, в таком случае $P_{i_{1}}*P_{i_{2}}*\dots *P_{i_{l}}*H_{P}>S$, поэтому секрет можно будет восстановить единственным образом. В данной схеме устранён один из главных недостатков обыкновенной схемы с разделением взвешенного секрета - любую долю $s_{i}$ можно описать точкой $(r_{i},P_{i})$, причём эта точка не обладает зависимостью между собственным весом и размером.

---

Данную схему можно также изменить для работы с несколькими секретами. Допустим, необходимо разделить секреты $S_{1},\dots ,S_{k}$, каждый секрет состоит из $n$ битов. Сложим секреты вместе, получив один секрет длиной $k*n$ битов. Необходимо рассмотреть три случая:

1. $k<w$: Добавим случайных битов, до размера $w*n$
2. $k=w$: Ничего не делаем
3. $k>w$: Введём дополнительный элемент с весом $(k-w)$

Производительность схемы

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

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

Значительную часть времени выполнения схемы отнимает генерация последовательностей Миньотта и взаимно простых модулей. Допустим, имеются доли $s_{1},s_{2},\dots ,s_{N}$ с весами $p_{1},p_{2},\dots ,p_{N}$ соответственно. Общий вес долей составит $p_{1}+p_{2}+\dots +p_{N}=W$, вес, необходимый для раскрытия секрета - $w$, размер числа - $n$ битов.

• Генерация последовательности Миньотта состоит из нескольких этапов:

1. Генерация $W$ попарно взаимно простых $P_{1},\dots ,P_{W}$. Преобладающей операцией является нахождение НОК, сложность её составляет $O(n^{2})$. Для каждого нового сгенерированного числа необходимо проверить, является ли оно попарно взаимно простым с каждый из предыдущих элементов, поэтому для генерации $W$ попарно взаимно простых чисел сложность составляет $O(W^{2}n^{2})$.
2. Их сортировка, её сложность составляет $O(Wlog(W)n)$.
3. Проверка условия $\prod _{i=0}^{w-2}P_{W-i}<\prod _{j=1}^{w}P_{j}$. Сложность перемножения двух чисел длиной $l$ битов и $v$ битов составляет $O(lv)$. Сложность проверки составит $O(w^{2}n^{2})$.

Таким образом, общая сложность генерации последовательности Миньотта составляет $O(W^{2}n^{2})$.

• Для генерации модуля пользователю с весом $p_{i}$ необходимо перемножить $p_{i}$ чисел размера $n$. Сложность генерации $N$ модулей составит $O((p_{1}-2)n^{2}+(p_{2}-1)n^{2}+\dots +(p_{N}-1)n^{2})=O((W-N)n^{2})$. Таким образом, общая сложность генерации модулей также составляет $O(W^{2}n^{2})$.

Схема не обладает хорошей производительностью, так как возможно модифицировать её и тем самым избавиться от необходимости генерации последовательностей Миньотта. На графиках приведены результаты анализа производительности схемы, основанной на схеме Миньотта со взвешенном разделением секрета и самой схемы. Для построения графика была выбрана $(4,15)$-пороговая схема с одним секретом, $p_{i}=1$ и ${\hat {p}}=(1,2,3,\dots ,1,2,3)$ соответственно.

Недостатки схемы

• Не обладает криптографической стойкостью, так как даже неполное множество пользователей может предоставить некоторую информацию о секрете.
• Не является простой в принципиальном плане или при реализации. Генерация последовательностей Миньотта и пороговых структур доступа является трудным и ресурсоемким процессом.
• Существует ограничение на область значений, в которой можно выбирать секрет:$S$ должен находится в промежутке между $p_{1}*p_{2}*\dots *p_{k}$ и $p_{n-k+2}*\dots *p_{n}$. Знание этого факта также даёт дополнительную информацию злоумышленнику.
• Для обеспечение хорошей криптостойкости необходима генерация больших значений ${\dfrac {\alpha -\beta }{\beta }}$, что также является ресурсоемкой задачей.
• Злоумышленник может обмануть пользователей схемы, подменив секрет.

Схемы поведения злоумышленников

выбор $S^{\prime }\in (\beta ,\alpha )$

выбор $S^{\prime }=(S+l)\mod r<\beta$

выбор $S^{\prime }=(S+l)\mod r>\alpha$

Можно выделить две схемы, описывающих поведение злоумышленников в пороговых схемах: модель CDV, в которой злоумышленники знают секрет и пытаются передать другим участникам ложные данные, и модель OKS, в которой злоумышленники не знают секрета заранее. В обыкновенной схеме Миньотта один злоумышленник всегда может обмануть $k-1$ пользователей в модели CDV и с большой вероятностью - в модели OKS. Допустим, участники $i_{1},i_{2},\dots ,i_{k}$ разделили секрет, и пользователь $i_{1}$ решает сжульничать. Следовательно, он должен изменить свою тень $I_{i_{1}}$ на $I_{i_{1}}^{\prime }$ так, чтобы $S^{\prime }\neq S,S\in (\beta ,\alpha )$. Пусть $l=p_{i_{2}}p_{i_{3}}\dots p_{i_{k}},r=p_{i_{1}}p_{i_{2}}\dots p_{i_{k}}\Rightarrow S=pl+q,p\in \mathbf {Z} _{b_{1}},q\in \mathbf {Z} _{I}$. Используя китайскую теорему об остатках, получим $S\mod l=S^{\prime }\mod l=q$, то есть, $S^{\prime }$ представим в виде $p^{\prime }l+q$. Так как последовательность Миньотта $p_{1},\dots ,p_{k}$ известна, можно найти $l$. Можно выбрать $p^{\prime }=p\pm 1$, откуда $I_{i_{1}}^{\prime }=(I_{i_{1}}\pm l)\mod p_{i_{1}}\Rightarrow S^{\prime }=(p\pm 1)l+q=(S\pm l)\mod r$

В модели CDV злоумышленник знает секрет, поэтому используя выражение $S^{\prime }=(S\pm l)\mod r$ он может удостовериться в том, что$S^{\prime }\in (\beta ,\alpha )$ (рис.1), существование $S^{\prime }$ гарантировано, если $k-1$ участников не могут определить секрет. Следовательно, злоумышленник может обмануть участников схемы с вероятностью 1. Более того, в этой модели злоумышленник может контролировать значение $S^{\prime }$, вычисляя $q$ напрямую из $S$: $I_{i_{1}}^{\prime }=S^{\prime }\mod p_{i_{1}}$, где $S^{\prime }=p^{\prime }l+q,p^{\prime }\in \mathbb {Z} _{\beta }:S^{\prime }\in (\beta ,\alpha )$

В модели OKS, так как злоумышленник не знает секрет, он не может проверить истинность неравенств $S-l<\beta$ и $S+l>\alpha$. В таком случае он всегда может использовать $I_{i_{1}}^{\prime }=(I_{i_{1}}+l)\mod p_{1}$. Единственный вариант, при котором обман может быть раскрыт - $S+l>\alpha$, откуда $S^{\prime }=(S+l)\mod r<\beta$(рис.2) или $S^{\prime }=(S+l)\mod r>\alpha$(рис.3). Следовательно, вероятность успешного обмана составляет $1-{\frac {1}{[{\frac {\alpha -\beta }{l}}]}}$

Пример

Пусть $n=5,k=3,p_{1}=661,p_{2}=673,p_{3}=677,p_{4}=683,p_{5}=691\Rightarrow \alpha =301165481,\beta =471953$. Тогда для секрета $S=500000$ будут сгенерированы тени $I_{1}=284,I_{2}=634,I_{3}=374,I_{4}=44,I_{5}=407$. Допустим, участники 1,2,3 объединили свои доли, и участник 1 хочет сжульничать. Тогда он вычисляет $p_{2}*p_{3}=455621$ и изменяет свою долю так, что $I_{1}^{\prime }=(I_{1}+p_{2}p_{3})\mod p_{1}=476$. В таком случае, после решения системы уравнений ${\begin{cases}x\equiv 476\mod 661\\x\equiv 634\mod 673\\x\equiv 374\mod 677\end{cases}}$ участники восстановят неверный секрет $S^{\prime }=(S+p_{2}p_{3})\mod p_{1}p_{2}p_{3}=955621$, также находящийся между $\alpha$и $\beta$. При этом пользователь 1 может получить настоящий секрет: $S=(S^{\prime }-p_{2}p_{3})\mod p_{1}p_{2}p_{3}=500000$

Модификация схемы

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

• Вводится дилер, генерирующий $(k,n)$-последовательность Миньотта $p_{1},p_{2},\dots ,p_{n}$. Также дилер генерирует $n$ различных простых $m_{1},\dots ,m_{n}$ таких, что:${\frac {\alpha -\beta }{\beta \max _{1\leqslant i_{1}<\dots <i_{k-1}\leqslant n}(m_{i_{1}}*\dots *m_{i_{k-1}})}}$ является достаточно большим. Секрет $S$ выбирается так, что $\beta <S<\alpha$. Долями $I_{i}$ являются $(S\mod p_{i},S\mod m_{i}p_{i},m_{i})$. Процесс восстановления секрета проходит так же, как и в стандартной схеме Миньотта. После того, как секрет $S^{\prime }$ восстановлен, любой участник $i$ может определить обман путём сравнения $S^{\prime }\mod m_{i}$ с данными, переданными дилером. Таким образом, злоумышленник может обмануть участника $j$ с вероятностью ${\frac {1}{m_{j}}}$

Литература

• M. Mignotte. How to Share a Secret (англ.) // Lecture Notes in Computer Science. — 1983. — Vol. 149. — P. 371—375. — doi:10.1007/3-540-39466-4_27. (недоступная ссылка)
• E. Kranakis. Primality and Cryptography (англ.) // Wiley-Teubner Series in Computer Science. — 1986. — Vol. 1. — P. 9.
• C. A. Asmuth and J. Bloom. A modular approach to key safeguarding (англ.) // IEEE Transactions on Information Theory. — 1986. — Vol. 2. — P. 208-210.

Ссылки

• General Secret Sharing Based on the Chinese Remainder Theorem (англ.). Electronic Notes in Theoretical Computer Science (2007). Дата обращения: 12 декабря 2013. Архивировано из оригинала 3 декабря 2013 года.
• A New Approach to Weighted Multi-Secret Sharing (англ.). Electronic Notes in Theoretical Computer Science (2011). Дата обращения: 12 декабря 2013. Архивировано из оригинала 19 декабря 2012 года.
• Cheating Detection and Cheater Identification in CRT-based Secret Sharing Schemes (англ.). “Al. I. Cuza” University Iasi, Romania (2009). Дата обращения: 12 декабря 2013.
• 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. Архивировано из оригинала 3 декабря 2013 года.