называется совершенной вероятностной СРС, реализующей
Пара (P,S) называется совершенной вероятностной СРС, реализующей структуру доступа Г, если
P(S0 = c0
| Si = ci, i Î A) Î {0, 1} для A Î Г, (18.1)
P(S0 = c0 | Si = ci, i Î A) = P(S0 = c0) для A Ï Г (18.2)
Это определение можно истолковать следующим образом. Имеется множество S0 всех возможных секретов, из которого секрет s0 выбирается с вероятностью p(s0), и имеется СРС, которая “распределяет” секрет s0 между n участниками, посылая “проекции” s1, …, sn секрета с вероятностью PS0 (s1, …, sn). Отметим, что і-ый учасник получает свою “проекцию” si Î Si и не имеет информации о значениях других “проекций”, однако знает все множества Si, а также оба распределения вероятностей p(s0) и PS0(s1, …, sn). Эти два распределения могут быть эквивалентны заменене на одно: P(s0, s1, …, sn) = p(S0)PS0(s1, …, sn), что и было сделано выше. Цель СРС, как указывалось во введении, состоит в том, чтобы:
- участники из разрешенного множества A (т. е. A Î Г) вместе могли бы однозначно восстановить значение секрета — это отражено в свойстве (18.1);
- участники, образующие неразрешенное множество А (А Ï Г), не могли бы получить дополнительную информацию об s0, т.е., чтобы вероятность того, что значение секрета S0
= c0, не зависела от значений “проекций” Si при і Î А — это свойство (18.2).
Замечание о терминологии. В англоязычной литературе для обозначения “порции” информации, посылаемой участнику СРС, были введены термины share (А. Шамир) и shadow (Г. Блейкли). Первый термин оказался наиболее популярным, но неадекватная (во всех смыслах) замена в данной работе акции на проекцию может быть несколько оправдана следующим примером.
Пример 18.1. Множество S0 всех возможных секретов состоит из 0, 1 и 2, “представленных”, соответственно: шаром; кубом, ребра которого параллельны осям координат; цилиндром, образующие которого параллельны оси Z. При этом диаметры шара и основания цилиндра, и длины ребра куба и образующей цилиндра, равны.
Матрица 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 такие, что s0 + s1 + … + sn = 0. Очевидно, что матрица V задает совершенную комбинаторную СРС для Г={1, …, n}, так как для любого собственного подмножества А Ì {1, …, n} и любых заданных значений координат из множества А число строк матрицы V с данным значением нулевой координаты равно qn–1 – |A|.
Удивительно, но простой схемы примера 2 оказывается достаточно, чтобы из нее, как из кирпичиков, построить совершенную СРС для произвольной структуры доступа. А именно, для всех разрешенных множеств, т.е. для А Î Г, независимо реализуем описанную только что пороговую (|A|, |A|)-СРС, послав тем самым і-му учаснику cтолько “проекций” siA, скольким разрешенным множествам он принадлежит. Это словесное описание несложно перевести на комбинаторный язык свойств матрицы V и убедиться, что эта СРС совершенна. Как это часто бывает, “совершенная” не значит “экономная”, и у данной СРС размер “проекции” оказывается, как правило, во много раз больше, чем размер секрета.
Матрица V задает БД- совершенную СРС, реализующую структуру доступа Г, если
||VAÈ0|| = ||VA|| × ||V0||?Г (А), (18.4)
где ?Г
(А) = 0, если А Î Г, и ?Г
(А) = 1 в противном случае.
Это определение отличается от определений 1 и 2 тем, что на неразрешенные множества А накладываются довольно слабое условие, а именно, если множество строк V с данными значениями координат из множества А непусто, то все возможные значения секрета встречаются в нулевой координате этих строк (без требований “одинаково часто” как в комбинаторном определении 2 или же “с априорной вероятностью” как в вероятностном определении 1). Легко видеть, что матрица любой совершенной вероятностной СРС задает БД-совершенную СРС, но обратное неверно.
Для произвольной комбинаторной СРС, задаваемой матрицей V, определим на множествах А Í {0, 1, …, n} функцию h(A) = logq
||VA||, где q = |S0|. Легко проверить, что max{h(A), h(B)} £ h(A È B) £ h(A) + h(B) для любых множеств А и В, а условие (184) может быть переписано в виде
hq(VAÈ0) = hq(VA) + ?Г (А) hq(V0)
Лемма. Для любой БД-совершенной СРС если А Ï Г и {A È i} Î Г, то h(i) ³ h(0).
Доказательство. По условиям леммы
h(A È 0) = h(A) + h(0) и h(A È i È 0) = h(A È і). Следовательно,
h(A) + h(i) ³ h (A È і) = h (A È і È 0) ³ h(A È 0) = h(A) + h(0)
Так мы предполагаем, что все точки і Î {1, …, n} существенные, т.е. для любого і найдется подмножество А такое, что А Ï Г и {A È і} Î Г, то из леммы вытекает
Следствие. Для любой БД-совершенной СРС |Si| ³ |S0| для всех і = 1, ..., n.
Следствие означает, как отмечалось выше, что для совершенных СРС “размер” проекции не может быть меньше “размера” секрета. Поэтому БД-совершенная СРС называется идеальной, если |Si| = |S0| для всех і = 1, ..., n.
Замечание. Неравенство |Si| ³ |S0| справедливо и для совершенных вероятностных СРС, поскольку их матрицы задают БД-совершенные СРС.
