Разделение секрета

Каждая доля секрета — это плоскость, а секрет представляет собой точку пересечения трёх плоскостей. Две доли секрета позволяют получить линию, на которой лежит секретная точка

Разделение секрета (Шаблон:Lang-en) — термин в криптографии, под которым понимают любой из способов распределения секрета среди группы участников, каждому из которых достаётся «персональная доля». Секрет может воссоздать только коалиция участников из первоначальной группы, причём входить в эту коалицию должно не менее некоторого изначально известного числа (порогового значения) участников.

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

Существующие схемы имеют две составляющие: разделение и восстановление секрета. К разделению относится формирование частей секрета и распределение их между членами группы, что позволяет разделить ответственность за секрет между её участниками. Обратная схема должна обеспечить его восстановление при условии доступности его хранителей в некотором необходимом количествеШаблон:Sfn.

Пример использования: протокол тайного голосования на основе разделения секретаШаблон:Sfn.

Простейший пример схемы разделения секрета

Пусть имеется группа из $t$ человек и сообщение $s$ длины $n$ , состоящее из двоичных символов. Если подобрать случайным образом такие двоичные сообщения $s_{1}, \dots, s_{t}$ , что в сумме они будут равняться $s$ , и распределить эти сообщения между всеми членами группы, получится, что прочесть сообщение будет возможно только в случае, если все члены группы соберутся вместеШаблон:Sfn.

В такой схеме есть существенная проблема: в случае утраты хотя бы одного из членов группы секрет будет утерян для всей группы безвозвратно.

Шаблон:ЯкорьПороговая схема

В отличие от процедуры разбиения секрета, где $t = n$ , в процедуре разделения секрета количество долей, которые нужны для восстановления секрета, может отличаться от того, на сколько долей секрет разделён. Такая схема носит название пороговой схемы $(t, n)$ , где $n$ — количество долей, на которые был разделён секрет, а $t$ — количество долей, которые нужны для восстановления секрета. Идеи схем $t \neq n$ были независимо предложены в 1979 году Ади Шамиром и Джорджем Блэкли. Кроме этого, подобные процедуры исследовались Гусом Симмонсом^[1]Шаблон:Sfn Шаблон:Sfn.

Если коалиция участников такова, что они имеют достаточное количество долей для восстановления секрета, то коалиция называется разрешённой. Схемы разделения секрета, в которых разрешённые коалиции участников могут однозначно восстановить секрет, а неразрешённые не получают никакой апостериорной информации о возможном значении секрета, называются совершеннымиШаблон:Sfn.

Схема Шамира

Шаблон:Main

Идея схемы заключается в том, что двух точек достаточно для задания прямой, трёх точек — для задания параболы, четырёх точек — для кубической параболы, и так далее. Чтобы задать многочлен степени $k$ , требуется $k + 1$ точек.

Для того, чтобы после разделения секрет могли восстановить только $k$ участников, его «прячут» в формулу многочлена степени $(k - 1)$ над конечным полем $G$ . Для однозначного восстановления этого многочлена необходимо знать его значения в $k$ точках, причём, используя меньшее число точек, однозначно восстановить исходный многочлен не получится. Количество же различных точек многочлена не ограничено (на практике оно ограничивается размером числового поля $G$ , в котором ведутся расчёты).

Кратко данный алгоритм можно описать следующим образом. Пусть дано конечное поле $G$ . Зафиксируем $n$ различных ненулевых известных элементов данного поля. Каждый из этих элементов приписывается определённому члену группы. Далее выбирается произвольный набор из $t$ элементов поля $G$ , из которых составляется многочлен $f (x)$ над полем $G$ степени $t - 1, 1 < t \leq n$ . После получения многочлена вычисляем его значение в несекретных точках и сообщаем полученные результаты соответствующим членам группыШаблон:Sfn.

Чтобы восстановить секрет, можно воспользоваться интерполяционной формулой, например формулой Лагранжа.

Важным достоинством схемы Шамира является то, что она легко масштабируема Шаблон:Sfn. Чтобы увеличить число пользователей в группе, необходимо лишь добавить соответствующее число несекретных элементов к уже существующим, при этом должно выполняться условие $r_{i} \neq r_{j}$ при $i \neq j$ . В то же время, компрометация одной части секрета переводит схему из $(n, t)$ -пороговой в $(n - 1, t - 1)$ -пороговую, при этом не раскрывая никакой информации о самом секрете.

Схема Шамира является одной из самых популярных пороговых схем разделения секрета. Данная схема, в частности, обладает свойством совершенности (доли любой неправомочной коалиции не позволяют получить какой-либо информации о секрете), идеальности (число битов, содержащихся в каждой доле секрета, равно числу битов, содержащихся в самом секрете), расширяемости (число владельцев долей секрета может быть в любой момент увеличено, при этом количество частей секрета, необходимых для восстановления секрета, останется неизменным) и т. д.Шаблон:Sfn Данная схема активно применяется в безопасных многосторонних вычислениях (например, в протоколе BGW)

Схема Блэкли

Шаблон:Main Две непараллельные прямые на плоскости пересекаются в одной точке. Любые две некомпланарные плоскости пересекаются по одной прямой, а три некомпланарные плоскости в пространстве пересекаются лишь в единственной точке. В общем случае, n n-мерных гиперплоскостей всегда пересекаются в одной точке. Одна из координат этой точки будет секретом. Тогда если закодировать секрет как несколько координат точки, то по одной доле секрета (одной гиперплоскости) можно получить какую-то информацию о секрете, то есть о взаимозависимости координат точки пересечения.


