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

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

История

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

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

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

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

$\{\begin{array}{c}x\equiv b_{1}mod{m}_1\\ ⋮\\ x\equiv b_{k}mod{m}_k\end{array}$ имеет решения в $\mathbb{Z}$ тогда и только тогда, когда $b_i\equiv b_{j}mod(m_i,m_j)\mathrm{\forall }1⩽i,j⩽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\mathrm{\forall }1⩽i<j⩽k$, китайскую теорему об остатках называют стандартной.

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

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

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

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

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

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

$\overline{𝒜}=\{A\in P(\{1,2,\dots ,n\})\mid |A|⩽k-1\}$

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

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

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

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

Пороговая схема разделения секрета Миньотта использует специальные последовательности чисел, названные последовательностями Миньотта. Пусть $n$ – целое, $n⩾2$, и $2⩽k⩽n$. $(k,n)$-последовательность Миньотта – последовательность взаимно простых положительных $p_1<p_2<\dots <p_n$ таких, что $\prod _{i=0}^{k-2}{p}_{n-i}<\prod _{i=1}^k{p}_i$ Последнее утверждение также равносильно следующему: $\underset{1⩽i_1<\dots <i_{k-1}⩽n}{\max }(p_{i_1}\dots p_{i_{k-1}})<\underset{1⩽i_1<\dots <i_k⩽n}{\min }(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$
2. Доли вычисляются, как $I_i=Smod{p}_i$, для всех $1⩽i⩽n$
3. Имея $k$ различных теней $I_{i_1},\dots ,I_{i_k}$, можно получить секрет $S$, используя стандартный вариант китайской теоремы об остатках – им будет единственное решение по модулю $p_{i_1}\dots p_{i_k}$ системы:

$\{\begin{array}{c}x\equiv I_{i_1}mod{p}_{i_1}\\ ⋮\\ x\equiv I_{i_k}mod{p}_{i_k}\end{array}$ Секретом является решение приведенной выше системы, более того, $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 ⩾p_{i_1}\dots p_{i_{k-1}}>x_0$. Для того, чтобы получить приемлемый уровень безопасности, должны быть использованы $(k,n)$ последовательности Миньотта с большим значением $\frac{\alpha -\beta }{\beta }$ Очевидно, что схема Миньотта не обладает значительной криптографической стойкостью, однако может оказаться удобной в приложениях, где компактность теней является решающим фактором.

Пример

Допустим, необходимо разделить секрет между $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=Smod{p}_i$: $I_1=50000mod5=0,I_2=50000mod7=6,I_3=50000mod11=5,I_4=50000mod13=2,I_5=50000mod17=3,I_6=50000mod19=11$
• Для восстановления секрета решим систему уравнений для $k$ теней (предположим, секрет восстанавливают участники 1-5):

$\{\begin{array}{c}x\equiv 0mod5\\ x\equiv 6mod7\\ x\equiv 5mod11\\ x\equiv 2mod13\\ x\equiv 3mod17\end{array}$.

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

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

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

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

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

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

Пусть $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}\}]\mathrm{\forall }1⩽i⩽N$, где $P_{a_1},\dots ,P_{a_N}$ - произвольное разбиение множества $\{1,2,\dots ,W\}$ такое, что $|P_{a_i}|=p_i\mathrm{\forall }1⩽i⩽N$

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

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

• Схема Асмута-Блума, также основанная на китайской теореме об остатках, была впервые представлена в 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=Smod{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{array}{c}S\equiv r_{i_1}mod{P}_{i_1}\\ S\equiv r_{i_2}mod{P}_{i_2}\\ ⋮\\ S\equiv r_{i_l}mod{P}_{i_l}\end{array}$ и вычислить 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}⩾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=Smod{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)$

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

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

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

Значительную часть времени выполнения схемы отнимает генерация последовательностей Миньотта и взаимно простых модулей. Допустим, имеются доли $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^2{n}^2)$.
2. Их сортировка, её сложность составляет $O(Wlog(W)n)$.
3. Проверка условия $\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)$ соответственно.

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

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

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

выбор $S^{\prime }\in (\beta ,\alpha )$

выбор $S^{\prime }=(S+l)modr<\beta$

выбор $S^{\prime }=(S+l)modr>\alpha$

Можно выделить две схемы, описывающих поведение злоумышленников в пороговых схемах: модель CDV, в которой злоумышленники знают секрет и пытаются передать другим участникам ложные данные, и модель OKS, в которой злоумышленники не знают секрета заранее. В обыкновенной схеме Миньотта один злоумышленник всегда может обмануть $k-1$ пользователей в модели CDV и с большой вероятностью - в модели OKS. Допустим, участники $i_1,i_2,\dots ,i_k$ разделили секрет, и пользователь $i_1$ решает сжульничать. Следовательно, он должен изменить свою тень $I_{i_1}$ на $I_{i_1}^{\prime }$ так, чтобы $S^{\prime }\ne 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 {𝐙}_{b_1},q\in {𝐙}_I$. Используя китайскую теорему об остатках, получим $Smodl=S^{\prime }modl=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)modr$

В модели CDV злоумышленник знает секрет, поэтому используя выражение $S^{\prime }=(S\pm l)modr$ он может удостовериться в том, что$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)modr<\beta$(рис.2) или $S^{\prime }=(S+l)modr>\alpha$(рис.3). Следовательно, вероятность успешного обмана составляет $1-\frac{1}{[\frac{\alpha -\beta }{l}]}$

Пример

Пусть $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{array}{c}x\equiv 476mod661\\ x\equiv 634mod673\\ x\equiv 374mod677\end{array}$ участники восстановят неверный секрет $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$

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

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

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

Литература

• Шаблон:СтатьяШаблон:Недоступная ссылка
• Шаблон:Статья
• Шаблон:Статья

Ссылки

• Шаблон:Cite web
• Шаблон:Cite web
• Шаблон:Cite web
• Шаблон:Cite web