Информационная безопасность является одной из составляющих национальной безопасности РФ и оказывает влияние на различные сферы жизнедеятельности общества и государства [3]. Поэтому вопросы, связанные с зашитой информации и с соответствующими математическими задачами, являются чрезвычайно важными. Такими, например, являются задачи разграничения доступа к информации [4] и разделения секрета, в том числе со сложной структурой доступа.
Основная идея схемы разделения секрета (СРС) состоит [2,8] в раздаче долей секрета участникам таким образом, чтобы заранее заданные коалиции участников (разрешенные коалиции) могли однозначно восстановить секрет (совокупность этих множеств называется структурой доступа), а неразрешенные - не получали никакой дополнительной, к имеющейся априорной, информации о возможном значении секрета. Такие СРС называются совершенными. Идеальными называются СРС, где размер доли секрета, предоставляемый участнику, не больше самого размера секрета. Если разрешенными коалициями являются любые множества из n или более элементов, то такие СРС называются пороговыми «n из N» СРС, где N - количество всех участников. В работе [6] ранее были описаны СРС при помощи многочленов на эллиптических кривых, в которой минимальные разрешённые коалиции участников имели близкую мощность, т.е. либо n, либо n+1. Такие схемы были названы почти пороговыми. Разрешенные коалиции идеальной схемы разделения секрета определяются циклами некоторого связного матроида (см. далее), изучение которого и дает структуру доступа [2,8].
Цель данного исследования - построение классов почти пороговых идеальных совершенных схем разделения секрета и их матроидов, при помощи комбинаторных методов конечных геометрий.
Аксиоматизация матроидов
Как известно [1], на множестве H определен матроид, если некоторые его подмножества названы независимыми (остальные - зависимыми), причём удовлетворяются аксиомы матроида. Известно много вариантов аксиоматизации матроидов [1]. Например, в терминах циклов, т.е. минимальных по включению зависимых подмножеств из Н, аксиом всего две. Представляется естественным рассмотреть двойственный вариант к аксиоматизации в терминах циклов, а именно, использовать не циклы С матроида M, а его нуль-множества Z, т.е. 
, которые можно назвать «антициклами». Тогда аксиомы матроида в терминах антициклов имеют следующий вид: 1) нет антицикла в антицикле, т.е. если Z1, Z2 - антициклы, и 
, то 
; 2) если 
, 
и 
, 
- антициклы, причем , то существует такой антицикл Z, что 
.
Напомним, что матроид называется связным, если для любых двух его элементов существует содержащий их цикл. Почти пороговым СРС соответствуют матроиды, которые было естественно назвать почти пороговыми, в том смысле, что его антициклы имеют близкую мощность.
Наша задача - через геометрическую интерпретацию представленных выше аксиом дать ряд конструкций почти пороговых СРС и соответствующих им матроидов.
Матроиды на проективном и аффинном пространстве
Пусть М - проективное m-мерное пространство над GF(q). Возьмем в качестве нуль-множеств Z гиперпространства в M. Как известно [7], 
и 
. Поскольку любые два гиперпространства 
и 
всегда пересекаются, т.е. 
, причем размерность 
, 
, то для любой точки 
, существует единственное гиперпространство Z, натянутое на {e} и на пересечение гиперпространств 
и 
, так что 
. А это - не что иное, как вторая аксиома матроида в терминах антициклов, которую можно назвать усиленной, т.к. существует единственное такое гиперпространство. Следовательно, вторая аксиома матроида выполняется. Первая аксиома матроида с очевидностью выполняется, т.к. размерности гиперпространств одинаковы и антицикла в антицикле быть не может. Итак, доказано
Утверждение 1. Проективное пространство M является матроидом над GF(q) с гиперпространствами в качестве антициклов.
Поскольку все циклы матроида M определяются как дополнения нуль-множеств Z, размерность которых одинакова, то отсюда вытекает
Утверждение 2. Циклы матроида в m-мерном проективном пространстве M имеют одинаковую мощность 
.
Перейдем к рассмотрению матроидов в аффинном m-мерном пространстве M над GF(q). Как известно, 
и 
. В аффинном пространстве может быть два случая пересечения гиперпространств 
и 
: 1) либо пересекаются, т.е. 
, тогда вторая аксиома матроида выполняется, что было доказано выше, как в проективном пространстве; 2) либо параллельны, т.е. , тогда это тривиальный случай и вторая аксиома матроида также выполняется, т.к. объединение двух соответствующих гиперпространствам циклов будет все пространство M. Первая аксиома матроида аналогично выполняется в обоих случаях как в проективном пространстве. Итак, доказано
Утверждение 3. Аффинное пространство M является матроидом над GF(q) с гиперпространствами в качестве антициклов.
Поскольку все циклы матроида M определяются как дополнения нуль-множеств Z, размерность которых одинакова, то отсюда вытекает
Утверждение 4. Циклы матроида в m-мерном аффинном пространстве M имеют одинаковую мощность 
.
При реализации такой СРС гиперпространства соответствуют линейным функциям, т.е. функциями вида 
, где 
и 
. Позиции кода - точки 
m-мерного пространства 
(они же - участники СРС), код состоит из тех 
-мерных векторов, т.е. функций 
, что 
для всех линейных непостоянных функций f.
Рассмотрим пример для q=3 и m=2. Построим табл. 1, описывающую циклы почти порогового матроида и проверочную матрицу H. При этом Ci соответствует функции fi (
).
Табл. 1.
|
№ функции |
f1=x2 |
f2=x1 |
f3=x1+ x2 |
f4= x1+ x2+1 |
f5= x1+ x2+2 |
f6= x2-x1 |
f7= x2-x1+1 |
f8= x2-x1+2 |
f9= x1+ 1 |
f10= x1+ 2 |
f11= x2+ 1 |
f12= x2+ 2 |
|
0 |
0 |
0 |
0 |
1 |
2 |
0 |
1 |
2 |
1 |
2 |
1 |
2 |
|
1 |
0 |
1 |
1 |
2 |
0 |
2 |
0 |
1 |
2 |
0 |
1 |
2 |
|
2 |
0 |
2 |
2 |
0 |
1 |
1 |
2 |
0 |
0 |
1 |
1 |
2 |
|
3 |
1 |
0 |
1 |
2 |
0 |
1 |
2 |
0 |
1 |
2 |
2 |
0 |
|
4 |
1 |
1 |
2 |
0 |
1 |
0 |
1 |
2 |
2 |
0 |
2 |
0 |
|
5 |
1 |
2 |
0 |
1 |
2 |
2 |
0 |
1 |
0 |
1 |
2 |
0 |
|
6 |
2 |
0 |
2 |
0 |
1 |
2 |
0 |
1 |
1 |
2 |
0 |
1 |
|
7 |
2 |
1 |
0 |
1 |
2 |
1 |
2 |
0 |
2 |
0 |
0 |
1 |
|
8 |
2 |
2 |
1 |
2 |
0 |
0 |
1 |
2 |
0 |
1 |
0 |
1 |
Итак, циклы матроида, с помощью функции выбора, определяются номерами ненулевых элементов столбцов табл. 1, построенной с помощью линейных функций: C1={3,4,5,6,7,8}, Z1={0,1,2}; C2={1,2,4,5,7,8}, Z2={0,3,6}; C3={1,2,3,4,6,8}, Z3={0,5,7}; C4={0,1,3,5,7,8}, Z4={2,4,6}; C5={0,2,4,5,6,7}, Z5={1,3,8}; C6={1,2,3,5,6,7}, Z6={0,4,8}; C7={0,2,3,4,7,8}, Z7={1,5,6}; C8={0,1,4,5,6,8}, Z8={2,3,7}; C9={0,1,3,4,6,7}, Z9={2,5,8}; C10={0,2,3,5,6,8}, Z10={1,4,7}; C11={0,1,2,3,4,5}, Z11={6,7,8}; C12={0,1,2,6,7,8}, Z6={3,4,5}. Ранг матрицы H над полем GF(3) равен трем, т.е. таблица СРС имеет 
срок.
Матроиды в схемах разделения секрета на эллиптических кривых
Как было сказано ранее, в работе [6] были описаны СРС при помощи многочленов на эллиптических кривых. В них участники параметризуются точками на эллиптической кривой, а их долями секрета являются значение секретного многочлена в этой точке на кривой. Подход этой статьи - использовать многочлен (третьей степени) на эллиптической кривой для генерации проверочной матрицы над GF(q) кода линейной СРС. Возьмем три конечные точки эллиптической кривой, находящиеся на одной прямой. Сумма этих точек будет равна нулю 0, т.е. бесконечно удаленной точке кривой [6]. Тогда по теореме о главных дивизорах [5] существует многочлен F третьей степени на эллиптической кривой с корнями в этих точках, т.е. 
(i=1,2,3). При этом эти точки могут совпадать. Таким образом, получается три случая: 1) если 
, то P1+P2+P3=0; 2) если P1=P2, то 2P1+P3=0 или, если P2=P3, то P1+2P2=0; 3) если P1=P2=P3, то 3P1=0.
Значение многочлена степени три в каждой конечной точке эллиптической кривой определяет строки проверочной матрицы H. При этом ненулевые элементы строк проверочной матрицы H определяют циклы 
векторного матроида M над GF(q), а нулевые элементы - нуль-множества Z, где М - множество конечных точек кривой над GF(q). Нуль-множества Z задаются прямыми, пересекающимися с эллиптической кривой, при этом сумма точек пересечения прямой, соответствующей нуль-множеству Z, с кривой равна нулю: если 
, то 
, и P1+P2+P3=0; если P1=P2, то 
, и либо 2P1+P3=0, либо P1+2P3=0; если P1=P2=P3, то 
, и 3P1=0.
Проверим выполнение первой аксиомы матроида в терминах антициклов. Поскольку циклы матроида определяются как дополнения нуль-множеств, то потребуем, чтобы в нуль-множествах матроида M не было одноэлементных нуль-множеств. Это означает, что на эллиптической кривой нет точек второго и третьего порядка. Тогда, если нуль-множества определяются по двум или трем различным точкам эллиптической кривой, то эти точки задают единственную прямую. Поэтому антицикла в антицикле, т.е. одной прямой внутри другой прямой, быть не может. Итак, при условии 
, т.е. нуль-множества Z определяются прямыми по двум или трем различным конечным точкам на эллиптической кривой, первая аксиома матроида выполняется.
Проверим выполнение второй аксиомы матроида в терминах циклов. Пусть 
, тогда 
и 
. Существует ли такой цикл С, что 
? Если прямые, соответствующие нуль-множествам 
и 
, не имеют общих точек пересечения на кривой 
, то объединение соответствующих циклов 
есть вся кривая без бесконечно удаленной точки кривой, т.е. 
. В этом тривиальном случае вторая аксиома матроида с очевидностью выполняется. Пусть Е - конечная точка на эллиптической кривой, тогда через нее и через любую другую точку кривой можно провести прямую, соответствующую нуль-множеству 
. Следовательно, во множестве 
есть цикл 
. Если же разные нуль-множества Z1 и Z2 пересекаются на кривой, т.е. 
, то только в одной точке, иначе они будут совпадать. Поэтому 
. При этом объединение соответствующих им циклов C1 и C2 есть вся кривая кроме бесконечно удаленной точки 0 и точки пересечения 
нуль-множеств. Итак, пусть 
, 
и 
, тогда 
. Пусть точка 
, тогда 
, и во множестве 
должен содержаться цикл - проверим это. Из 
вытекает, что прямая 
определяет нуль-множество 
, содержащее две различные точки 
и 
, так что искомым циклом будет 
. Следовательно, вторая аксиома матроида выполняется. Итак, доказано
Утверждение 5. Если на эллиптической кривой нет точек второго и третьего порядка, то множество ее конечных точек М с определенными выше через нуль-множества циклами является матроидом.
Поскольку нуль-множества матроида M определяются прямыми, которые могут иметь две или три различные точки пересечения с эллиптической кривой, то отсюда вытекает
Утверждение 6. Мощность циклов матроида М равна либо 
, если 
, либо 
, если 
, где N=|GEC(GF(q))|.
Из утверждения 6 следует, что при помощи многочлена на эллиптической кривой реализуется линейная идеальная совершенная почти пороговая СРС.
Пример реализации идеальной совершенной почти пороговой СРС при помощи эллиптических кривых над GF(3)
Рассмотрим эллиптическую кривую 
над полем GF(3). Всего эта кривая имеет 
точек, включая бесконечно удаленную, которые образуют абелеву группу. При этом группа G изоморфна 
, т.е. 
, поэтому каждую точку кривой можно сопоставить с вычетом по модулю семь. Конечным точкам соответствуют ненулевые вычеты, так что 
. В силу этого изоморфизма будем обозначать точки так: 1=(2;2), 2=(0;2), 3=(1;1), 4=(1;2), 5=(0;1), 6=(2;1)=-1. Тогда возможны три варианта: 1) P1+P2=0, degF=2; 2) 2P1+P2=0, degF=3; 3) P1+P2+P3=0, degF=3. Определим, какие нуль-множества будут соответствовать этим трём вариантам, при этом 0 не учитывается:
1) P1+P2=0, Z1={1,6}; Z2={2,5}; Z3={3,4};
2) 2P1+P2=0, Z4={1,5}; Z2={2,3}; Z6={3,1}; Z7={4,6}; Z8={5,4}; Z9={6,2};
3) P1+P2+P3=0, Z10={1,2,4}; Z11={3,5,6}={-1,-2,-4}.
Циклами матроида М будут дополнения этих нуль-множеств 
:
1) C1={2,3,4,5}; C 2={1,3,4,6}; C 3={1,2,5,6};
2) C4={2,3,4,6}; C2={1,4,5,6}; C6={2,4,5,6}; C7={1,2,3,5}; C8={1,2,3,6}; C9={1,3,4,5};
3) C10={3,5,6}; C11={1,2,4}.
Нетрудно проверить непосредственно, что обе аксиомы матроида выполняются. Приведем первый шаг реализации такой СРС - определим проверочную матрицу кода Н:
Ранг матрицы H над GF(3) равен трем, т.е. таблица СРС имеет 
срок.
Рассмотрим, как строились строки матрицы Н. Для первого случая (P1+P2=0), т.е. первые три строки матрицы H, прямая, определяющая нуль-множество, вертикальна, что даёт многочлен вида 
. Так, в первой строке 
равна абсциссе первой (или шестой) точки эллиптической кривой, так как Z1={1,6}, -1=6, т.е. 
. Далее, для каждого элемента первой строки рассчитывается значение 
, где 
- значение абсциссы точки соответствующей номеру столбца с 1 до 6.
Для второго (2P1+P2=0) и третьего (P1+P2+P3=0) случая, т.е. с четвертой по девятую строку и последние две строки соответственно, рассчитывалось значение функции 
. Так, для расчета четвертой строки матрицы H параметры k и b находятся из системы двух линейных уравнений и Z4={1,5}:
. Отсюда k=2 и b=1. Далее, для каждого элемента четвертой строки рассчитывается значение 
, где 
, 
- значение абсциссы и ординаты точки, соответствующей номеру столбца с 1 до 6. Аналогичные расчеты производились и в третьем случае.
Заключение
В данной работе рассмотрен двойственный вариант аксиоматизации матроидов с помощью антициклов - нуль-множеств. Доказано, что реализуется бесконечная серия матроидов M на m-мерном проективном и аффинном пространстве над GF(q) с одинаковой мощностью циклов 
. Показана реализация идеальной совершенной почти пороговой СРС на эллиптической кривой, на которой многочлен третьей степени используется для генерации проверочной матрицы над GF(q) кода линейной СРС.
Рецензенты:
- Баутин Сергей Петрович, доктор физ.-мат. наук, профессор, профессор кафедры «Высшая и прикладная математика». Уральский государственный университет путей сообщения, г.Екатеринбург.
- Ялышев Юрий Иванович, доктор физ.-мат. наук, профессор, и.о. заведующего кафедрой «Информационные технологии и защита информации», проректор по информатизации. Уральский государственный университет путей сообщения, г.Екатеринбург.