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

Утверждение 2. Доля матриц вида (1) среди невырожденных матриц размера k х k есть O(k22-k).

Таким образом, доля матриц H вида (1) мала, а значит, почти всегда известна структура множества G и можно описать классы эквивалентности секретных ключей криптосистемы Мак-Элиса — Сидельникова.

ЛИТЕРАТУРА

1. Сидельников В. М. Открытое шифрование на основе двоичных кодов Рида — Маллера // Дискретная математика. 1994. Т. 6. №2. С. 3-20.

2. McEliece R. J. A public-key cryptosystem based on algebraic coding theory // DSN Progress Report. 1978. V. 42-44. P. 114-116.

3. Сидельников В. М., Шестаков С. О. О системе шифрования, построенной на основе обобщенных кодов Рида-Соломона // Дискретная математика. 1992. Т. 4. №3. С. 57-63.

4. Чижов И. В. Пространство ключей криптосистемы Мак-Элиса — Сидельникова: дис. ... канд. физ.-мат. наук. М.: МГУ, 2010.

УДК 512.6: 003.26 DOI 10.17223/2226308X/10/29

О ЯВНЫХ КОНСТРУКЦИЯХ ДЛЯ РЕШЕНИЯ ЗАДАЧИ

"A SECRET SHARING"

К. Л. Геут, К. А. Кириенко, П. О. Садков, Р. И. Таскин, С. С. Титов

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

Ключевые слова: NSUCRYPTO-2015, поле Галуа, кривая, разделение секрета.

Во втором раунде олимпиады по криптографии NSUCRYPTO-2015 [1] была предложена задача на специальный приз программного комитета Problem 1 "A secret sharing", в ноябре 2016 г. отмеченная как все ещё не решённая [2].

Постановка задачи требует предложить для каждого натурального n £ N явную конструкцию подмножества M множества F^ всех битовых строк длины n, удовлетворяющего следующим двум условиям:

1) каждый элемент u £ M может быть представлен в виде u = x ф y ф z, где x,y,z — различные элементы множества M = F^ \ 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); представим F^ в виде декартова произведения F^ = F^ х F^, а множество L — в виде кривой, состоящей из точек (x,y) этой плоскости, удовлетворяющих уравнению F(x,y) = 0 (x,y £ F^). Будем искать уравнение кривой L в явном виде

y = f

Математические методы криптографии

69

где Х,у € ЩТ"; / : —^ Щ^7". Через функцию (1) условия 1 и 2 записываются следующим образом:

1') каждая точка (м,^) € х не лежащая на кривой Ь, т.е. V = /(и), может быть представлена в виде

и = Х1 + Х2 + Хз,

V = /

где х1 = х2 = х3 = х1 и знак «+» обозначает побитовое сложение в Щ^Т"; 2') для всех х1 = х2 = х3 = х1 справедливо

/

Будем считать полем Галуа ОЕ(2т) и строить / в виде многочлена. Возьмём / в виде

у = /

Проверяя 2', найдём

у = /

Следовательно, равенство в (3) равносильно равенству (х1 + х2)(х1 + х3)(х2 + х3) = 0, что в поле характеристики два равносильно тому, что или х1 + х2 = 0, или х1 + х3 = 0, или х2 + х3 = 0. Это противоречит условию различности точек х1 = х2 = х3 = х1. Итак, функция (4) удовлетворяет условию 2'.

Приступим теперь к проверке условия 1'. Используя (5) в (2), получим в поле характеристики 2

0 = w = и3 + V =

Значит, условие 1' сводится к условию

1") для любых и, V, таких, что и3 + V = 0 и и = х1 + х2 + х3, существуют такие (все

различные) х1,х2 и х3, что справедливо (6). Выразим х3 из (2) х3 = и + х1 + х2, подставим его в (6) и получим

0 = ад = и3 + V = (х1 + х2)(и + х2 )(и + х1) = = [(Х1 + и) + (Х2 + и)](х1 + и)(х2 + и) = (х + у)ху,

где обозначено х = х1 + и, у = х2 + и.

Пусть ад € ОЕ(2т) —произвольный отличный от нуля элемент поля. Если существуют такие элементы х,у € ОЕ(2т), что w = ху(х + у), то для любых и, V, таких, что и3 + V = ад, имеем при х1 = х + и, х2 = у + и, х3 = х + у + и равенства (2) и (7). При этом из (7) при ад = 0 вытекает х1 = х2 = х3 = х1, и равенство (2) справедливо ввиду

V = и3 + ад = (Х1 + Х2 + Хз)3 + (Х1 + Х2)(Х1 + Хз )(Х2 + Хз) = Х3 + Х3 + х3.

Итак, функция (4) удовлетворяет условию 1' тогда и только тогда, когда

1"') для любого ненулевого ад € ОЕ(2т) существуют элементы х,у € ОЕ(2т), удовлетворяющие уравнению (7).

Сведём уравнение (7) к квадратному. Вводя a = ai = x + y и a2 = xy = w/a, видим, что £ = x и £ = y — корни квадратного уравнения

£2 + a£ + w = 0.

a

£

Вводя вместо £ новую неизвестную n = _, из £ = an получим посредством (8) квад-

a

ратное для n уравнение

2 w

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.

Таким образом, получена явная конструкция для решения задачи при чётной размерности.

ЛИТЕРАТУРА

1. http://nsucrypto.nsu.ru. International Students' Olympiad in Cryptography NSUCRYPTO.

2. 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.

3. Болотов А. А., Гашков С. Б., Фролов А. Б. Элементарное введение в эллиптическую криптографию: алгебраические и алгоритмические основы. М.: КомКнига, 2006.

4. Болотов А. А., Гашков С. Б., Фролов А. Б. Элементарное введение в эллиптическую криптографию: Протоколы криптографии на эллиптических кривых. М.: КомКнига, 2006.

5. ЛидлР, Нидеррайтер Г. Конечные поля. М.: Мир, 1988.