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

Начнем с формальной математической модели. Имеется 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₀.