О явных конструкциях для решения задачи "A secret sharing" | Прикладная дискретная математика. Приложение. 2017. № 10. DOI: 10.17223/2226308X/10/29

О явных конструкциях для решения задачи "A secret sharing"

Рассматривается следующая задача: построить подмножество M С Fn, удовлетворяющее двум условиям: 1) каждый элемент u Е M может быть представлен в виде суммы трёх различных элементов множества M = Fn \ M; 2) сумма любых трёх различных элементов из M принадлежит M. Излагаются подходы к решению этой проблемы, в частности, для чётной размерности предложена явная конструкция искомого множества на основе кубической параболы.

On explicit constructions for solving the problem "A secret sharing".pdf Во втором раунде олимпиады по криптографии NSUCRYPTO-2015 [1] была предложена задача на специальный приз программного комитета Problem 1 "A secret sharing", в ноябре 2016 г. отмеченная как все ещё не решённая [2]. Постановка задачи требует предложить для каждого натурального n Е n явную конструкцию подмножества M множества fn всех битовых строк длины n, удовлетворяющего следующим двум условиям: 1) каждый элемент u Е M может быть представлен в виде u = x ф y ф z, где x, y, z - различные элементы множества M = fn \ M; 2) для всех различных x, y, z Е M справедливо x ф y ф z Е M. Обозначая L = M, можем переписать условия 1 и 2 для L. Как показывают вычислительные эксперименты, |L| ^ 2n/2. Это оправдывает подход к построению L в виде кривой при чётном n = 2m. Пусть n = 2m (m Е n); представим fn в виде декартова произведения fn = fm х fm, а множество L - в виде кривой, состоящей из точек (x,y) этой плоскости, удовлетворяющих уравнению F(x,y) = 0 (x,y Е fm). Будем искать уравнение кривой L в явном виде y = f (x), (1) где x,y Е fm; f : fm -^ fm. Через функцию (1) условия 1 и 2 записываются следующим образом: 1') каждая точка (u,v) Е fm х fm, не лежащая на кривой L, т.е. v = f(u), может быть представлена в виде u = x1 + x2 + x3, (2) v = f (x1) + f (x2) + f (x3), (2) где x1 = x2 = x3 = x1 и знак «+» обозначает побитовое сложение в fm; 2') для всех x1 = x2 = x3 = x1 справедливо f (x1 + x2 + x3) = f (x1) + f (x2) + f (x3). (3) Будем считать fm полем Галуа GF(2m) и строить f в виде многочлена. Возьмём f в виде y = f (x) = x3. (4) Проверяя 2', найдём y = f (x1 + x2 + x3) = (x1 + x2 + x3)3 = (x1 + x3 + x3) + 3(x1 + x2)(x1 + x3)(x2 + x3). (5) Следовательно, равенство в (3) равносильно равенству (x1 + x2)(x1 + x3)(x2 + x3) = 0, что в поле характеристики два равносильно тому, что или x1 + x2 = 0, или x1 + x3 = 0, или x2 + x3 = 0. Это противоречит условию различности точек x1 = x2 = x3 = x1. Итак, функция (4) удовлетворяет условию 2'. Приступим теперь к проверке условия 1'. Используя (5) в (2), получим в поле характеристики 2 0 = w = u3 + v = (x1 + x2)(x1 + x3)(x2 + x3). (6) Значит, условие 1' сводится к условию 1") для любых u, v, таких, что u3 + v = 0 и u = x1 + x2 + x3, существуют такие (все различные) x1,x2 и x3, что справедливо (6). Выразим x3 из (2) x3 = u + x1 + x2, подставим его в (6) и получим 0 = w = u3 + v = (x1 + x2)(u + x2 )(u + x1) = = [(x1 + u) + (x2 + u)](x1 + u)(x2 + u) = (x + y)xy, где обозначено x = x1 + u, y = x2 + u. Пусть w Е GF(2m) -произвольный отличный от нуля элемент поля. Если существуют такие элементы x,y Е GF(2m), что w = xy(x + y), то для любых u,v, таких, что u3 + v = w, имеем при x1 = x + u, x2 = y + u, x3 = x + y + u равенства (2) и (7). При этом из (7) при w = 0 вытекает x1 = x2 = x3 = x1, и равенство (2) справедливо ввиду v = u3 + w = (x1 + x2 + x3)3 + (x1 + x2)(x1 + x3 )(x2 + x3) = x3 + x3 + x3. Итак, функция (4) удовлетворяет условию 1' тогда и только тогда, когда 1"') для любого ненулевого w Е GF(2m) существуют элементы x,y Е GF(2m), удовлетворяющие уравнению (7). Сведём уравнение (7) к квадратному. Вводя a = ai = x + y и a2 = xy = w/a, видим, что £ = x и £ = y - корни квадратного уравнения £2 + a£ + w = 0. (8) a £ Вводя вместо £ новую неизвестную n = _, из £ = an получим посредством (8) квадa ратное для n уравнение 2w n2 + n + = 0. a3 Как известно [3-5], необходимым и достаточным условием существования решения уравнения (8) является равенство нулю следа свободного члена, т. е. ( w \ tr Ы = 0 Заметим, что в качестве a мы можем, для данного w, выбирать произвольный (ненулевой) элемент поля GF(2m). При этом уравнение (7) есть частный случай уравнения (6) при x3 = u = 0, w = v = 0. Следовательно, условия 1, 1', 1", 1"' равносильны следующему условию: 3) для любого ненулевого w G GF(2m) существует такой ненулевой a G GF(2m), что (абсолютный) след элемента w/a3 равен нулю. Проверка этого условия произведена в зависимости от m mod 4. Суммируя результаты, получаем итоговое Утверждение 1. При чётном n = 2m, m ^ 3, кубическая парабола M = L = {(x,y) G fn : y = x3,x,y G GF(2m)} удовлетворяет требованиям задачи 1, 2. Таким образом, получена явная конструкция для решения задачи при чётной размерности.

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

