=Paper=
{{Paper
|id=Vol-1825/p28
|storemode=property
|title= О схемах разделения секрета и однородных матроидах (About secret sharing schemes and homogeneous matroids)
|pdfUrl=https://ceur-ws.org/Vol-1825/p28.pdf
|volume=Vol-1825
|authors=Nikita V. Medvedev,Sergei S. Titov
}}
== О схемах разделения секрета и однородных матроидах (About secret sharing schemes and homogeneous matroids)==
https://ceur-ws.org/Vol-1825/p28.pdf
О схемах разделения секрета и однородных матроидах
Н.В. Медведев С.С. Титов
itcrypt@gmail.com sergey.titov@usaaa.ru
Уральский государственный университет путей сообщения (Екатеринбург)
Аннотация
Работа посвящена исследованию однородных матроидов, т.е. таких,
которые имеют циклы одинаковой мощности. Рассмотрены неко-
торые плоскости таких матроидов. Установлена их связь с блок-
схемами. Дано частичное описание матроидов коранга три, а так
же поставлены задачи для дальнейшего исследования.
Ключевые слова: однородные структуры доступа; схемы разде-
ления секрета; матроиды; циклы.
1 Введение
Разграничение доступа на основе схем разделения секрета (СРС) состоит в том, чтобы заранее заданные
(разрешенные) коалиции участников могли однозначно восстановить секрет, а неразрешенные – не получа-
ли никакой дополнительной информации, к имеющейся априорной, о возможном значении секрета, такие
СРС называются совершенными. Идеальными называются СРС, где размер доли секрета, предоставля-
емый участнику, не больше размера самого секрета. Если разрешенными коалициями являются любые
множества из k или более элементов, то такие СРС называются пороговыми "k из N " СРС, где N –
количество всех участников [1, 2, 3].
Общая проблема описания матроидов, соответствующих СРС, пока не решена [1]. Актуальной задачей
является описание однородных (homogeneous [4]) СРС, т.е. таких, где мощность всех разрешенных коалиций
k, но, возможно, не все k-элементные множества входят в структуру доступа СРС.
Как известно [1, 5], разрешенные коалиции идеальной совершенной схемы разделения секрета опреде-
ляются циклами некоторого связного матроида, изучение которого и дает структуру доступа.
2 Основные понятия и термины
Напомним [6, 7], что на множестве E определен матроид M , если некоторые его подмножества названы
независимыми (остальные – зависимыми), причём удовлетворяются аксиомы матроида; так, в терминах
циклов – минимальных (по включению) зависимых подмножеств из M – аксиом всего две: 1) нет цикла в
цикле, т.е. если C, D – циклы, и C ⊂ D, то C = D; 2) если C1 6= C2 – циклы, и x ∈ C1 ∩ C2 , то C1 ∪ C2 \ {x}
содержит цикл. Под N будем понимать мощность матроида M , т.е. N = |E|. Любое максимальное независи-
мое подмножество B, содержащееся в E, называется базой матроида M . Дополнение базы матроида будем
называть кобазой B = E \ {B}, и, аналогично, дополнение цикла матроида – антицикл (когиперплоскость)
C = E \ C. Из [8] известно, что аффинные и проективные пространства являются матроидами над GF (q) с
гиперпространствами в качестве антициклов. Рангом матроида M называется мощность любой его базы.
Ранговая функция двойственного матроида M ∗ называется коранговой функцией (корангом) матроида M
c by the paper’s authors. Copying permitted for private and academic purposes.
Copyright °
In: G.A. Timofeeva, A.V. Martynenko (eds.): Proceedings of 3rd Russian Conference "Mathematical Modeling and Information
Technologies" (MMIT 2016), Yekaterinburg, Russia, 16-Nov-2016, published at http://ceur-ws.org
224
[6]. Матроид называется связным, если для любых двух его элементов существует содержащий их цикл.
Простым или комбинаторной геометрией называется матроид, в котором нет одноэлементных и двухэле-
ментных циклов [6]. Под однородностью матроида понимается одинаковость мощностей его циклов n, где,
возможно, не все n-элементные множества – циклы. При этом, если все его n-элементные подмножества
– циклы, то такой матроид называется пороговым (равномерным). Ранее в [9] матроиды были названы
почти пороговыми с близкой мощностью циклов, т.е. n или n + 1. Матроид назовем разделяющим тогда и
только тогда, когда для любых x 6= y существует разделяющий их цикл C, т.е. x ∈
/ C, y ∈ C.
3 Некоторые свойства однородных матроидов
В представленном ниже подходе к описанию однородных матроидов большую роль играют арифметические
соотношения между параметрами характеризующих его объектов.
Пусть M = (E, C) – связный разделяющий матроид на множестве E с семейством циклов C. Пусть
N = |E| > n, и пусть M – однородный, т.е. все его циклы C имеют мощность n:
C ∈ C ⇒ |C| = n. (1)
Если a, b ∈ E, a 6= b, то, в силу того, что M – разделяющий, существует цикл C0 такой, что a ∈ C0 ,
b∈
/ C0 . В силу того, что M – связный, существуют такие два цикла C1 , C2 , что C1 6= C2 , b ∈ C1 , b ∈ C2 и
C0 = Db (C1 , C2 ) = (C1 ∪ C2 ) \ Jb (C1 , C2 ), (2)
где [5]
\
Jb (C1 , C2 ) = {C : b ∈ C ⊂ (C1 ∪ C2 )}. (3)
Из (2) вытекает, что
C0 = (C1 ∩ C0 ) ∪ (C2 ∩ C0 ). (4)
Следовательно, |C1 ∩ C0 | + |C2 ∩ C0 | ≥ |C0 | = n, и поэтому для C00 = C1 или для C00 = C2 выполняется
неравенство |C00 ∩ C0 | ≥ dn/2e. Итак, доказано
Утверждение 1. В связном разделяющем однородном матроиде для любых двух различных элементов
a, b и любого цикла C, содержащего a, но не содержащего b, существует цикл C 0 , содержащий b и такой,
что
|C ∩ C 0 | ≥ dn/2e = bn + 1/2c. (5)
Пусть e ∈ E – любой элемент и C1 6= C2 – два содержащих его различных цикла. Согласно определению
\
Je (C1 , C2 ) = {C : e ∈ C ⊂ (C1 ∪ C2 )}. (6)
Поскольку
Je (C1 , C2 ) ⊂ (C1 ∩ C2 ), (7)
имеем
|De (C1 , C2 )| = |(C1 ∪ C2 ) \ Je (C1 , C2 )| ≥ |(C1 ∪ C2 ) \ (C1 ∩ C2 )| = |C1 ⊕ C2 |. (8)
Следовательно, De (C1 , C2 ) может быть минимальным по включению (и, значит, циклом) только если n =
|De (C1 , C2 )| ≥ |C1 ⊕ C2 |.
Пусть F – максимальное по включению подмножество в E, в котором каждое n-элементное подмноже-
ство является циклом. Можно считать, что |F | ≥ n.
Утверждение 2. Множество F является подпространством матроида M .
Доказательство. От противного, если F не замкнуто, то существует e ∈ E \ F , лежащий в замыкании
F , т.е. существует такой цикл C1 , что {e} = C1 \ F . Возьмем любой элемент d ∈ F \ C1 . Тогда C2 =
{d}∪(C1 ∩F ) ⊂ F , и, поскольку |C2 | = n, то по предположению C2 является циклом. Значит, C1 ⊕C2 = {e, d},
и поэтому любое n-элементное подмножество в {e, d} ∪ (C1 ∩ C2 ) является циклом, т.е. любой элемент x
225
в C1 \ {e} можно заменить на любой элемент d ∈ F \ C1 , и при этом множество {e} ∪ (C1 \ {x}) ∪ {d}
также будет циклом. Отсюда вытекает, что любое n-элементное подмножество в {e} ∪ F есть цикл, что
противоречит максимальности F .
Поскольку M – не пороговый (не равномерный), то F 6= E. Для каждого a ∈ E \ F обозначим через k(a)
минимальную мощность множества C 0 \F по всем таким циклам C 0 ∈ C, что a ∈ C 0 . Согласно утверждению
1 имеем
k(a) ≤ n − dn/2e (9)
Поскольку F – подпространство матроида, имеем 1 < k(a).
Пусть k – минимальное такое число, т.е. k = min k(a), a ∈ E \ F . Из предыдущего ясно, что 2 ≤ k ≤
n − dn/2e. Если k(a1 ) = k, т.е. на элементе a1 ∈ E \ F этот минимум достигается, то существует такой
цикл C 0 , что C 0 \ F = {a1 , ..., ak }, |C 0 \ F | = k. По утверждению 1 имеем C 0 ∩ F 6= ®. Дополняя это
множество C 0 ∩ F до подмножества C ⊂ F мощности n, можем считать C 0 = {a1 , ..., ak , f1 , ..., fn−k }, C =
{f1 , ..., fn−k , ..., fn } ∈ C. Поскольку никакое подмножество в {a1 , ..., ak } мощности (k − 1) не равно (C 00 \ F )
ни для какого C 00 ∈ C, то любое такое подмножество вместе с любым (n − 1)-элементным подмножеством в
F является независимым и, следовательно, есть база некоторого подпространства F 0 . Ясно, что F ⊂ F 0 и
rankF 0 = (k − 1) + (n − 1) = n + k − 2. Следовательно, в любом (n − 1)-элементном подмножестве множества
F существует единственное его (n − k)-элементное подмножество D такое, что {a1 , a2 , ..., ak } ∪ D – цикл
(достаточно для этого в базу F 0 включить элементы a2 , ..., ak ). Введем во множестве C = {f1 , ..., fn } ⊂ F
следующее бинарное отношение: u ≡ v тогда и только тогда, когда в C \ {u} и в C \ {v} такое подмножество
D одно и то же. Легко проверяется рефлексивность, симметричность и транзитивность этого отношения,
т.е. это – отношение эквивалентности. Соответствующее ему разбиение множества C имеет, очевидно,
одинаковые мощности классов эквивалентности, а именно n − (n − k) = k, т.к. мощность каждого такого
D равна (n − k).
Следовательно, {a1 , ..., ak } задает разбиение любого n-элементного подмножества C ⊂ F на k-
элементные подмножества, дополнение каждого из которых до C, объединенное с {a1 , ..., ak }, есть цикл.
Отсюда вытекает
Утверждение 3. Мощность циклов n делится на k.
Теперь допустим, что |F | ≥ n + 1. Взяв G ⊂ F , |G| = n + 1, видим, что A∪B ˙ есть база в F 0 , где
A – любое такое подмножество в {a1 , ..., ak }, что |A| = k − 1;
B – любое такое подмножество в G, что |B| = n − 1;
∪˙ – обозначает объединение непересекающихся множеств.
Следовательно, для любых двух различных элементов x, y ∈ G, x 6= y, существует единственный цикл
Cxy = {a1 , ..., ak }∪D ˙ xy , где Dxy ⊂ G \ {x, y} = Bxy , |Dxy | = n − k.
Рассмотрим случай минимального значения k = 2. По утверждению 3 в этом случае n четно. Здесь
|Dxy | = n − k = n − 2, так что Dxy получается удалением из G еще одного, кроме x и y, однозначно
определенного по ним элемента z:
Dxy = G \ {x, y, z}. (10)
Значит, на G имеется семейство троек {x, y, z}, которые удовлетворяют следующим свойствам:
1. Если x ∈ G, то |G \ {x}| = n, и поэтому имеется разбиение C = G \ {x} на двухэлементные подмно-
жества, каждое из которых в объединении с {x} дает такую тройку. Следовательно, каждый элемент x
содержится ровно в r = n/2 тройках.
2. В силу единственности Dxy каждая пара x, y различных элементов содержится точно в одной тройке
(λ = 1).
3. Более того, для разных x1 6= x2 ни один смежный класс разбиения множества G \ {x1 } не совпадает
ни с одним смежным классом разбиения множества G \ {x2 }, т.к. иначе имелись бы два цикла C1 и C2 с
C1 ⊕ C2 = {x1 , x2 }, откуда вытекало бы, что каждое n-элементное подмножество в C1 ∪ C2 – есть цикл,
в том числе циклы C 0 и C 00 такие, что C 0 \ F = {a1 }, C 00 \ F = {a2 } что противоречит замкнутости F .
Следовательно, число таких троек равно n(n+1)
3·2 .
Из этих свойств вытекает, что полученное семейство троек образует блок-схему [10] с параметрами:
(n + 1) – количество элементов;
(n+1)n
6 – количество блоков (троек);
3 – количество элементов в блоке (в тройке);
226
r = n2 – количество блоков (троек), содержащий любой данный элемент;
λ = 1 – каждая пара различных элементов содержится точно в одном блоке (в тройке).
Итак, получаем блок-схему D(n + 1, (n+1)n
6 , n2 , 3, 1) (см. раздел 15.4 в [10]), т.е. систему троек Штейнера.
Такие тройки существуют, как известно, при n ≡ 0(mod 6) или n ≡ 2(mod 6). Таким образом, однородные
матроиды оказываются связанными с блок-схемами.
4 Обобщение конструкции
Проведем проверку аксиом когиперплоскостей для троек Штейнера. Пусть H1∗ = {x, y, z} и H2∗ = {u, v, w},
где |{x, y, z}| = |{u, v, w}| = 3, xy = z, uv = w. Определяем циклы C1 = E \ {x, y, z} и C2 = E \ {u, v, w} так,
что e ∈ C1 ∩ C2 и e ∈ E \ {x, y, z, u, v, w}. Следовательно, существуют d, c такие, что C = E \ {c, d, e} ∈ C.
Действительно, если H1∗ ∩ H2∗ = ®, то C1 ∪ C2 \ {e} = E \ {e} и в качестве H ∗ = E \ C подойдет любая
тройка {c, d, e}, где cd = e. Если H1∗ ∩ H2∗ 6= ®, то при C1 6= C2 имеем в точности |H1∗ ∩ H2∗ | = 1.
Пусть H1∗ ∩H2∗ = {d}, имеем e 6= d, т.к. e ∈ E \{H1∗ ∪H2∗ }. Значит, если обозначить c = ed, то |{c, d, e}| = 3,
можно положить H ∗ = {c, d, e}, C = E \ H ∗ . Итак, доказано
Утверждение 4. Семейство троек Штейнера удовлетворяет аксиомам гиперплоскостей.
Матроид, у которого когиперплоскости – тройки Штейнера, является однородным связным и разделя-
ющим. Рассмотрим каждое из этих свойств. Очевидно, что матроид является однородным, т.к. k = 3 и
мощности когиперплоскостей будут одинаковыми.
Докажем, что матроид является связным. При x 6= y, z = xy, т.е. {x, y, z} – тройка Штейнера. Как
известно, при N > 3 имеем N ≥ 7. Если, от противного, любая тройка Штейнера пересекается с {x, y}, то
в каждой такой тройке есть либо x, либо y. При N > 3 существует такой u, что u ∈ / {x, y, z}, тогда uz = v.
Ясно, что u 6= z, т.к. {u, v, z} – тройка Штейнера, v 6= x, иначе u = y, и v 6= y, т.к. иначе было бы u = x.
Итак, построена тройка {u, v, z}, не содержащая ни x, ни y, что и требовалось доказать.
Докажем, что матроид является разделяющим. Пусть {x, y, z} – тройка Штейнера, при N > 3 существует
такое u, что u ∈ / {x, y, z}, тогда yu = v. Если v = x, то u = z, вопреки u ∈/ {x, y, z}. Если же v = z, то u = x,
вопреки u ∈ / {x, y, z}. Значит, тройка {u, v, u} не содержит x, что и требовалось доказать.
Теперь при k ≥ 3, λ = 1, n = |E| − k рассмотрим блок-схему и проверим аксиомы гиперплоскостей для
блоков.
Любая пара в единственном блоке B = H ∗ , |B| = k.
1) Если H1∗ ∩ H2∗ = ®, e ∈ E \ (H1∗ ∪ H2∗ ), C1 ∪ C2 \ {e} = E \ {e}; Ci = E \ Hi∗ , то подойдет любая H ∗
такая, что e ∈ H ∗ .
2) Если H1∗ ∩ H2∗ 6= ®, то при |H1∗ ∩ H2∗ | ≥ 2 имеем H1∗ = H2∗ , поэтому 0 < |H1∗ ∩ H2∗ | < 2, т.е. при H1∗ 6= H2∗
имеем |H1∗ ∩ H2∗ | = 1. Пусть H1∗ ∩ H2∗ = {d}. Тогда нам надо найти H ∗ такую, что {d, e} ⊂ H ∗ . Из-за λ = 1
такая H ∗ существует и единственная. Проверка аксиом гиперплоскостей завершена. Итак, доказано
Утверждение 5. Блок-схема с λ = 1 задает когиперплоскости однородного связного разделяющего
матроида.
Доказательство. Аналогично случаю при k = 3.
Очевидно, что для λ = 2 блок-схема не удовлетворяет аксиомам гиперплоскостей.
Это рассмотрение указывает на сложность задачачи описания однородных матроидов и позволяет по-
ставить следующие задачи:
- описание блок-схем для однородных матроидов;
- построение СРС по однородному матроиду, построенному как блок-схема.
5 Однородные матроиды коранга три
В [11] дано описание однородных матроидов коранга три. При этом утверждение доказано в не явном
предположении, что существует не более одной линии, проходящей через точку b, не лежащей на данной
линии, и не пересекающейся с ней. Ниже дано уточненное изложение этого вопроса.
Определение линии bc: x ∈ bc тогда и только тогда, когда во всех циклах, не содержащих ни b, ни c, нет
и x.
Рассмотрим матроид, в котором любой цикл содержит элементы либо a, либо b, либо c, либо пару их,
либо все три. (Значит, {a, b, c} – кобаза). Из непороговости вытекает, что мощность m антициклов ≥ 3.
Пусть A1 , A2 – циклы, такие, что a ∈ A1 , a ∈ A2 (b ∈/ Ai , c ∈
/ Ai ), где (i = 1, 2). Тогда если A1 6= A2 , то в
(A1 ∪ A2 ) \ {a} есть цикл A, причем a ∈
/ A, b ∈
/ A, c ∈
/ A (противоречие с вышеописанным предположением).
227
Следовательно, существует единственный цикл A такой что a ∈ A, b ∈ / A, c ∈ / A. Аналогично – для
элементов b, c матроида M и циклов B, C. Если a1 , a2 таковы, что не существуют циклов, не содержащих
{a1 , b, c} или {a2 , b, c}, то Ai (i = 1, 2) – единственный цикл, такой, что ai ∈ Ai , b ∈
/ Ai , c ∈
/ Ai (i = 1, 2).
Если A1 ∩ A2 6= ®, то при A1 6= A2 эта единственность нарушается для любого a ∈ A1 ∩ A2 по второй
аксиоме циклов. Если же A1 ∩ A2 = ®, то цикл A1 не содержит {a2 , b, c}, и A2 не содержит {a1 , b, c}
вопреки предположению. Итак, существует единственный цикл A, не содержащий ни b, ни c, и поэтому
можно определить лишь bc = A.
Поэтому bc = A, т.е. для каждой линии (вне которой есть хотя бы одна точка) существует единственный
цикл, дополнением которой он является.
Утверждение 6. Вне каждой линии есть точка.
Доказательство: В противном случае не существовали бы три точки a, b, c.
Предположим, как было указано выше, что для любой точкивне любой данной линии, существует не
более одной линии, содержащей эту точку и не пересекающейся с данной линией.
Следствие 1. N = |M | = n + |bc| для любых точек b 6= c и определяемой ими линии bc.
Следствие 2. Если w ∈ uv, u 6= v 6= w 6= u, то u ∈ vw, v ∈ uw, как дополнение единственного цикла.
Итак, циклов (и антициклов) всего
2
CN N (N − 1)
2 = .
CN −n (N − n)(N − n − 1)
Пусть m = N − n есть мощность антициклов, т.е. количество точек на каждой линии. Тогда пары точек
u 6= v и a 6= b определяет одну и ту же линию, когда они обе ей принадлежат, и таких пар на линии всего
2 2
Cm . А всего пар различных элементов матроида – CN . Поэтому количество всех линий как антициклов
равно
2
CN N (N − 1) N (N − 1)
2
= = .
Cm m(m − 1) (N − n)(N − n − 1)
Зафиксируем точку b и линию ac, b ∈ / ac. Тогда, поскольку для каждой точки x на линии ac получаем
(m − 1) точку на линии bx (кроме b), итого получаем (поскольку все эти линии разные для разных x, т.к.
иначе было бы b ∈ ac = x1 x2 ) всего m(m − 1) + 1 точек. Если этими точками исчерпываются все элементы
матроида, то N = m2 − m + 1, и линий всего
(m2 − m + 1)(m2 − m)
= m2 − m + 1
m(m − 1)
("проективный случай" проективная плоскость порядка (m − 1)).
Итого получаем N = [m(m − 1) + 1] + (m − 1) = (m + 1)(m − 1) + 1 = (m2 − 1) + 1 = m2 ("аффинный
случай" – аффинная плоскость порядка m), а линий всего
N (N − 1) m2 (m2 − 1)
= = m(m + 1).
m(m − 1) m(m − 1)
Случай 1.
Далее произведем проверку аксиом проективной плоскости, взяв линии в качестве прямых.
Аксиома 1. Две различные точки определяют единственную прямую.
Доказательство следует из разделимости матроида.
Аксиома 2. Две прямые пересекаются в единственной точке.
Пусть однородный матроид M мощности |M | = N = m2 − m + 1, где m – мощность линий (антициклов),
и a, b, c – его элементы, не содержащиеся в одном антицикле. По описанному выше построению все точки
(элементы матроида) исчерпываются точками линий, соединяющих точку b с точками ac.
Пусть L1 = C1 , L2 = C2 – две разные линии, дополнения циклов C1 и C2 , C1 6= C2 . Ясно, что если линии
пересекутся в двух или более точках, то они совпадут (см. первую аксиому плоскости). Если же они не
пересекутся, L1 ∩ L2 = ®, то C1 ∪ C2 = M .
Пусть w ∈ M – любой элемент, C – цикл, содержащий w. Тогда линия L = C не проходит через w и
содержит m точек. Линии, проходящие через w и через различные точки линии L, различны, и их всего
m штук. Точек на всех этих линиях, как было вычислено выше, всего N = m2 − m + 1. Следовательно,
этими точками исчерпываются все элементы матроида, и других линий, проходящих через w, больше нет.
228
Итак, доказано:
Утверждение 7. Через любую точку w проходят ровно m линий.
Всего пар различных линий
2 N (N − 1) (m2 − m + 1)(m2 − m) (m2 − m + 1)m(m − 1)
CN = = = .
2 2 2
2
Следовательно, количество пар различных линий, проходящих через любую данную точку, равно Cm =
m(m−1)
2 . Умножая это количество на мощность матроида, получаем количество всех пар линий, имеющих
непустое пересечение, и поскольку это число совпадает с количеством всех вообще пар линий, делаем
вывод, что непересекающихся линий нет. Итак, доказано:
Утверждение 8. В "проективном случае" каждая пара различных линий пересекается в единственной
точке.
Аксиома 3. Существуют четыре точки, никакие три из которых не лежат на одной линии.
Итак, пусть m ≥ 3, точки a, b, c не лежат на одной линии (антицикле). Возьмем, поскольку m ≥ 3,
третью точку x на линии ac отличную от a и c. Соединим ее линией с b, и опять-таки пользуясь тем, что
m ≥ 3, третью точку d на линии bx, отличную от b и x. Из аксиомы 1 следует, что d ∈ / ac, d ∈
/ ab, d ∈
/ bc.
По построению a ∈ / bc, b ∈
/ ac, c ∈
/ ab. Так, что a ∈
/ dc, a ∈
/ db, b ∈
/ dc, c ∈
/ ad, b ∈
/ ad, c ∈
/ bd, действительно,
никакие три не лежат на одной линии. Итак, в самом деле в "проективном случае" получаем конечную
проективную плоскость.
Случай 2.
Далее рассмотрим проверку аксиом аффинной плоскости.
Аксиома 1 совпадает с проективным случаем.
Аксиома 2. Через любую точку вне данной линии проходит единственная линия, не пересекающая
данную (по [12]).
Пусть однородный матроид (в "аффинном случае") мощности |M | = N = m2 , где m – мощность анти-
циклов, и a, b, c – его элементы, не содержащиеся в одном антицикле (как в вышеописанном построении).
Все точки матроида исчерпываются точками линий, соединяющими точку b с точками ac и точками един-
ственной линии, проходящей через b и не пересекающейся с ac. Таким образом, через точку b проходит
всего (m + 1) линий. Ясно, что через любую точку w проходит не более (m + 1) линий, содержащих как
раз (m − 1)(m + 1) + 1 = (m2 − 1) + 1 = m2 = N точек. А так как через w и любую точку, отличную от
w, можно провести единственную прямую, то, следовательно, через каждую точку проходят ровно m + 1
линий, и так можно получить все точки матроида. Поэтому среди этих (m + 1) линий есть в точности одна,
не пересекающая данную линию, в которой всего m точек.
Аксиома 3. Cовпадает с проективным случаем.
По нашему предположению, этих линий не более одной.
Итак, доказано
Утверждение 9. Однородный связный разделяющий матроид коранга три, в котором для любой точки
вне данного антицикла существует не более одного антицикла не пересекающегося с данным, является либо
аффинной плоскостью порядка m, либо проективной плоскостью порядка (m − 1) с прямыми линиями в
качестве антициклов.
6 Заключение
Итак, в работе показана связь однородных матроидов с блок-схемами, а именно с семейством троек Штей-
нера. Доказано, что блок-схема с параметром λ = 1 задает когиперплоскости однородного связного разде-
ляющего матроида. Представлено частичное описание однородных матроидов коранга три. Сформулиро-
ваны задачи для дальнейшего исследования однородных матроидов.
Список литературы
[1] Vvedenie v kriptografiju [Introduction to cryptography]. Pod obshh. red. V. V. Yashchenko. SPb, Piter,
2001. (in Russian) = Введение в криптографию. Под общ. ред. В. В. Ященко. СПб, Питер, 2001.
[2] G. R. Blackley, G. A. Kabatiansky. Generalized ideal secret sharing schemes and matroids. Problemy
peredachi informacii, 33(3):102–110, 1997. (in Russian) = Г. Р. Блейкли, Г. А. Кабатянский. Обоб-
229
щенные идеальные схемы, разделяющие секрет, и матроиды. Проблемы передачи информации,
33(3):102–110, 1997.
[3] E. A. Bolotova, S. S. Konovalova, S. S. Titov. Properties of access control lattices, perfect ciphers and
secret sharing schemes. Problemy bezopasnosti i protivod. terrorizmu: materialy IV mezhdunar. nauch.
konf., 2:71–86, 2009. (in Russian) = Е. А. Болотова, С. С. Коновалова, С. С. Титов. Свойства
решеток разграничения доступа, совершенные шифры и схемы разделения секрета. Проблемы
безопасности и противод. терроризму: материалы IV междунар. науч. конф., 2:71–86, 2009.
[4] J. Marti-Farre, C. Padro. Secret sharing schemes on sparse homogeneous access structures with rank
three. Electronic Journal of Combinatorics, 11(1), Research Paper 72, 2004.
[5] D. J. A. Welsh Matroid Theory. London, Academic press, 1976.
[6] M. O. Asanov, V. A. Baransky, V. V. Rasin. Diskretnaja matematika: grafy, matroidy, algoritmy
[Discrete mathematics: graphs, matroids, algorithms]. Izhevsk: NIC Reguljarnaja i haoticheskaja
dinamika, 2001. (in Russian) = М. О. Асанов, В. А. Баранский, В. В. Расин. Дискретная ма-
тематика: графы, матроиды, алгоритмы. Ижевск: НИЦ Регулярная и хаотическая динамика,
2001.
[7] N. White. Theory of Matroids. Cambridge University Press, 1986.
[8] N. V. Medvedev, S. S. Titov. Problems of almost threshold secret sharing schemes. Applied Discrete
Mathematics, 5:53–54, 2012. (in Russian) = Н. В. Медведев, С. С. Титов. Проблемы почти пороговых
схем разделения секрета. Прикладная дискретная математика, 5:53–54, 2012.
[9] N. V. Medvedev, S. S. Titov. On almost threshold matroids and secret sharing schemes. Vestnik UrFO.
Bezopasnost v informacionnoj sfere, 1(3):31–36, 2012. (in Russian) = Н. В. Медведев, С. С. Титов.
О почти пороговых матроидах и схемах разделения секрета. Вестник УрФО. Безопасность в
информационной сфере, 1(3):31–36, 2012.
[10] M. Hall. Combinatorial Theory. Blaisdell, Waltham, 1967. = М. Холл. Комбинаторика. Москва,
Мир, 1970.
[11] N. V. Medvedev, S. S. Titov. On homogeneous ideal secret sharing schemes and matroids of corank
three. Vestnik UrFO. Bezopasnost v informacionnoj sfere, 4(18):21–26, 2015. (in Russian) = Н. В.
Медведев, С. С. Титов. Об однородных идеальных схемах разделения секрета и матроидах коранга
три. Вестник УрФО. Безопасность в информационной сфере, 4(18):21–26, 2015.
[12] E. Artin. Geometric algebra. Bull. Amer. Math. Soc. 64, 1958. = Э. Артин. Геометрическая алгебра.
Москва, Наука, 1969.
230
About secret sharing schemes and homogeneous matroids
Nikita V. Medvedev
Ural State University of Railway Transport (Yekaterinburg, Russia)
Sergei S. Titov
Ural State University of Railway Transport (Yekaterinburg, Russia)
Abstract. This research is devoted to homogeneous matroids, which have equal power of circuits. Some
flats of such matroids are considered, as well as their connection with block-schemes. A partial description of
homogeneous matroids of corank three is given. The authors set tasks for further research.
Keywords: homogeneous access structure, secret sharing schemes, matroids, circuits.
231