Разделение секрета для произвольных структур доступа

Начнем с формальной математической модели. Имеется n+1 множество S₀, S₁, …, S_n и (совместное) распределение вероятностей P на их декартовом произведении S = S₀ * …* S_n. Соответствующие случайные величины обозначаются через S_i. Имеется также некоторое множество Г подмножеств множества {1, …, n}, называемое структурой доступа.

Определение 18.1

Пара (P,S) называется совершенной вероятностной СРС, реализующей структуру доступа Г, если

P(S₀ = c₀ | S_i = c_i, i Î A) Î {0, 1} для A Î Г, (18.1)

P(S0 = c0 | Si = ci, i Î A) = P(S0 = c0) для A Ï Г (18.2)

Это определение можно истолковать следующим образом. Имеется множество S₀ всех возможных секретов, из которого секрет s₀ выбирается с вероятностью p(s₀), и имеется СРС, которая “распределяет” секрет s₀ между n участниками, посылая “проекции” s₁, …, s_n секрета с вероятностью P_S0 (s₁, …, s_n). Отметим, что і-ый учасник получает свою “проекцию” s_i Î S_i и не имеет информации о значениях других “проекций”, однако знает все множества S_i, а также оба распределения вероятностей p(s₀) и P_S0(s₁, …, s_n). Эти два распределения могут быть эквивалентны заменене на одно: P(s₀, s₁, …, s_n) = p(_S0)P_S0(s₁, …, s_n), что и было сделано выше. Цель СРС, как указывалось во введении, состоит в том, чтобы:

· участники из разрешенного множества A (т. е. A Î Г) вместе могли бы однозначно восстановить значение секрета — это отражено в свойстве (18.1);

· участники, образующие неразрешенное множество А (А Ï Г), не могли бы получить дополнительную информацию об s₀, т.е., чтобы вероятность того, что значение секрета S₀ = c₀, не зависела от значений “проекций” S_i при і Î А — это свойство (18.2).

Замечание о терминологии. В англоязычной литературе для обозначения “порции” информации, посылаемой участнику СРС, были введены термины share (А. Шамир) и shadow (Г. Блейкли). Первый термин оказался наиболее популярным, но неадекватная (во всех смыслах) замена в данной работе акции на проекцию может быть несколько оправдана следующим примером.

Пример 18.1. Множество S₀ всех возможных секретов состоит из 0, 1 и 2, “представленных”, соответственно: шаром; кубом, ребра которого параллельны осям координат; цилиндром, образующие которого параллельны оси Z. При этом диаметры шара и основания цилиндра, и длины ребра куба и образующей цилиндра, равны. Первый участник получает в качестве своей “доли” секрета его проекцию на плоскость XY, а второй — на плоскость XZ. Ясно, что вместе они однозначно восстановят секрет, а порознь — нет. Однако эта СРС не является совершенной, так как любой из участников получает информацию о секрете, оставляя только два значения секрета как возможные при данной проекции (например, если проекция — квадрат, то шар невозможен).

Еще одно замечание. Элемент (участник) x Î {1, …, n} называется несущественным (относительно Г), если для любого неразрешенного множества А множество А È x также неразрешенное. Очевидно, что несущественные участники настолько несущественны для разделения секрета, что им просто не нужно посылать никакой информации. Поэтому далее, без ограничения общности, рассматриваются только такие структуры доступа Г, для которых все элементы являются существенными. Кроме того, естественно предполагать, что Г является монотонной структурой, т.е. из А Ì В, А Î Г следует В Î Г.

Пример 18.2. Рассмотрим простейшую структуру доступа — (n,n)-пороговую схему, т.е. все участники вместе могут восстановить секрет, а любое подмножество участников не может получить дополнительной информации о секрете. Будем строить идеальную СРС, выбирая и секрет, и его проекции из группы Z_q вычетов по модулю q, т.е. S₀ = S₁ = … = S_n = Z_q. Дилер генерирует n–1 независимых равномерно распределенных на Z_q случайных величин х_i и посылает і-му учаснику (і = 1,..., n-1) его “проекцию” s_i = x_i, а n-му участнику — s_n = s₀ – (s₁ + … + s_n-1). Кажущееся “неравноправие” n-ого участника тут же исчезает, если мы выпишем распределение P_S0(s₁,…, s_n), которое очевидно равно 1/qn–1, если s₀ = s₁ + … + s_n, а в остальных случаях равно 0. Теперь легко проверяется и свойство (18.2), означающее в данном случае независимость случайной величины S₀ от случайных величин {S_i: і Î А} при любом собственном подмножестве А.

