Список обозначений

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

secret sharing scheme

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

Действующими лицами схемы разделения секрета являются дилер (иногда называемый лидером) и $n$ участников (обозначаемых числами от $1$ до $n$). Задачей дилера является вычисление долей произвольного секрета и раздача их участникам. Имеется также монотонная структура доступа $(\Delta,\Gamma)$. Кроме того, пусть $S$ — непустое конечное множество, из которого выбираются секреты.

Предположим, что каждому $s\in S$ поставлена в соответствие случайная величина $\widetilde\sigma(s)$, принимающая значения в множестве вида $S_1\times\dots\times S_n$, где множества $S_i$ конечны. Через $\widetilde\sigma_i(s)$, где $i\in\{1,\dots,n\}$, будет обозначаться $i$-й элемент последовательности $\widetilde\sigma(s)$, а через $\widetilde\sigma_I(s)$, где $I\subseteq\{1,\dots,n\}$, — последовательность $(\widetilde\sigma_i(s)\,|\, i\in I)$. Подчеркнем, что здесь случайные величины $\widetilde\sigma_i(s)$ не предполагаются независимыми. Смысл случайной величины $\widetilde\sigma(s)$ состоит в том, что ее случайное значение дилер использует в качестве набора долей секрета $s\in S$. После выбора такого значения $(s_1,\dots,s_n)$ дилер посылает $s_i$ $i$-му участнику в качестве доли этого участника. Тогда коалиция участников $I$ получает $(s_i\,|\, i\in I)$, являющееся случайным значением $\widetilde\sigma_I(s)$.

Схему разделения секрета можно отождествить с семейством случайных величин $(\widetilde\sigma(s)\,|\, s\in S)$. Каким условиям должно удовлетворять это семейство? Во-первых, нужно, чтобы произвольная разрешенная коалиция участников могла по своим долям однозначно восстановить секрет. Это условие формализуется следующим образом: $\mathop{\mathrm{supp}}\widetilde\sigma_I(s)\cap\mathop{\mathrm{supp}}\widetilde\sigma_I(s’)=\varnothing$ для любого $I\in\Gamma$ и любых различных $s,s’\in S$. Во-вторых, произвольная запрещенная коалиция участников не должна иметь возможность по своим долям найти секрет. Это условие чаще всего формализуют в следующем наиболее сильном смысле: для любых $J\in\Delta$ и $s,s’\in S$ случайные величины $\widetilde\sigma_J(s)$ и $\widetilde\sigma_J(s’)$ распределены одинаково. Последнее условие означает, что случайное значение $\widetilde\sigma_J(s)$ при $J\in\Delta$ не содержит никакой информации о $s$. Схемы разделения секрета, удовлетворяющие этому условию, называются совершенными. Именно совершенные схемы разделения секрета обычно рассматриваются в литературе.

Схема разделения секрета называется идеальной, если $\#S_i=\#S$ для любого $i\in\{1,\dots,n\}$. Известно, что если \begin{equation}\label{e:JDeltaJiGamma} \exists\,J\in\Delta J\cup\{i\}\in\Gamma, \end{equation} то $\#S_i\geqslant\#S$ ($i\in\{1,\dots,n\}$). Для справедливости последнего неравенства схема разделения секрета даже не обязана быть совершенной, а должна лишь удовлетворять более слабому условию $\bigcap_{s\in S}\mathop{\mathrm{supp}}\widetilde\sigma_J(s)\ne\varnothing$ при $J\in\Delta$. В то же время если $\Delta\cup\Gamma$ совпадает с множеством всех подмножеств $\{1,\dots,n\}$, то участники $i$, не удовлетворяющие условию \eqref{e:JDeltaJiGamma}, в некотором смысле несущественны для схемы разделения секрета и могут быть исключены из нее (см. [1]). Это показывает, что при некоторых предположениях в идеальной схеме разделения секрета мощности множеств $S_i$ являются минимально возможными.

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

Введение в теорию схем разделения секрета можно найти в гл. 5 книги [1]. См. также пионерские работы [2] и [3].

Пример 1 схема Шамира; см. [3]
Пусть $(\Delta,\Gamma)$ — пороговая структура доступа с порогом $t$. Общедоступными параметрами схемы Шамира являются конечное поле $F$ из более чем $n$ элементов и различные ненулевые элементы $a_1,\dots,a_n$ этого поля. Тогда $S=S_1=\dots=S_n=F$ и \[ \widetilde\sigma(s)=(s,\widetilde r_1,\dots,\widetilde r_t) \begin{pmatrix}1&\ldots&1\\a_1&\ldots&a_n\\ \vdots&\vdots&\vdots\\a_1^t&\ldots&a_n^t \end{pmatrix}\quad(s\in F), \] где $\widetilde r_1,\dots,\widetilde r_t$ — независимые случайные величины, распределенные равномерно на $F$. Схема Шамира является совершенной и идеальной.

Литература

  • [1] «Введение в криптографию» 2012
  • [2] Blakley, G. R. «Safeguarding cryptographic keys» 1979
  • [3] Shamir, A. «How to share a secret» 1979

Адрес редакции сайта: dialogus@cryptography.ru
© При копировании материалов ссылка на авторов,
© а при их отсутствии — на сайт, обязательна