Определение 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экспоненциально).