Данное выше определение СРС, оперирующее понятием распределение вероятностей, ниже переведено, почти без потери общности, на комбинаторный язык, который представляется более простым для понимания. Произвольная M * (n + 1)-матрица V, строки которой имеют вид v = (v₀, v₁, …, v_n), где v_i Î S_i, называется матрицей комбинаторной СРС, а ее строки — правилами распределения секрета. Для заданного значения секрета s₀ дилер СРС случайно и равновероятно выбирает строку v из тех строк матрицы V, для которых значение нулевой координаты равно s₀.

Определение 18.2

Матрица V задает совершенную комбинаторную СРС, реализующую структуру доступа Г, если, во-первых, для любого множества А Î Г нулевая координата любой строки матрицы V однозначно определяется значениями ее координат из множества А, и, во-вторых, для любого множества А Ï Г и любых заданных значений координат из множества А число строк матрицы V с данным значением α нулевой координаты не зависит от α.

Сопоставим совершенной вероятностной СРС, задаваемой парой (P, S), матрицу V, состоящую из строк s Î S, таких что P(s) > 0. Заметим, что если в определении 1 положить все ненулевые значения P одинаковыми, а условия (18.1) и (18.2) переформулировать на комбинаторном языке, то получится определение 2. Это комбинаторное определение несколько обобщается, если допустить в матрице V повторяющиеся строки, что эквивалентно вероятностному определению 1, когда значения вероятностей P(s) — рациональные числа.

Продолжение примера 18.2 (из предыдущего раздела). Переформулируем данную выше конструкцию (n,n)-пороговой СРС на комбинаторном языке. Строками матрицы V являются все векторы s такие, что s₀ + s₁ + … + s_n = 0. Очевидно, что матрица V задает совершенную комбинаторную СРС для Г={1, …, n}, так как для любого собственного подмножества А Ì {1, …, n} и любых заданных значений координат из множества А число строк матрицы V с данным значением нулевой координаты равно q^{n–1 – |A|}.

Удивительно, но простой схемы примера 2 оказывается достаточно, чтобы из нее, как из кирпичиков, построить совершенную СРС для произвольной структуры доступа. А именно, для всех разрешенных множеств, т.е. для А Î Г, независимо реализуем описанную только что пороговую (|A|, |A|)-СРС, послав тем самым і-му учаснику cтолько “проекций” s_i^A, скольким разрешенным множествам он принадлежит. Это словесное описание несложно перевести на комбинаторный язык свойств матрицы V и убедиться, что эта СРС совершенна. Как это часто бывает, “совершенная” не значит “экономная”, и у данной СРС размер “проекции” оказывается, как правило, во много раз больше, чем размер секрета. Эту схему можно сделать более экономной, так как достаточно реализовать пороговые (|A|, |A|)-СРС только для минимальных разрешенных множеств А, т.е. для А Î Г_min, где Г_min — совокупность минимальных (относительно включения) множеств из Г. Тем не менее, для пороговой (n, n/2)-СРС размер “проекции” (измеренный, например, в битах) будет в C_n^n/2 ~ 2n/ раз больше размера секрета (это наихудший случай для рассматриваемой конструкции). С другой стороны, как мы убедимся чуть позже, любая пороговая структура доступа может быть реализована идеально, т.е. при совпадающих размерах “проекции” и секрета. Поэтому естественно возникает вопрос о том, каково максимально возможное превышение размера “проекции” над размером секрета для наихудшей структуры доступа при наилучшей реализации. Формально, R(n) = max R(Г), где max берется по всем структурам доступа Г на n участниках, а R(Г) = min max, где min берется по всем СРС, реализующим данную структуру доступа Г, а max — по і = 1,..., n. Приведенная конструкция показывает, что R(n) £ C_n^n/2n. С другой стороны, R(n) ³ n/log n. Такой огромный “зазор” между верхней и нижней оценкой дает достаточный простор для исследований (предполагается, что R(n) зависит от n экспоненциально).