NSUCRYPTO-2015, поле Галуа, кривая, разделение секрета, NSUCRYPTO-2015, Galois field, secret sharing, parabola curve

Авторы

ФИООрганизацияДополнительноE-mail
Геут Кристина ЛеонидовнаУральский государственный университет путей сообщенияассистентgluskokrl@rtural.ru
Кириенко Константин АндреевичУральский государственный университет путей сообщениястудентracoon-95@mail.ru
Садков Прохор ОлеговичУральский государственный университет путей сообщениястудентprokhor.sadkov@yandex.ru
Таскин Роман ИгоревичУральский государственный университет путей сообщениястудентtaskinroman@mail.ru
Титов Сергей СергеевичУральский государственный университет путей сообщениядоктор физико-математических наук, профессорstitov@usaaa.ru
Всего: 5

Ссылки

http://nsucrypto.nsu.ru. International Students' Olympiad in Cryptography NSUCRYPTO.
Agievich S., Gorodilova A., Idrisova V., et al. Mathematical problems of the Second International Students' Olympiad in Cryptography // Cryptologia. 2017. http://www. tandfonline.com/doi/full/10.1080/01611194.2016.1260666.
Болотов А. А., Гашков С. Б., Фролов А. Б. Элементарное введение в эллиптическую криптографию: алгебраические и алгоритмические основы. М.: КомКнига, 2006.
Болотов А. А., Гашков С. Б., Фролов А. Б. Элементарное введение в эллиптическую криптографию: Протоколы криптографии на эллиптических кривых. М.: КомКнига, 2006.
Лидл Р., Нидеррайтер Г. Конечные поля. М.: Мир, 1988.
 О явных конструкциях для решения задачи

О явных конструкциях для решения задачи "A secret sharing" | Прикладная дискретная математика. Приложение. 2017. № 10. DOI: 10.17223/2226308X/10/29