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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Схема Миньотта — пороговая схема разделения секрета, построенная с использованием простых чисел. Позволяет разделить секрет (число) между 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 \geqslant k \geqslant n . (k,n)-последовательность Миньотта – последовательность взаимно простых положительных p_1 < p_2 <\dots  < p_n таких, что \prod^{k-2}_{i=0}p_{n-i}<\prod^{k}_{i=1}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]

Алгоритм[править | править исходный текст]

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

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

\begin{cases}
x \equiv I_{i_1}\mod p_{i_1}\\
\vdots \\
x \equiv I_{i_k}\mod p_{i_k}
\end{cases} Секретом является решение приведенной выше системы, более того, S лежит в пределах Z_{{p_{i_1}},\dots ,p_{i_k}}, т.к. S < \alpha . С другой стороны, имея всего k-1 различных теней I_{i_1},\dots ,I_{i_{k-1}}, можно сказать, что S\equiv x_0 \mod p_{i_1}\dots p_{i_{k-1}}, где x_0 – единственное решение по модулю p_{i_1}\dots p_{i_{k-1}} исходной системы (в данном случае: S>\beta \geqslant p_{i_1}\dots p_{i_{k-1}}>x_0.[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 2\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^{\prime }_{j}\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 взаимно простых чисел, а также некоторое случайное число, с помощью которого шифруется секрет, и уже на основе зашифрованного секрета вычисляются тени. В схема Асмута-Блума отсутствуют некоторые недостатки, присущие схеме Миньотта:
  1. Нет ограничения на область, в которой можно выбирать секрет
  2. Набор из менее, чем k теней пользователей не дает никакой информации о секрете
  1. Предполагаем, что раскрытый вес равен w, а n-длина используемых чисел в битах. Также полагаем, что w<n. Стоит отметить, что в реальных схемах w\ll n.
  2. Секрет S в таком случае выберем длиной w*n битов (если он меньше, дополним его, например, путем повторения битов секрета или добавления случайных битов).
  3. Для пользователя U_i, обладающего весом его доли p_i, выберем простое число P_i длиной p_i*n битов и такое, что p_i<w. Простые числа выбраны в данном случае для упрощения работы алгоритма, для корректной работы схемы достаточно выбора попарно взаимно простых чисел.
  4. Вычислим r_i=S\mod P_i и определим долю пользователя U_i, как s_i=\{(r_i,p_i)\}.
  5. При восстановлении секрета любой коллектив пользователей U_{i_1},U_{i_2},\dots ,U_{i_l} такой, что p_{i_1}+p_{i_2}+\dots +p_{i_l}>w может составить систему уравнений:

\begin{cases}
S \equiv r_{i_1}\mod P_{i_1}\\
S \equiv r_{i_2}\mod P_{i_2}\\
\vdots \\
S \equiv r_{i_l}\mod P_{i_l}\\
\end{cases} и вычислить S, применив китайскую теорему об остатках. Так как размер S составляет w*n битов, размер произведения модулей \hat{P}=P_{i_1}*P_{i_2}*\dots *P_{i_n} состоит из, по меньшей мере, (p_{i_1}+p_{i_2}+\dots +p_{i_l})*n-l, можно видеть, что \hat{P}>S, пока w<n. Именно это позволяет вычислить секрет S единственным образом. Можно ослабить условие на сумму весов долей до p_{i_1}+p_{i_2}+\dots +p_{i_l}\geqslant w, тогда в случае p_{i_1}+p_{i_2}+\dots +p_{i_l}=w длина \hat{P} составляет, как минимум, w*n-w+1, поэтому необходимо ограничить S до w*n-w битов. Если же это невозможно, можно сохранить работоспособность схемы, введя дополнительный элемент, модуль которого H_P - наименьшее простое число из w битов, доля элемента - H_s=S\mod H_P. Этот элемент можно использовать, как дополнительное уравнение в приведенной выше системе, в таком случае P_{i_1}*P_{i_2}*\dots *P_{i_l}*H_P>S, поэтому секрет можно будет восстановить единственным образом. В данной схеме устранен один из главных недостатков обыкновенной схемы с разделением взвешенного секрета - любую долю s_i можно описать точкой (r_i,P_i), причем эта точка не обладает зависимостью между собственным весом и размером.


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

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

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

Таким образом, общая сложность генерации последовательности Миньотта составляет O(W^2n^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^2n^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^{\prime }_{i_1} так, чтобы 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^{\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

В модели CDV злоумышленник знает секрет, поэтому используя выражение S^\prime =(S\pm l)\mod r он может удостовериться в том, чтоS^\prime \in (\beta ,\alpha ) (рис.1), существование S^\prime гарантировано, если k-1 участников не могут определить секрет. Следовательно, злоумышленник может обмануть участников схемы с вероятностью 1. Более того, в этой модели злоумышленник может контролировать значение S^\prime , вычисляя q напрямую из S: I^{\prime }_{i_1}=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^{\prime }_{i_1}=(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^{\prime }_1=(I_1+p_2p_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_2p_3)\mod p_1p_2p_3=955621, также находящийся между \alpha и \beta . При этом пользователь 1 может получить настоящий секрет: S=(S^\prime -p_2p_3)\mod p_1p_2p_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_ip_i, m_i). Процесс восстановления секрета проходит так же, как и в стандартной схеме Миньотта. После того, как секрет S^\prime восстановлен, любой участник i может определить обман путем сравнения S^\prime \mod m_i с данными, переданными дилером. Таким образом, злоумышленник может обмануть участника j с вероятностью \frac{1}{m_j} [7]

Примечания[править | править исходный текст]

  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.
  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
  7. 1 2 3 Cheating Detection and Cheater Identification in CRT-based Secret Sharing Schemes (англ.). “Al. I. Cuza” University Iasi, Romania (2009). Проверено 18 ноября 2013.

Литература[править | править исходный текст]

Ссылки[править | править исходный текст]