Определение 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₀.