Problems of almost threshold secret sharing schemes.pdf В настоящее время вопросы, связанные с криптографическими методами защитыинформации и математическими задачами криптологии, являются чрезвычайно важ-ными [1]. Такими, например, являются задачи делегирования прав, разграничения до-ступа к информации и разделения секрета. Одними из основных криптографическихпримитивов в теории и практике защиты информации являются схемы разделениясекрета (СРС).Основная идея СРС состоит в предоставлении участникам долей секрета такимобразом, чтобы только заранее заданные разрешённые коалиции участников моглиоднозначно восстановить секрет, а неразрешённые не получали никакой дополнитель-ной к имеющейся априорной информации о возможном значении секрета [2].В работе [3] описаны идеальные почти пороговые СРС, основанные на эллипти-ческих кривых и позволяющие реализовать более сложную, чем у пороговых СРС,структуру доступа [4], при которой не все n-элементные множества участников могутоднозначно восстановить секрет. Эллиптическая кривая и точки на ней используютсядля параметризации участников. В работе [5] доказано, что можно реализовать та-кую СРС с бесконечным количеством участников, где всюду плотность расположениярациональных точек на эллиптической кривой выступает аналогом совершенности.Разрешённые коалиции идеальной совершенной схемы разделения секрета опреде-ляются циклами некоторого связного матроида, изучение которого и даёт структурудоступа [2], в данном случае матроиды будут почти пороговыми [3].Если в структуре доступа СРС есть незаменимые участники, т. е. те, которые вхо-дят во все разрешённые коалиции, то основная идея СРС - восстановление секретав отсутствие каких-либо участников - не работает. Незаменимость участника означа-ет, что, какова бы ни была доля секрета, выдаваемая этому участнику, без его участияв восстановлении секрета не обойтись. Незаменимые участники фактически обладаюттеми же правами, что и дилер, хранитель секрета, и ассоциируются с ним. Они облада-ют «правом вето», т. е. без них ничего не решится. Итак, для разделения незаменимыхучастников необходимо, чтобы был цикл, содержащий по отдельности каждого из этихдвух участников. Этим доказаноУтверждение 1. В матроиде, соответствующем СРС, нет незаменимых участни-ков тогда и только тогда, когда для любых x = y существует разделяющий их цикл C,т. е. x Е C, y Е C.Назовём такие матроиды разделяющими.Матроид назовем почти пороговым, если все его циклы имеют мощность n, но, воз-можно, не все его n-элементные подмножества - циклы. Путём комбинаторных рас-суждений доказаноУтверждение 2. Для мощностей цикла 1, 2 и 3 связного почти порогового непо-рогового матроида не существует.Разграничение доступа к информации в компьютерных системах естественным об-разом, путём рассмотрения битовых строк, приводит к бинарным матроидам, т. е. мат-роидам, реализующимся как векторные над полями характеристики два. На этом путиудаётся построить связный почти пороговый непороговый матроид с мощностью цик-ла 4. Рассмотрением фактор-групп группы кода СРС получена обобщающаяТеорема 1. Бинарные связные разделяющие почти пороговые матроиды исчер-пываются матроидами, соответствующими кодам Рида - Маллера первого порядка.

Скачать электронную версию публикации