Введение к работе
Постановка задачи и актуальность темы диссертации.
Настоящая диссертация посвящена двум основным темам:
-
Исследование структуры и возможности точного представления матрицами (линейности) группы унитреугольных автоморфизмов относительно свободных групп.
-
Построение новых конструкций возможно односторонних функций на основе алгоритмической неразрешимости проблемы эндоморфной сводимости в группах и Диофантовой проблемы.
Группа унитреугольных автоморфизмов. Группам автоморфизмов относительно свободных групп как конечного, так и бесконечного, рангов посвящено немало работ (см. обзоры1' 2' 3).
Обозначим через Fn свободную группу ранга п с базисом Хп = {х\}..., хп}, через F^0 свободную группу бесконечного счетного ранга с базисом Х^0 = {х\} Х2, }, группа F^0 рассматривается как объединение F^0 = U=1Fn. Также обозначим через Gn относительно свободную группу ранга п некоторого многообразия групп С, через G$0 относительно свободную группу бесконечного счетного ранга многообразия С.
Отметим известные результаты о линейности групп автоморфизмов и их подгрупп относительно свободных групп конечного ранга. Почти ниль-потентной называется группа, допускающая нильпотентную подгруппу конечного индекса.
^oman'kov V. A. Automorphisms of groups // Acta Appl. Math. 1992. Vol. 29. P. 241-280.
2Носков Г. А., Ремесленников В. H., Романьков В. А. Бесконечные группы // Итоги науки и техники.
Алгебра. Топология. Геометрия. 1979. Т. 17. С. 65-158. 3Bachmuth S. Automorphisms of solvable groups I // Proceedings of Groups — St. Andrews. 1985. P. 1-14.
Из результатов Д. Крамера4 следует линейность группы AutF
Э. Форманек и К. Прочези5 доказали, что при п > 3 группа AutFn не линейна.
Л. Ауслендер и Г. Баумслаг6 доказали, что группа автоморфизмов любой конечно порожденной почти нильпотентной группы линейна. Более того, голоморф такой группы (значит и ее группа автоморфизмов) допускают точное представление матрицами над кольцом целых чисел Z. Отсюда следует в частности, что группы автоморфизмов относительно свободных групп конечного ранга почти нильпотентных многообразий групп допускают точное представление матрицами.
А. Ю. Ольшанский7 доказал, что если относительно свободная группа Gn не свободна и не почти нильпотентна, то ее группа автоморфизмов AutGn не линейна. В этой же работе отмечалось, что близкие по формулировке результаты содержатся в статьях О. М. Матейко и А. И. Тавгеня8, А. А. Коробова9. Однако, обе эти статьи содержат неточности в формулировках и существенные ошибки в доказательствах (см. работу А. Ю. Ольшанского).
Заметим также, что группа автоморфизмов AutG$0 для любого нетривиального многообразия С содержит подгруппу, определяемую всеми подстановками бесконечного счетного множества свободных порождающих У^0, которая изоморфна группе подстановок S$0. Последняя, как хорошо известно,
4Krammer D. The hypercenter of linear groups // Invent. Math. 2000. Vol. 142, no. 3. P. 451-586. 5Formanek E., Procesi C. The automorphism group of a free group is not linear // J. Algebra. 2002. Vol. 149.
P. 494-499. 6Auslander L., Baumslag G. Automorphism groups of finitely generated nilpotent groups // Bull. Amer. Math.
Soc. 1967. Vol. 73. P. 716-717. 701shanskii A. Y. Linear automorphism groups of relatively free groups // Turk. J. Math. 2007. Vol. 31. P.
105-111. 8Матейко О. M., Тавгень А. И. Линейность групп автоморфизмов относительно свободных групп // Матем.
заметки. 1995. Т. 58, № 3. С. 465-467. 9Коробов А. А. Разделенные разности в теории дифференциально-разностных уравнений и в теории групп
// Вестник Новосибирского гос. университета, серия матем., мех., информ. 2006. Т. 6, Na 3. С. 25-48.
нелинейна.
Никакие из приведенных работ не дают представление о линейности достаточно естественной подгруппы унитрегольных автоморфизмов.
Новые конструкции возможно односторонних функций. Односторонние (в другой терминологии однонаправленные) функции являются неотъемлемой частью криптографических схем и протоколов. Теоретически их существование при формальном определении до сих пор не установлено. В то же время, односторонние функции являются основным инструментом во многих разделах и приложениях криптографии, в частности, они применяются в электронных подписях, протоколах аутентификации, алгоритмах генерации псевдослучайных последовательностей и т.п. Конечно, используемые с указанной целью функции можно назвать только возможно односторонними.
Относительно общей теории односторонних функций см. монографии М. Сипсера10, X. Пападимитриу11, О. Гольдрейха12. В работах Л. Левина13,14 приведена универсальная функция, которая автоматически является односторонней, если существует хотя бы одна односторонняя функция. Такие функции названы полными односторонними функциями. Для их построения Л. Левин использовал нумерацию всех машин Тьюринга и комбинаторный тайлинг. Отсюда видно, что такое построение имеет чисто теоретическое значение. В работе А. А. Кожевникова, С. И. Николенко15 приведены другие примеры полных односторонних функций.
Sipser М. Introduction to the theory of computation. Section 10.6.3: One-way functions. PWS Publishing, 1997.
P. 374-376. 1Papadimitriou С. H. Foundations of Cryptography. Section 12.1: One-way functions. Addison Wesley, 1993. P.
279-298.
2Goldreich O. Computational Complexity: Volume 1, Basic Tools. Cambridge: Cambridge University Press, 2001.
3Левин Л. А. Односторонние функции // Проблемы передачи информации. 2003. Т. 39, Na 1. С. 103-117.
4Levin L. A. One-way Functions and Pseudorandom Generators // Combinatorica. 1987. Vol. 7, no. 4. P. 357-363.
5Кожевников А. А., Николенко С. И. О полных односторонних функциях // Проблемы передачи информации. 2009. Т. 45, № 2. С. 101-118.
Новые конструкции односторонних функций, предложенные в диссертации, относятся к "криптографии основанной на группах"("group-based cryptography") — современному направлению, возникшему на рубеже 20-го и 21-го столетий. Основными объектами в нем являются абстрактные бесконечные группы, а основной целью — построение на этих группах криптографических схем и протоколов. Исследования ведутся методами теории групп, теории сложности и теории вычислений. Современное состояние полученных в этой области результатов отражено в монографиях А. Мясникова, В. Шпильрайна, А. Ушакова 16' 17.
Научная новизна. Все результаты являются новыми, носят теоретический характер и могут найти применения в дальнейших исследованиях.
Внутреннее единство. Исследование унитреугольных автоморфизмов проводилось в связи с идеей построения алгебраических схем односторонних функций с использованием морфизмов групп, в свою очередь связанных с Ди-офантовой проблемой согласно работ научного руководителя. Возможность представления матрицами делает схему менее защищенной. Поэтому возникает естественный вопрос о точной представимости матрицами. Если длина автоморфизма незначительно превосходит длину исходного, то это также ослабляет схему с его использованием. Поэтому естественно решить проблему оценки длины обратного автоморфизма через длину исходного.
Основные результаты диссертации.
1. Описана структура групп унитреугольных автоморфизмов как произведения относительно свободных групп данного многообразия меньших рангов без пересечений, что позволяет определить однозначную нор-
6Myasnikov A., Shpilrain V., Ushakov A. Group-based cryptography (Advanced Courses in Mathematics - CRM
Barcelona). Birkhauser Basel, 2008. 7Myasnikov A., Shpilrain V., Ushakov A. Non-commutative cryptography and complexity of group-theoretic
problemsc (Amer. Math. Soc. Surveys and Monographs). Amer. Math. Soc, 2011.
мальную форму элементов.
Доказано, что группа унитреугольных автоморфизмов относительно свободной группы ранга п многообразия групп отличного от многообразия всех групп допускает точное представление матрицами тогда и только тогда, когда относительно свободная группа ранга п — 1 почти нильпотента.
3.
4. 5.
6.
Дана точная оценка длины обратного к унитреугольному автоморфизму в случае свободной абелевой группы и абсолютно свободной группы.
Приведено явное диофантого представление дискретного логарифма.
Предложены схемы построения двушагово односторонних функций на основе неразрешимости Диофантовой проблемы, рассмотрены предпосылки криптостойкости данных схем.
Предложена схема построения возможно односторонних функций на основе неразрешимости проблемы эндоморфной сводимости в группах, в качестве приложения приведена схема аутентификации с нулевым разглашением пользователей в системе.
Методы исследования. Методы, используемые автором для доказательства результатов, опираются на теорию групп, теорию сложности и теорию вычислений.
Апробация результатов. Основные результаты диссертации докладывались на алгебраическом семинаре ОмГУ им. Ф. М. Достоевского и ОФ ИМ им. С. Л. Соболева СО РАН; Сибирской научной школе-конференции с международным участием "Компьютерная безопасность и криптография" SIBERCRYPT'll (Томск, 2011 г.); международной конференции по алгебре и математической логике "Мальцевские чтения "(Новосибирск, 2011 г.).
Публикации. По теме диссертации опубликованы работы [1-8]. Статьи [1-5] опубликованы в изданиях, входящих в перечень ВАК. Работы [3-5, 7, 8] выполнены в соавторстве с В. А. Романьковым при равном вкладе соавторов.
Структура диссертации. Диссертация состоит из оглавления, введения, трех глав и списка литературы, который включает 73 наименования. Объем диссертации 65 страниц.
