Введение в криптографию




Идеальное разделение секрета и матроиды - часть 3


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

В связи с теоремой возникает несколько естественных вопросов. Прежде всего, не порождают ли идеальные СРС все матроиды? Нет, например, матроид Вамоса не может быть получен как матроид идеальной СРС []. С другой стороны, линейные матроиды есть ни что иное как рассмотренные в разделе  идеальные одномерные линейные СРС. В связи с этим возникает вопрос о существовании структуры доступа , которую невозможно реализовать в виде идеальной одномерной линейной СРС, но можно в виде идеальной многомерной линейной СРС. Недавно такой пример был построен [], и, значит, мы можем говорить о многомерных линейных матроидах как классе матроидов более общем, чем линейные.

Итак, идеальных СРС больше, чем линейных матроидов, но меньше, чем всех матроидов. Уточнить, ``насколько больше'', представляется довольно сложной задачей. В частности, существует ли идеально реализуемая структура доступа , которую невозможно реализовать как идеальную линейную многомерную СРС?

Next: Литература к главе 5

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

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

Contents:




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