Введение в криптографию
[an error occurred while processing this directive]

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


Сопоставим совершенной вероятностной СРС, задаваемой парой , матрицу состоящую из строк , таких что 0$" width="66" height="31" >. Заметим, что если в положить все ненулевые значения одинаковыми, а условия и

переформулировать на комбинаторном языке, то получится . Это комбинаторное определение несколько обобщается, если допустить в матрице повторяющиеся строки, что эквивалентно вероятностному , когда значения вероятностей - рациональные числа.

Пример 2. (продолжение)  

Переформулируем данную выше конструкцию -пороговой СРС на комбинаторном языке. Строками матрицы являются все векторы такие, что . Очевидно, что матрица задает совершенную комбинаторную СРС для

, так как для любого собственного подмножества и любых заданных значений координат из множества число строк матрицы с данным значением нулевой координаты равно .

Удивительно, но простой схемы примера 2 оказывается достаточно, чтобы из нее, как из кирпичиков, построить совершенную СРС для произвольной структуры доступа. А именно, для всех разрешенных множеств, т.е. для , независимо реализуем описанную только что пороговую -СРС, послав тем самым -му участнику столько ``проекций''  , скольким разрешенным множествам он принадлежит. Это словесное описание несложно перевести на комбинаторный язык свойств матрицы и убедиться, что эта СРС совершенна. Как это часто бывает, ``совершенная'' не значит ``экономная'', и у данной СРС размер ``проекции'' оказывается, как правило, во много раз больше, чем размер секрета. Эту схему можно сделать более экономной, так как достаточно реализовать пороговые -СРС только для минимальных разрешенных множеств , т.е. для , где - совокупность минимальных (относительно включения) множеств из . Тем не менее, для пороговой -СРС размер ``проекции'' (измеренный, например, в битах) будет в раз больше размера секрета (это наихудший случай для рассматриваемой конструкции). С другой стороны, как мы убедимся чуть позже, любая пороговая структура доступа может быть реализована идеально, т.е. при совпадающих размерах ``проекции'' и секрета. Поэтому естественно возникает вопрос о том, каково максимально возможное превышение размера ``проекции'' над размером секрета для наихудшей структуры доступа при наилучшей реализации. Формально, , где берется по всем структурам доступа на участниках, а , где берется по всем СРС, реализующим данную структуру доступа , а - по . Приведенная конструкция показывает, что

. С другой стороны, как было доказано лишь недавно [], . Такая огромная ``щель'' между верхней и нижней оценкой дает, по нашему мнению, достаточный простор для исследований (автор предполагает, что растет экспоненциально от ).

Next: 5.3. Линейное разделение секрета

Up: 5. Математика разделения секрета

Previous: 5.1. Введение

Contents:




- Начало -  - Назад -  - Вперед -


[an error occurred while processing this directive]