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

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

История

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

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

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

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

В основе схемы лежит использование китайской теоремы об остатках, которая позволяет пользователям, имеющим некоторую долю секрета, восстановить сам секрет, причём единственным образом. Существует несколько версий теоремы, назовём следующую общей: Пусть [math]\displaystyle{ k\geqslant 2, m_1,\dots,m_k\geqslant 2, b_1,\dots,b_k\in \mathbb{Z} }[/math]. Тогда система уравнений

[math]\displaystyle{ \begin{cases} x \equiv b_1\mod m_1\\ \vdots \\ x \equiv b_k\mod m_k \end{cases} }[/math] имеет решения в [math]\displaystyle{ \mathbb{Z} }[/math] тогда и только тогда, когда [math]\displaystyle{ b_i\equiv b_j\mod (m_i,m_j)\forall 1\leqslant i,j\leqslant k }[/math]. Более того, если приведенная система имеет решения в [math]\displaystyle{ \mathbb{Z} }[/math], она имеет единственное решение в [math]\displaystyle{ \mathbb{Z}_{[m_1,\dots,m_k]}, [m_1,\dots,m_k] }[/math] определяет наименьшее общее кратное [math]\displaystyle{ m_1,\dots,m_k }[/math]. В случае, если [math]\displaystyle{ (m_i,m_j)=1\forall 1\leqslant i\lt j\leqslant k }[/math], китайскую теорему об остатках называют стандартной.

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

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

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

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

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

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

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

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

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

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

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

Пороговая схема разделения секрета Миньотта использует специальные последовательности чисел, названные последовательностями Миньотта. Пусть [math]\displaystyle{ n }[/math] – целое, [math]\displaystyle{ n \geqslant 2 }[/math], и [math]\displaystyle{ 2 \leqslant k \leqslant n }[/math]. [math]\displaystyle{ (k,n) }[/math]-последовательность Миньотта – последовательность взаимно простых положительных [math]\displaystyle{ p_1 \lt p_2 \lt \dots \lt p_n }[/math] таких, что [math]\displaystyle{ \prod^{k-2}_{i=0}p_{n-i}\lt \prod^{k}_{i=1}p_i }[/math] Последнее утверждение также равносильно следующему: [math]\displaystyle{ \max _{1 \leqslant i_1\lt \dots \lt i_{k-1}\leqslant n}(p_{i_1}\dots p_{i_{k-1}})\lt \min _{1 \leqslant i_1\lt \dots \lt i_k\leqslant n}(p_{i_1}\dots p_{i_k}) }[/math]

Алгоритм

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

1. Секрет [math]\displaystyle{ S }[/math] выбирается, как случайное число такое, что [math]\displaystyle{ \beta \lt S \lt \alpha }[/math], где [math]\displaystyle{ \alpha = \prod^{k}_{i=1}p_i , \beta = \prod^{k-2}_{i=0}p_{n-i} }[/math]. Другими словами, секрет должен находиться в промежутке между [math]\displaystyle{ p_1 * p_2 * \dots * p_k }[/math] и [math]\displaystyle{ p_{n-k+2} * \dots * p_n }[/math]
2. Доли вычисляются, как [math]\displaystyle{ I_i=S\mod p_i }[/math], для всех [math]\displaystyle{ 1 \leqslant i \leqslant n }[/math]
3. Имея [math]\displaystyle{ k }[/math] различных теней [math]\displaystyle{ I_{i_1},\dots ,I_{i_k} }[/math], можно получить секрет [math]\displaystyle{ S }[/math], используя стандартный вариант китайской теоремы об остатках – им будет единственное решение по модулю [math]\displaystyle{ p_{i_1}\dots p_{i_k} }[/math] системы:

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

Пример

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

• Выбираем последовательность Миньотта [math]\displaystyle{ p_1=5, p_2=7, p_3=11, p_4=13, p_5=17, p_6=19 }[/math].
• Вычисляем для данной последовательности [math]\displaystyle{ \alpha =p_1*p_2*p_3*p_4*p_5=85085 }[/math], [math]\displaystyle{ \beta =p_3*p_4*p_5*p_6=46189 }[/math].
• Выбираем [math]\displaystyle{ S }[/math] такое, что [math]\displaystyle{ \beta \lt S\lt \alpha }[/math], например, [math]\displaystyle{ S=50000 }[/math].
• Вычисляем доли: [math]\displaystyle{ I_i=S\mod p_i }[/math]: [math]\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 }[/math]
• Для восстановления секрета решим систему уравнений для [math]\displaystyle{ k }[/math] теней (предположим, секрет восстанавливают участники 1-5):

