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

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

История

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

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

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

В основе схемы лежит использование китайской теоремы об остатках, которая позволяет пользователям, имеющим некоторую долю секрета, восстановить сам секрет, причём единственным образом. Существует несколько версий теоремы, назовём следующую общей: Пусть $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$ , китайскую теорему об остатках называют стандартной[2].

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

Допустим, имеется 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)$ -пороговыми схемами разделения секрета[1].

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

Пороговая схема разделения секрета Миньотта использует специальные последовательности чисел, названные последовательностями Миньотта. Пусть $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}$
Доли вычисляются, как $I_{i}=S\mod p_{i}$ , для всех $1\leqslant i\leqslant n$
Имея $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}$ .[1] Для того, чтобы получить приемлемый уровень безопасности, должны быть использованы $(k,n)$ последовательности Миньотта с большим значением ${\dfrac {\alpha -\beta }{\beta }}$ [3] Очевидно, что схема Миньотта не обладает значительной криптографической стойкостью, однако может оказаться удобной в приложениях, где компактность теней является решающим фактором.

Пример

Допустим, необходимо разделить секрет между $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}}])$ .В данном случае для нахождения секрета необходимо использовать обобщённый вариант китайской теоремы об остатках.[4]

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

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

Пусть $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$ битов. Реализация схемы Миньотта со взвешенным разделением секрета не является целесообразной, так как генерация последовательности Миньотта и взвешенной пороговой структуры доступа является трудо- и ресурсоемкой задачей. Существуют более простые и эффективные схемы со взвешенным разделением секрета, в которых также устранена зависимость между весом и размером тени.[5]

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

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

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

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

Предполагаем, что раскрытый вес равен $w$ , а $n$ -длина используемых чисел в битах. Также полагаем, что $w<n$ . Стоит отметить, что в реальных схемах $w\ll n$ .
Секрет $S$ в таком случае выберем длиной $w*n$ битов (если он меньше, дополним его, например, путём повторения битов секрета или добавления случайных битов).
Для пользователя $U_{i}$ , обладающего весом его доли $p_{i}$ , выберем простое число $P_{i}$ длиной $p_{i}*n$ битов и такое, что $p_{i}<w$ . Простые числа выбраны в данном случае для упрощения работы алгоритма, для корректной работы схемы достаточно выбора попарно взаимно простых чисел.
Вычислим $r_{i}=S\mod P_{i}$ и определим долю пользователя $U_{i}$ , как $s_{i}=\{(r_{i},p_{i})\}$ .
При восстановлении секрета любой коллектив пользователей $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$ битов. Необходимо рассмотреть три случая:

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

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

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

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

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

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

Генерация $W$ попарно взаимно простых $P_{1},\dots ,P_{W}$ . Преобладающей операцией является нахождение НОК, сложность её составляет $O(n^{2})$ . Для каждого нового сгенерированного числа необходимо проверить, является ли оно попарно взаимно простым с каждый из предыдущих элементов, поэтому для генерации $W$ попарно взаимно простых чисел сложность составляет $O(W^{2}n^{2})$ .
Их сортировка, её сложность составляет $O(Wlog(W)n)$ .
Проверка условия $\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)$ соответственно[5].

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

Не обладает криптографической стойкостью, так как даже неполное множество пользователей может предоставить некоторую информацию о секрете.
Не является простой в принципиальном плане или при реализации. Генерация последовательностей Миньотта и пороговых структур доступа является трудным и ресурсоемким процессом.
Существует ограничение на область значений, в которой можно выбирать секрет: $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}}]}}$ [7]

Пример

Пусть $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$ [7]

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

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

Вводится дилер, генерирующий $(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}}}$ [7]

Примечания

Maurice Mignotte, 1983, pp.371-375
General Secret Sharing Based on the Chinese Remainder Theorem (англ.) (недоступная ссылка). Electronic Notes in Theoretical Computer Science (2007). Дата обращения: 18 ноября 2013. Архивировано 3 декабря 2013 года.
Evangelos Kranakis, 1986, p. 9
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 года.
A New Approach to Weighted Multi-Secret Sharing (англ.) (недоступная ссылка). Electronic Notes in Theoretical Computer Science (2011). Дата обращения: 18 ноября 2013. Архивировано 19 декабря 2012 года.
C. A. Asmuth and J. Bloom, 1986, pp. 208-210
Cheating Detection and Cheater Identiﬁcation in CRT-based Secret Sharing Schemes (англ.). “Al. I. Cuza” University Iasi, Romania (2009). Дата обращения: 18 ноября 2013.

Литература

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 Identiﬁcation 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 года.

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

[:0-1] 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 декабря 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. Архивировано 3 декабря 2013 года.

[:1-5] A New Approach to Weighted Multi-Secret Sharing (англ.) (недоступная ссылка). Electronic Notes in Theoretical Computer Science (2011). Дата обращения: 18 ноября 2013. Архивировано 19 декабря 2012 года.

[6] C. A. Asmuth and J. Bloom, 1986, pp. 208-210

[:2-7] Cheating Detection and Cheater Identiﬁcation in CRT-based Secret Sharing Schemes (англ.). “Al. I. Cuza” University Iasi, Romania (2009). Дата обращения: 18 ноября 2013.