WikiSort.ru - Не сортированное

ПОИСК ПО САЙТУ | о проекте

Схема Миньотта — пороговая схема разделения секрета, построенная с использованием простых чисел. Позволяет разделить секрет (число) между $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_{5}=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 }}$ , что также является ресурсоемкой задачей.
Злоумышленник может обмануть пользователей схемы, подменив секрет.

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

Можно выделить две схемы, описывающих поведение злоумышленников в пороговых схемах: модель 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]

Примечания

1 2 3 4 Maurice Mignotte, 1983, pp.371-375
↑ General Secret Sharing Based on the Chinese Remainder Theorem (англ.). Electronic Notes in Theoretical Computer Science (2007). Проверено 18 ноября 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.
1 2 3 A New Approach to Weighted Multi-Secret Sharing (англ.). Electronic Notes in Theoretical Computer Science (2011). Проверено 18 ноября 2013.
↑ C. A. Asmuth and J. Bloom, 1986, pp. 208-210
1 2 3 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.
A New Approach to Weighted Multi-Secret Sharing (англ.). Electronic Notes in Theoretical Computer Science (2011). Проверено 12 декабря 2013.
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.

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .

Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2025
WikiSort.ru - проект по пересортировке и дополнению контента Википедии

[:0-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.

[:1-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

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