Blocking varieties in steiner triples.pdf Во втором раунде международной интернет-олимпиады по криптографии NSU-CRYPTO-2015 [1] была предложена задача на специальный приз программного комитета «A secret sharing», в 2016 и 2017 гг. отмеченная как всё ещё не решённая [2, 3]. Решение этой задачи рассматривается с точки зрения блокировки двумерных аффинных многообразий над полем GF(2). Здесь под задачей блокировки семейства S подмножеств T множества E понимается задача построения такого минимального по включению подмножества M, что любое подмножество T из семейства S имеет непустое пересечение с M. Каждое такое подмножество M называется блокирующим множеством семейства S, а подмножество L - E \\ M - дополнением блокирующего множества. Задача блокировки троек Штейнера может трактоваться как вспомогательная при решении исходной задачи NSUCRYPTO, поскольку каждое такое многообразие является сдвигом однозначно определённого двумерного линейного многообразия, соответствующего линейной тройке Штейнера [4]. Проблеме вложимости произвольной системы троек Штейнера в совершенный двоичный код посвящена работа [5]. Проблеме реализации связи блок-схем с семейством троек Штейнера, где однородный матро-ид, когиперплоскости которого - это тройки Штейнера, соответствует идеальной схеме разделения секрета, посвящена работа [6]. Линейные системы троек Штейнера Sn - системы с v - 2n - 1 элементами - ненулевыми битовыми строками длины n, n ^ 3, в которых бинарная операция квазигруппы Штейнера есть побитовое сложение по модулю два. Для матроидов линейных троек Штейнера ниже построены соответствующие им схемы разделения секрета [7, 8], а также рассмотрены методы построения блокирующих множеств минимальной и максимальной мощности. Утверждение 1. Мощность l дополнения L блокирующего множества удовлетворяет неравенству l(l + 1)/2 ^ v. Используя данное неравенство, получим, что для нелинейной тройки Штейнера при v - 13 минимальная мощность дополнения l - 5, а для v - 31 не может быть меньше восьми. Линейные системы троек Штейнера можно трактовать как систему предписанных соотношений в конечных бинарных полях. В зависимости от их интерпретации задачу блокировки можно рассматривать в связи с реализацией схем разделения секрета (СРС) в конечных полях. Так, проблема «A secret sharing» как проблема блокировки аффинных многообразий приводит к задаче реализации СРС, сохраняющих предписанные соотношения в виде семейства H4 четвёрок в GF(2n), таких, что X1+X2+X3+X4 = 0, а проблема блокировки линейных троек Штейнера приводит к задаче реализации СРС, сохраняющих предписанные соотношения в виде семейства H3 троек в GF(2n), таких, что X1 + X2 + X3 = 0. Эти зависимости можно трактовать как циклы [9] в некоторых матроидах. Утверждение 2. Семейство H4 с добавлением пятиэлементных подмножеств, никакие четыре элемента которых не дают в сумме нуль, удовлетворяет аксиомам циклов матроида. Утверждение 3. Семейство H3 с добавлением четырёхэлементных подмножеств, никакие три элемента которых не дают в сумме нуль, удовлетворяет аксиомам циклов матроида. Оказывается, эти матроиды являются матроидами идеальных СРС, реализация которых аналогична реализации схемы Шамира и основывается на интерполяционных многочленах с нулевым следом. Утверждение 4. Классом многочленов, разделяющих секрет посредством циклов семейства H4 построенного матроида, является класс многочленов вида /(x) = = ax4 + bx2 + cx + d, где a, b, c, d - произвольные элементы поля GF(2n). Утверждение 5. Классом многочленов, разделяющих секрет посредством циклов семейства H3 построенного матроида, является класс многочленов вида /(x) = = ax3 + bx + c, где a, b, c - произвольные элементы поля GF(2n). Для нелинейных троек Штейнера мощность блокирующего множества может быть получена только полным перебором, например: Утверждение 6. Для v =13 максимальные и минимальные мощности дополнительного множества равны |L|min = 5, |L|max = 6. Система троек, построенная на тринадцати элементах, не относится к линейным. Рекуррентная конструкция блокирующего множества M и его дополнения L такова: Утверждение 7. Для любого дополнительного множества L существует L& в Sk (при k > n, k - мощность множества битовых строк, в которых первые n битов равны нулю), имеющее мощность |L&| = |L| • 2k-n. Максимальность такого L вытекает из условия, что для любого элемента из тройки u £ M существуют x1, x2 £ L, что u = x1 ф x2 и L не включает в себя ни одной тройки с нулевой суммой. Конструкция минимального блокирующего множества M и его дополнения L такова: G = M U {0} есть подгруппа группы (F^; ф) индекса два (линейное пространство), а L = G ф h (h £ G) -её смежный класс (аффинное пространство). Эта конструкция, очевидно, даёт решение задачи блокировки в общем случае линейной тройки Штей-нера при n ^ 3, при этом |L| = 2П-1, |M| = 2n-1 - 1. Итак, предложены конструкции блокирующих множеств троек Штейнера и оценки возможных значений их мощности.

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