О блокировке двумерных аффинных многообразий | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/1

О блокировке двумерных аффинных многообразий

Рассмотрена проблема блокировки семейств подмножеств и предложена конструкция расширения блокирующих множеств семейства двумерных аффинных многообразий в пространстве битовых строк при увеличении его размерности. Рассмотрены приложения этой конструкции к решению задачи «A secret sharing» олимпиады NSUCRYPTO не только для чётной, но и для нечётной размерности пространства. Приведены примеры и вычислены мощности дополнений блокирующих множеств этого семейства многообразий для высоких нечётных размерностей.

On the blocking of two-dimensional affine varieties.pdf При построении отображений конечных полей, обладающих хорошими криптографическими свойствами, в том числе при разделении секрета, построении APN-функ-ций и т. п., естественным образом возникает подзадача блокировки семейств подмножеств, т.е. задача построения блокирующего множества - такого, что в каждом подмножестве блокируемого семейства найдётся элемент этого множества. Эта задача аналогична классической задаче нахождения трансверсали - системы различных представителей. Так, задачу «A secret sharing» олимпиады по криптографии NSUCRYPTO-2015 [1] можно трактовать как задачу блокировки двумерных аффинных многообразий над полем GF(2). Эта задача частично решена [2, 3], а именно: предложена конструкция дополнения L блокирующего множества M для чётной размерности пространства над полем GF(2). В данной работе для полного решения задачи предлагается конструкция дополнения блокирующего множества, пригодная и для нечётных размерностей пространства, на основе построения расширения множества L при увеличении размерности на единицу. Под задачей блокировки семейства S подмножеств T множества E понимается задача построения такого минимального по включению подмножества M, что любое подмножество T из семейства S имеет непустое пересечение с подмножеством M. Каждое такое подмножество M называется блокирующим множеством семейства S, а подмножество L = E \\ M - дополнением блокирующего множества. Так, если E - множество точек конечной плоскости, семейство S включает в себя все прямые линии T на этой плоскости, то известная задача блокировки прямых [4, 5] состоит в построении минимального нетривиального множества M точек, такого, что в каждой прямой найдётся хотя бы одна точка из M. Таким образом, блокирующее множество на плоскости - это множество точек, пересекающих множество линий. Блокирующее множество называется тривиальным, если оно содержит линию. Семейство прямых в конечной плоскости естественным образом связано с 0(2)-стойкими шифрами [6, 7], являясь при этом семейством гиперплоскостей однозначно определённого матроида, элементы которого (точки) могут быть интерпретированы как участники некоторой идеальной схемы разделения секрета [8]. В задаче «A secret sharing» E есть множество битовых строк длины n, семейство S включает в себя все двумерные аффинные многообразия над GF(2), т.е. такие четы-рёхэлементные подмножества T = {x\\, x2, x3, x4} множества E, что x1 + x2+x3+x4 = 0, и требуется предложить конструкцию блокирующего множества M (или, что равносильно, его дополнения L). В информационной безопасности, если пользоваться метафорой семейства S множеств как семейства контролируемых пространств или возможных траекторий движения злоумышленника, то элементы блокирующего множества M представляют собой в этой метафоре [9] блок-посты или контролирующие устройства (типа датчиков движения, камер видеонаблюдения и т.п.); так что если эти семейства и множества имеют конкретную математическую (в частности, геометрическую) природу, то можно ставить соответствующие математические задачи блокировки. Пусть L = M даёт решение задачи блокировки двумерных аффинных многообразий в Fn. Можно ли включить L в множество L+, дающее решение этой задачи в пространстве Fn+1? Если L+ = L U L', L' С Fn+1 \\ F£, то L' = {f + t : t E T}, где f - фиксированный элемент f E Fn+1 \\ Fn, T С Fn. Необходимым и достаточным условием того, что L+ даёт решение, является |L+ ф L+ \\ {0}| = Сг2+ (где = |L+|) при максимальном L+ (по включению) с таким равенством. Утверждение 1. Подмножество L = M даёт решение задачи блокировки двумерных аффинных многообразий в Fn тогда и только тогда, когда L - максимальное по включению подмножество, такое, что |L ф L\\{0}| = Сг2, где / = |L|. Это свойство равносильно тому, что для любых двух различных пар {u, v} = {w, t}, u = v, w = t, {u, v, w, t} С L, имеем u ф v = w ф t. Утверждение 2. Если множество L = M, дающее решение задачи блокировки двумерных аффинных многообразий в Fn, можно включить в множество L+, дающее решение этой задачи в пространстве Fn+1, то найдётся такое подмножество T С Fn, что (L ф L) П (T ф T) = {0} и |(T ф T) \\ {0}| = C2T|. При этом если T - максимальное по включению такое подмножество, то множество L+ = L U {f ф t : t E T} = L U ({f} ф T), где f - произвольный элемент в Fn+1 \\ F£, даёт решение этой задачи. Конструкция. Пусть n = 2m. Тогда Fn = F^ х F^, имеется конструкция [3] множества L в виде L = {(x,x3) : x E GF(2m)}. Пусть L- есть дополнение блокирующего множества в F^ = GF(2m). Положим T = {(0,t) : t E L-} для любого m, так что условие инъективности выполняется. Проверяя условие отсутствия общих ненулевых сумм, видим, что если (x1,x3) + + (x2,x;]) = (0, t1) + (0, t2), то x1 + x2 = 0, откуда x1 = x2, и поэтому x3 + x3 = 0 = t1 +12, откуда t1 = t2. Следовательно, (L ф L) П (T ф T) = {(0, 0)} и для решения задачи блокировки в Fn+1 требуется установить только максимальность T. Возьмём без ограничения общности f = (0,...,0,1) E Fn+1 \\ Fn, так что L' = = {f + t : t E L-} удовлетворяет условию инъективности. Будем представлять элементы из Fn+1 = F2m+1 в виде троек (x,y,z), где x E F^ = GF(2m), y E F^ = GF(2m), z E F2. Тогда L = {(x, x3, 0) : x E GF(2m)}, L' = {(0,t, 1) : t E L-} и L+ = L U L' удовлетворяет условию инъективности. Для проверки условия максимальности возьмём элемент e = (a,b,c) E Fn+1. Если c = 0, то либо e E L, либо e представим в виде суммы трёх различных элементов из L по построению. Если же c = 1, то при a = 0 либо e E L', либо e представим в виде суммы трёх различных элементов из L' согласно выбору L- , поскольку 1 ф 1 ф 1 = 1. Пусть, наконец, c =1 и a = 0. Тогда при b = a3 имеем e = (a, a3, 0) + (0, 0, 0) + + (0, 0,1), где первые два слагаемых принадлежат L, а третье - L' (предполагается, без ограничения общности, что 0 E L-). При b = a3 положим b = a3 + d. Здесь a = 0, d = 0, так что единственный возможный вариант представления e в виде суммы трёх элементов из L+ - взять два слагаемых из L и одно из L'. Будем искать представление e в виде e = (a, b, 1) = (x1, x1,0) + (x2, x3,0) + (0, t, 1). (1) Это даёт систему уравнений x1 + x2 = a, xf + x2 + t = b. Обозначим x1 = x, тогда x2 = x + a и последнее уравнение принимает вид x3 + (a + x)3 + t = a3 + d. Раскрывая скобки и приводя подобные, получим ax2 + a2x + t = d. Деля на a3 = 0, приходим к уравнению y2 + y = (t' + d') для y = x/a, где обозначено t' = t/a3, d' = d/a3. Как известно [10], решение y существует тогда и только тогда, когда (абсолютный) след правой части равен нулю, т.е. Tr(t' + d') = 0. Итак, наличие представления (1) равносильно возможности подбора для данного d такого t E L-, что Tr(t') = Tr(d'). Поскольку областью значений функции следа является двухэлементное поле F2 = = {0, 1}, для существования такого t при любом d достаточно, чтобы в L-/a3 имелись как элементы с нулевым, так и элементы с единичным следом. Докажем две леммы. Лемма 1. Пусть L - дополнение блокирующего множества в F^ = GF(2k). Тогда для любого ненулевого h E GF(2k) множество L* = hL также является дополнением блокирующего множества. Доказательство. Если l* E L* (i = 1,..., 4) различны и l* + l* + l* + l* - 0, то l* = hli, i = 1,... , 4, причём /1 + l2 + l3 + l4 = 0 и все l^ тоже различны, что невозможно. Если m* E L*, то m* = hm, где m E L, так что имеется представление m в виде суммы трёх различных элементов из L, т. е. m = l1 + l2 + l3, l E L (i =1, 2, 3). Однако тогда имеется и представление для m*, так как m* = hl1 + hl2 + hl3 = l* +1* +1*, где l*, l*, l* - три различных элемента из L*. ■ Лемма 2. Пусть L - дополнение блокирующего множества в F^ = GF(2k). Тогда в L есть элемент с нулевым следом и есть элемент с единичным следом. Доказательство. Пусть, от противного, в L нет ни одного элемента с нулевым следом. Значит, все элементы в L имеют след равный единице. Следовательно, все суммы троек элементов из L имеют след, тоже равный единице, так как 1 ф 1 ф 1 = 1, что противоречит представимости элементов дополнения L, содержащего элементы и с нулевым следом, в виде сумм троек элементов из L. Аналогично - для L без элементов с единичным следом. ■ Применяя эти леммы, получаем при k = m и h =1/a3 Утверждение 3. Для произвольного L-, являющегося дополнением блокирующего множества в F^ (без ограничения общности содержащего нуль), предложенная конструкция даёт множество L+, являющееся дополнением блокирующего множества в F2m+1. Таким образом, для решения задачи «A secret sharing» предложена конструкция множества, блокирующего двумерные многообразия, не только для чётной, но и для нечётной размерности. Необходимо применить описанную процедуру расширения конечное число раз в зависимости от числа n - размерности пространства. Если n чётно, то имеем конструкцию работы [3]. Если n = 2k + 1 и множество Lk известно (например, если k чётно), то применяем процедуру расширения, получив |Ln | = 2k + |Lfc |. Если n = 4k - 1, то, в случае необходимости, можно применить процедуру ещё один раз, при этом мощность дополнения Ln блокирующего множества равна |Ln| = 22k + 2k. Так, из того, что |L51 = 7, находим |L11| = 25 + 7 = 39, а из |L3| = 4 находим |L7| = 23 + 4 = 12. Поэтому множества L23 и L15 находятся «в два действия», т. е. повторным применением описанной процедуры, при этом получается |L23| = 211 + 25 + 7 = 2087, |L151 = 27 + 23 + 4 = 27 + 12 = 140. В три действия находим, например, |L47| = 223 + |L23| = 8390695. Очевидно, что для любого n число процедур расширения не превосходит log2 n, оно достигает максимума s для n = 2s - 1. Например, при s = 5 имеем, применяя процедуру четыре раза, |L31| = 215 + |L15| = 32908, а при s = 8 имеем, применяя процедуру семь раз, |L255| = 2127 + 263 + 231 + 215 + 27 + 23 + 4. Этот метод может быть применён и к другим криптографическим задачам [11].