Схема Блэкли в трёх измерениях: каждая доля секрета — это плоскость, а секрет — это одна из координат точки пересечения плоскостей. Двух плоскостей недостаточно для определения точки пересечения, но достаточно для получения дополнительной информации об этой точке.

С помощью схемы БлэклиШаблон:Sfn можно создать (t,Шаблон:Nbspn)-схему разделения секрета для любых t и n: для этого надо использовать размерность пространства, равную t, и каждому из n игроков дать одну гиперплоскость, проходящую через секретную точку. Тогда любые t из n гиперплоскостей будут однозначно пересекаться в секретной точке.

Схема Блэкли менее эффективна, чем схема Шамира: в схеме Шамира каждая доля такого же размера, как и секрет, а в схеме Блэкли каждая доля в t раз больше. Существуют улучшения схемы Блэкли, позволяющие повысить её эффективность.

Схема Блэкли обладает свойством идеальности и свойством линейности, при этом эта схема является обобщением схемы Шамира. В некоторых случаях схема Блэкли может обладать свойством совершенности.

Схемы, основанные на китайской теореме об остатках

Шаблон:Main В 1983 году Шаблон:Iw, Асмут и Блум предложили две схемы разделения секрета, основанные на китайской теореме об остатках. Для некоторого числа (в схеме Миньотта это сам секрет, в схеме Асмута — Блума — некоторое производное число) вычисляются остатки от деления на последовательность чисел, которые раздаются сторонам. Благодаря ограничениям на последовательность чисел, восстановить секрет может только определённое число сторонШаблон:Sfn Шаблон:Sfn.

Пусть количество пользователей в группе равно $n$ . В схеме Миньотта выбирается некоторое множество попарно взаимно простых чисел ${m_{1}, m_{2}, . . ., m_{n}}$ таких, что произведение $k - 1$ наибольших чисел меньше, чем произведение $k$ наименьших из этих чисел. Пусть эти произведения равны $M$ и $N$ , соответственно. Число $k$ называется порогом для конструируемой схемы по множеству ${m_{1}, m_{2}, . . ., m_{n}}$ . В качестве секрета выбирается число $S$ такое, для которого выполняется соотношение $M < S < N$ . Части секрета распределяются между участниками группы следующим образом: каждому участнику выдаётся пара чисел $(r_{i}, m_{i})$ , где $r_{i} \equiv S (\mod m_{i})$ .

Чтобы восстановить секрет, необходимо объединить $t \geq k$ фрагментов. В этом случае получим систему сравнений вида $x \equiv r_{i} (\mod m_{i})$ , множество решений которой можно найти, используя китайскую теорему об остатках. Секретное число $S$ принадлежит этому множеству и удовлетворяет условию $S < m_{1} \cdot m_{2} \cdot . . . \cdot m_{t}$ . Также несложно показать, что если число фрагментов меньше $k$ , то, чтобы найти секрет $S$ , необходимо перебрать порядка $\frac{N}{M}$ целых чисел. При правильном выборе чисел $m_{i}$ такой перебор практически невозможно реализовать. К примеру, если разрядность $m_{i}$ будет от 129 до 130 бит, а $k < 15$ , то соотношение $\frac{N}{M}$ будет иметь порядок $2^{100}$ Шаблон:Sfn.

Схема Асмута — Блума является доработанной схемой Миньотта. В отличие от схемы Миньотта, её можно построить в таком виде, чтобы она была совершеннойШаблон:Sfn.

Схемы, основанные на решении систем уравнений

Шаблон:Main В 1983 году Карнин, Грин и Хеллман предложили свою схему разделения секрета, которая основывалась на невозможности решить систему с $m$ неизвестными, имея менее $m$ уравненийШаблон:Sfn.

В рамках данной схемы выбираются $n + 1$ $m$ -мерных векторов $V_{0}, V_{1}, . . ., V_{n}$ так, чтобы любая матрица размером $m \times m$ , составленная из этих векторов, имела ранг $m$ . Пусть вектор $U$ имеет размерность $m$ .

Секретом в схеме является матричное произведение $U^{T} V_{0}$ . Долями секрета являются произведения $U^{T} V_{i}, 1 \leq i \leq n$ .

Имея любые $m$ долей, можно составить систему линейных уравнений размерности $m \times m$ , неизвестными в которой являются коэффициенты $U$ . Решив данную систему, можно найти $U$ , а имея $U$ , можно найти секрет. При этом система уравнений не имеет решения в случае, если долей меньше, чем $m$ ^[2].

Способы обмана пороговой схемы

Существуют несколько способов нарушить протокол работы пороговой схемы:

владелец одной из долей может помешать восстановлению общего секрета, отдав в нужный момент неверную (случайную) долюШаблон:Sfn.
злоумышленник, не имея доли, может присутствовать при восстановлении секрета. Дождавшись оглашения нужного (порогового) числа долей, он быстро восстанавливает секрет самостоятельно и генерирует ещё одну долю, после чего предъявляет её остальным участникам. В результате он получает доступ к секрету и остаётся непойманнымШаблон:Sfn. Имея секрет в моменте, злоумышленник может распорядиться им сразу, либо подождать достаточное для отвода подозрений количество времени и использовать секрет позднее.

Также существуют другие возможные нарушения работы, не связанные с особенностями реализации схемы:

злоумышленник может сымитировать ситуацию, при которой необходимо раскрытие секрета, тем самым выведав доли всех участников или их частиШаблон:Sfn.

См. также

Примечания

Шаблон:Примечания

Литература

Шаблон:^

[1] Шаблон:Статья

[:1-2] Шаблон:Книга

[1]

[2]

Разделение секрета

Содержание

Простейший пример схемы разделения секрета