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

История

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример

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

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

${\displaystyle {\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}}}$ .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

---

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример

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

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

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

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

Примечания

Литература

• . (англ.) // Lecture Notes in Computer Science. — 1983. — Vol. 149 . — P. 371—375 . — doi : . (недоступная ссылка)
• . (англ.) // Wiley-Teubner Series in Computer Science. — 1986. — Vol. 1 . — P. 9 .
• . (англ.) // IEEE Transactions on Information Theory. — 1986. — Vol. 2 . — P. 208-210 .

Ссылки

• (англ.) . Electronic Notes in Theoretical Computer Science (2007). Дата обращения: 12 декабря 2013. Архивировано из 3 декабря 2013 года.
• (англ.) . Electronic Notes in Theoretical Computer Science (2011). Дата обращения: 12 декабря 2013. Архивировано из 19 декабря 2012 года.
• (англ.) . “Al. I. Cuza” University Iasi, Romania (2009). Дата обращения: 12 декабря 2013.
• (англ.) . Proceedings of the 6th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (2004). Дата обращения: 12 декабря 2013. Архивировано из 3 декабря 2013 года.