[math]\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} }[/math].

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

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

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

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

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

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

Пусть [math]\displaystyle{ S(k,n,N,P) }[/math] - секрет, где [math]\displaystyle{ P=(p_1,\dots ,p_N) }[/math] - веса теней пользователей. Сгенерируем [math]\displaystyle{ (k,W) }[/math]-последовательность Миньотта, где [math]\displaystyle{ W=\sum_{i=1}^{n}p_i }[/math]. Тогда [math]\displaystyle{ P_i=[\{ P^{\prime }_{j}\mid j\in P_{a_j}\}] \forall 1 \leqslant i \leqslant N }[/math], где [math]\displaystyle{ P_{a_1},\dots ,P_{a_N} }[/math] - произвольное разбиение множества [math]\displaystyle{ \{1,2,\dots ,W\} }[/math] такое, что [math]\displaystyle{ |P_{a_i}|=p_i \forall 1\leqslant i\leqslant N }[/math]

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

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

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

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

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

1. Предполагаем, что раскрытый вес равен [math]\displaystyle{ w }[/math], а [math]\displaystyle{ n }[/math]-длина используемых чисел в битах. Также полагаем, что [math]\displaystyle{ w\lt n }[/math]. Стоит отметить, что в реальных схемах [math]\displaystyle{ w\ll n }[/math].
2. Секрет [math]\displaystyle{ S }[/math] в таком случае выберем длиной [math]\displaystyle{ w*n }[/math] битов (если он меньше, дополним его, например, путём повторения битов секрета или добавления случайных битов).
3. Для пользователя [math]\displaystyle{ U_i }[/math], обладающего весом его доли [math]\displaystyle{ p_i }[/math], выберем простое число [math]\displaystyle{ P_i }[/math] длиной [math]\displaystyle{ p_i*n }[/math] битов и такое, что [math]\displaystyle{ p_i\lt w }[/math]. Простые числа выбраны в данном случае для упрощения работы алгоритма, для корректной работы схемы достаточно выбора попарно взаимно простых чисел.
4. Вычислим [math]\displaystyle{ r_i=S\mod P_i }[/math] и определим долю пользователя [math]\displaystyle{ U_i }[/math], как [math]\displaystyle{ s_i=\{(r_i,p_i)\} }[/math].
5. При восстановлении секрета любой коллектив пользователей [math]\displaystyle{ U_{i_1},U_{i_2},\dots ,U_{i_l} }[/math] такой, что [math]\displaystyle{ p_{i_1}+p_{i_2}+\dots +p_{i_l}\gt w }[/math] может составить систему уравнений:

[math]\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} }[/math] и вычислить S, применив китайскую теорему об остатках. Так как размер [math]\displaystyle{ S }[/math] составляет [math]\displaystyle{ w*n }[/math] битов, размер произведения модулей [math]\displaystyle{ \hat{P}=P_{i_1}*P_{i_2}*\dots *P_{i_n} }[/math] состоит из, по меньшей мере, [math]\displaystyle{ (p_{i_1}+p_{i_2}+\dots +p_{i_l})*n-l }[/math], можно видеть, что [math]\displaystyle{ \hat{P}\gt S }[/math], пока [math]\displaystyle{ w\lt n }[/math]. Именно это позволяет вычислить секрет [math]\displaystyle{ S }[/math] единственным образом. Можно ослабить условие на сумму весов долей до [math]\displaystyle{ p_{i_1}+p_{i_2}+\dots +p_{i_l}\geqslant w }[/math], тогда в случае [math]\displaystyle{ p_{i_1}+p_{i_2}+\dots +p_{i_l}=w }[/math] длина [math]\displaystyle{ \hat{P} }[/math] составляет, как минимум, [math]\displaystyle{ w*n-w+1 }[/math], поэтому необходимо ограничить [math]\displaystyle{ S }[/math] до [math]\displaystyle{ w*n-w }[/math] битов. Если же это невозможно, можно сохранить работоспособность схемы, введя дополнительный элемент, модуль которого [math]\displaystyle{ H_P }[/math] - наименьшее простое число из [math]\displaystyle{ w }[/math] битов, доля элемента - [math]\displaystyle{ H_s=S\mod H_P }[/math]. Этот элемент можно использовать, как дополнительное уравнение в приведенной выше системе, в таком случае [math]\displaystyle{ P_{i_1}*P_{i_2}*\dots *P_{i_l}*H_P\gt S }[/math], поэтому секрет можно будет восстановить единственным образом. В данной схеме устранён один из главных недостатков обыкновенной схемы с разделением взвешенного секрета - любую долю [math]\displaystyle{ s_i }[/math] можно описать точкой [math]\displaystyle{ (r_i,P_i) }[/math], причём эта точка не обладает зависимостью между собственным весом и размером.

