Методы и средства защиты информации



              

Математика разделения секрета - часть 2


Неформально говоря, схема, разделяющая секрет (СРС) позволяет “распределить” секрет между n участниками таким образом, чтобы заранее заданные разрешенные множества участников могли однозначно восстановить секрет (совокупность этих множеств называется структурой доступа), а неразрешенные — не получали никакой дополнительной к имеющейся априорной информации о возможном значении секрета. СРС с последним свойством называются совершенными.

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

Будем говорить, что семейство подпространств {L0, …, Ln} конечномерного векторного пространства L над полем K удовлетворяет свойству “все или ничего”, если для любого множества A Ì {1, …, n} линейная оболочка подпространств {La: a Î A} либо содержит подпространство L0 целиком, либо пересекается с ним только по вектору 0. В подразделе “Линейное разделение секрета” мы увидим, что такое семейство задает “линейную” СРС, у которой множество A Ì {1, …, n} является разрешенным, если и только если линейная оболочка подпространств {La: a Î A} содержит подпространство L0 целиком. В связи с этим понятием возникает ряд вопросов. Например, если поле K конечно (|K| = q) и все подпространства {L0, …, Ln} одномерны, то каково максимально возможное число участников n для линейных пороговых (n, k)-СРС (k > 1)? Иначе говоря, каково максимально возможное число векторов {h0, …, hn} таких, что любые k векторов, содержащие вектор h0, линейно независимы, а любые k + 1 векторов, содержащие вектор h0, линейно зависимы.Оказывается, что это свойство эквивалентно следующему, на первый взгляд более сильному, свойству: любые k векторов линейно независимы, а любые k + 1 — линейно зависимы. Такие системы векторов изучались в геометрии как N-множества (N = n + 1) в конечной проективной геометрии PG(k–1, q), в комбинаторике — как ортогональные таблицы силы k и индекса ? = 1, в теории кодирования — как проверочные матрицы МДР кодов. В подразделе “Линейное разделение секрета” мы приведем известную конструкцию таких множеств с N = q + 1. Существует довольно старая гипотеза о том, что это и есть максимально возможное N, за исключением двух случаев: случая q < k, когда N = k + 1, и случая q = 2m, k = 3 или k = q – 1, когда N = q + 2.




Содержание  Назад  Вперед