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

Введение - часть 2


История СРС начинается с 1979 года, когда эта проблема была поставлена и во многом решена Г. Блейкли [] и А. Шамиром [] для случая пороговых -СРС (т.е. разрешенными множествами являются любые множества из или более элементов). Особый интерес вызвали так называемые , т.е. такие, где ``размер'' информации, предоставляемой участнику, не больше ``размера'' секрета (а меньше, как было показано, он и не может быть). Оказалось [], что любой такой СРС соответствует (определение, что это такое, см. в разделе ) и, следовательно, не для любой структуры доступа возможно идеальное разделение секрета. С другой стороны, было показано, что для любого набора разрешенных множеств можно построить совершенную СРС, однако известные построения весьма ``неэкономны''. В данной статье рассматриваются алгебро-геометрические и комбинаторные задачи, возникающие при математическом анализе ``схем, разделяющих секрет''. Вот пример одной из таких задач.

Будем говорить, что семейство подпространств

конечномерного векторного пространства над полем удовлетворяет свойству ``все или ничего'', если для любого множества линейная оболочка подпространств либо содержит подпространство целиком, либо пересекается с ним только по вектору . В разделе  мы увидим, что такое семейство задает ``линейную'' СРС, у которой множество является разрешенным, если и только если линейная оболочка подпространств содержит подпространство целиком. В связи с этим понятием возникает ряд вопросов. Например, если поле конечно () и все подпространства одномерны, то каково максимально возможное число участников для линейных пороговых -СРС (1$" width="42" height="29" >)? Иначе говоря, каково максимально возможное число векторов таких, что любые векторов, содержащие вектор , линейно независимы, а любые векторов, содержащие вектор , линейно зависимы. Оказывается, что это свойство эквивалентно следующему, на первый взгляд более сильному, свойству: любые векторов линейно независимы, а любые  - линейно зависимы. Такие системы векторов изучались в геометрии как -множества () в конечной проективной геометрии , в комбинаторике как ортогональные таблицы силы  и индекса , в теории кодирования как проверочные матрицы МДР кодов (подробнее см. []). В разделе  мы приведем известную конструкцию таких множеств с , а довольно старая гипотеза состоит в том, что это и есть максимально возможное , за исключением двух случаев: случая , и случая , или , когда

Next: 5.2. Разделение секрета для

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

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

Contents:




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


[an error occurred while processing this directive]