---

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

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

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

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

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

Значительную часть времени выполнения схемы отнимает генерация последовательностей Миньотта и взаимно простых модулей. Допустим, имеются доли [math]\displaystyle{ s_1,s_2,\dots ,s_N }[/math] с весами [math]\displaystyle{ p_1,p_2,\dots ,p_N }[/math] соответственно. Общий вес долей составит [math]\displaystyle{ p_1+p_2+\dots +p_N=W }[/math], вес, необходимый для раскрытия секрета - [math]\displaystyle{ w }[/math], размер числа - [math]\displaystyle{ n }[/math] битов.

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

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

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

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

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

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

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

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

выбор [math]\displaystyle{ S^\prime \in (\beta, \alpha ) }[/math]

выбор [math]\displaystyle{ S^\prime =(S+l)\mod r\lt \beta }[/math]

выбор [math]\displaystyle{ S^\prime =(S+l)\mod r\gt \alpha }[/math]

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

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

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

Пример

Пусть [math]\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 }[/math]. Тогда для секрета [math]\displaystyle{ S=500000 }[/math] будут сгенерированы тени [math]\displaystyle{ I_1=284,I_2=634,I_3=374,I_4=44,I_5=407 }[/math]. Допустим, участники 1,2,3 объединили свои доли, и участник 1 хочет сжульничать. Тогда он вычисляет [math]\displaystyle{ p_2*p_3=455621 }[/math] и изменяет свою долю так, что [math]\displaystyle{ I^{\prime }_1=(I_1+p_2p_3)\mod p_1=476 }[/math]. В таком случае, после решения системы уравнений [math]\displaystyle{ \begin{cases} x \equiv 476\mod 661\\ x \equiv 634\mod 673\\ x \equiv 374\mod 677 \end{cases} }[/math] участники восстановят неверный секрет [math]\displaystyle{ S^\prime =(S+p_2p_3)\mod p_1p_2p_3=955621 }[/math], также находящийся между [math]\displaystyle{ \alpha }[/math]и [math]\displaystyle{ \beta }[/math]. При этом пользователь 1 может получить настоящий секрет: [math]\displaystyle{ S=(S^\prime -p_2p_3)\mod p_1p_2p_3=500000 }[/math]

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

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

• Вводится дилер, генерирующий [math]\displaystyle{ (k,n) }[/math]-последовательность Миньотта [math]\displaystyle{ p_1, p_2,\dots ,p_n }[/math]. Также дилер генерирует [math]\displaystyle{ n }[/math] различных простых [math]\displaystyle{ m_1,\dots ,m_n }[/math] таких, что:[math]\displaystyle{ \frac{\alpha -\beta }{\beta \max _{1\leqslant i_1\lt \dots \lt i_{k-1}\leqslant n}(m_{i_1}*\dots *m_{i_{k-1}})} }[/math] является достаточно большим. Секрет [math]\displaystyle{ S }[/math] выбирается так, что [math]\displaystyle{ \beta \lt S\lt \alpha }[/math]. Долями [math]\displaystyle{ I_i }[/math] являются [math]\displaystyle{ (S\mod p_i, S\mod m_ip_i, m_i) }[/math]. Процесс восстановления секрета проходит так же, как и в стандартной схеме Миньотта. После того, как секрет [math]\displaystyle{ S^\prime }[/math] восстановлен, любой участник [math]\displaystyle{ i }[/math] может определить обман путём сравнения [math]\displaystyle{ S^\prime \mod m_i }[/math] с данными, переданными дилером. Таким образом, злоумышленник может обмануть участника [math]\displaystyle{ j }[/math] с вероятностью [math]\displaystyle{ \frac{1}{m_j} }[/math]

Литература

• 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 года.