Ключевые слова

аффинные многообразия, блокирующее множество, NSUCRYPTO, affine manifolds, blocking set, NSUCRYPTO

Авторы

ФИООрганизацияДополнительноE-mail
Титов Сергей СергеевичУральский государственный университет путей сообщениядоктор физико-математических наук, профессорsergey.titov@usaaa.ru
Геут Кристина ЛеонидовнаУральский государственный университет путей сообщениястарший преподаватель кафедры естественно-научных дисциплинgeutkrl@yandex.ru
Всего: 2

Ссылки

Сайт олимпиады NSUCRYPTO. http://nsucrypto.nsu.ru/
Tokareva N., Gorodilova A., Agievich S., et al. Mathematical methods in solutions of the problems from the Third International Students' Olympiad in Cryptography // Прикладная дискретная математика. 2018. №40. С. 34-58.
Геут К. Л., Кириенко К. А., Садков П. О. и др. О явных конструкциях для решения задачи "A secret sharing" // Прикладная дискретная математика. Приложение. 2017. № 10. С. 68-70.
Szonyi T. Blocking sets in desarguesian affine and projective planes // Finite Fields and their Appl. 1997. V.3. Iss.3. P. 187-202.
Polverino O. Linear sets in finite projective spaces // Discrete Mathematics. 2010. V. 310. Iss. 22. P. 3096-3107.
Зубов А.Ю. Совершенные шифры. М.: Гелиос АРВ, 2003.
Болотова Е. А., Коновалова С. С., Титов С. С. Свойства решёток разграничения доступа, совершенные шифры и схемы разделения секрета // Проблемы безопасности и противодействия терроризму. Материалы IV Междунар. науч. конф. М.: МЦНМО, 2009. Т. 2. С.71-86.
Парватов Н. Г. Совершенные схемы разделения секрета // Прикладная дискретная математика. 2008. №2(2). С. 50-57.
Башуров В. В., Филимоненкова Т. И. Математические модели безопасности. Новосибирск: Наука, 2009. 87 с.
Лидл Р., Нидеррайтер Г. Конечные поля. М.: Книга по Требованию, 2013. Т. 1-2. 812 с.
Городилова А. А. От криптоанализа щифра к криптографическому свойству булевой функции // Прикладная дискретная математика. 2016. №3(33). С. 16-44.
 О блокировке двумерных аффинных многообразий | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/1

О блокировке двумерных аффинных многообразий | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/1