Диофантова криптография на бесконечных группах | ПДМ. 2012. № 2(16).

Диофантова криптография на бесконечных группах

В работе даётся краткое представление криптографии, основанной на группах («group-based cryptography»),- современного направления, главными объектами в котором являются абстрактные бесконечные группы, а основной целью - построение на них криптографических примитивов, систем и протоколов. Исследования по этому направлению ведутся методами теории групп, теории сложности и теории вычислений. Обращается внимание на использование неразрешимых и трудноразрешимых алгоритмических проблем теории групп в качестве основы обозначенного построения. Обсуждаются аспекты сложности алгоритмических проблем и связанных с ними проблем поиска. Объясняется универсальность диофантова языка в криптографии. Отмечается его объединяющая роль. В качестве возможных платформ для криптографических систем и протоколов предлагается использовать свободные метабелевы группы. Приводятся основания для такого использования, в том числе алгоритмическая разрешимость в этих группах проблемы равенства и наличие нормальных форм записи элементов группы. Ещё одним основанием является алгоритмическая неразрешимость в таких группах проблемы существования решений у групповых уравнений и алгоритмическая неразрешимость проблемы эндоморфной сводимости, вытекающих из неразрешимости 10-й Проблемы Гильберта. Предполагается, что в последующей работе автора совместно с С.Ю. Ерофеевым материал данной работы будет использован для построения на свободных метабелевых группах возможно односторонних функций и протоколов аутентификации с нулевым разглашением.

Diophantine cryptography over innite groups.pdf ВведениеПонятие «криптография, основанная на группах» (англ. вариант - group-basedcryptography) появилось сравнительно недавно - на рубеже XX и XXI столетий. Такобозначено направление исследований, основными объектами которого являются аб-страктные бесконечные группы, а основной целью - построение на них криптографи-ческих систем и протоколов. Исследования ведутся методами теории групп, теориисложности и теории вычислений.Данному направлению посвящены монографии [1, 2], а также множество статей,затрагивающих самые разные вопросы. Часть из этих работ представляет криптогра-фические примитивы, другая описывает криптографические системы и протоколы,третья исследует вопросы сложности и т. д. Некоторые работы посвящена вскрытиюслабостей представленных систем и протоколов. Имеются и практические разработки,в том числе компьютерные программы, для использования полученных результатовна практике. Обширный список работ по данному направлению можно найти в [3].В настоящей работе даётся краткое представление о криптографии, основанной нагруппах, обсуждается использование неразрешимых и трудноразрешимых алгоритми-ческих проблем теории групп в качестве основы для построения криптографическихсистем и протоколов. Для обоснования возможности такого использования мы обра-щаем внимание на следующие аспекты:- Как должна быть задана и какими свойствами должна обладать группа, претен-дующая на роль платформы для построения криптографических систем и прото-колов?- Какой должна быть алгоритмическая проблема, претендующая на роль основы дляпостроения криптографических систем и протоколов?- Каковы общие принципы обозначенных построений и чем должна обуславливатьсяих криптостойкость?Подобные вопросы уже неоднократно рассматривались в литературе. После тогокак вышла пионерская в данном направлении работа М. Аншеля и др. [4], в кото-рой представлена схема генерации общего ключа, известная теперь как протокол Ан-шель - Аншеля - Голдфельда, появилось множество работ, эксплуатирующих те илииные алгоритмические проблемы для построения систем и протоколов. В [4] в каче-стве платформы берётся группа кос Артина на n нитях для достаточно большого n.В качестве алгоритмической в ней рассматривается проблема сопряжённости в груп-пе двух наборов элементов g = ( g 1 , . . . , gk) и f = ( f 1 , . . . , fk). Алгоритм может бытьпредставлен в любой группе. Конкретный её выбор обуславливается многими факто-рами. Во-первых, группа, выбранная в качестве платформы, должна быть удобнойдля реализации алгоритма. В то же время необходимо обеспечить криптостойкостьалгоритма. Об этом более подробно говорится в дальнейшем. Опишем сам алгоритмв общем виде.Пусть G - конечно порождённая группа с множеством порождающих элементов{ж1 , . . . ,жп } , которое можно считать фиксированным. Любой элементгруппы G запи-сывается в виде группового слова от порождающих элементов. Групповым называет-ся слово, записанное от букв ж1 , . . . , жп и формальных обратных ж - 1 , . . . , ж- 1 . Конечно,такая запись элемента неоднозначна. Во-первых, возможны сокращения подслов ви-да ж^ж". для е = ±1. Если таких подслов нет, то слово называется редуцированнымили несократимым. Если G = - свободная группа с базисом { ж 1 , . . . , жп}, то записьэлемента в виде несократимого слова однозначна. В группе, не являющейся свободной,существуют нетривиальные слова, записывающие наравне с пустым словом тривиаль-ный элемент. Они называются соотношениями группы.Предположим, что в группе G существует нормальная форма записи её элемен-тов. Это означает, что любой элемент может быть однозначно записан в виде кано-нического слова от порождающих элементов. Переход от произвольной записи эле-мента g = g ^ 1 , . . . , жп) к его записи в нормальной форме н ф ^ ) предполагается эф-фективным. Обычно он осуществляется через переписывающий процесс, получающийна входе произвольное слово от порождающих элементов и выдающий на выходе за-пись соответствующего элемента в нормальной форме. В свободной группе с базисом{ ж 1 , . . . , ж п } это обычный процесс сокращения подслов вида ж|ж"., о которых гово-рилось выше. Известно, что результат - несократимое слово - не зависит от выборапорядка сокращения.В протоколе Аншель - Аншеля - Голдфельда корреспонденты A и B, часто имену-емые как Алиса и Боб, выбирают наборы элементов g = ( g 1 , . . . , gk) и f = ( f 1 , . . . , f)группы G, причём A выбирает набор g, а B - набор f. Эти наборы считаются из-вестными (public). Затем A выбирает секретное (private) слово u = u ( f 1 , . . . , f k ) , а B -секретное слово v = v ( g 1 , . . . , g^). Они могут это сделать, так как наборы известны. Да-лее A выполняет сопряжение набора f элементом u, получая набор fu = ( f U , . . . , fU).Запись вида ab означает сопряжение bab- 1 элемента а элементом b. В дальнейшемчерез [a, b] обозначается коммутатор = aba- 1b- 1 элементов а и b. Корреспондент Aвычисляет и публикует нормальную форму н ф ( / и ) = ( н ф ( ^ ) , . . . , н ф ( ^ ) ) . Подобнымобразом корреспондент B вычисляет и публикует набор н ф ^ ) = ( н ф ^ ) , . . . , н ф ^ ) ) .Предполагается, что в группе G вычисление по опубликованным нормальным фор-мам сопряжённых наборов элементов u и v - трудная задача. На этом основываетсякриптостойкость протокола. После выхода [4] появилось множество работ с анали-зом этой криптостойкости, где подчёркивается важность выбора параметров, ключейи т. п. Появились соответствующие рекомендации и т. п.На выходе протокола корреспонденты получают секретный ключ. Делается этоследующим образом. Корреспондент A вычисляет элементu ( н ф ^ 1 ) , . . . , н ф ^ ) ) u - 1 = [ v , u ].Корреспондент B вычисляет тот же самый элемент [v, u] из равенстваv v ^ ( f U ) , . . . , н ф ^ ) ) - 1 = [v,u].Таким образом пользователи A и B генерируют общий известный только им ключK = нф[v, u].Мы здесь не приводим и не обсуждаем конкретные свойства групп кос Артинавыбранных авторами [4] в качестве платформы своего протокола. Относительно этихсвойств см. классическую работу А. А. Маркова [5], монографию П. Дехорноя [6], обзорВ. Я. Лина [7] или ещё какую-нибудь монографию, посвящённую группам кос Артина.О криптографии на группах кос Артина, включая подробное описание протоколаАншель - Аншеля - Голдфельда, см. обзоры П. Дехорноя [8] и К. Мальбурга [9].Нам важно выделить некоторые основные, с нашей точки зрения, свойства группыкос Артина, позволяющие рассматривать приведённые построения как заслуживаю-щие внимания. Эти свойства следующие:- Группы при любом n являются конечно определёнными, то есть порождаютсяконечнымимножествами порождающих элементов, все соотношения между кото-рыми следуют из конечного множества определяющих соотношений.- Группы обладают нормальными формами однозначной записи элементов, пе-реход к которым от записей в виде групповых слов эффективен.- В группах кос нахождение сопрягающего элемента u по элементу g и нормальнойформе н ф ^ и ) сопряжённого к нему элемента является трудноразрешимой задачей.Более того, она остаётся трудноразрешимой при замене одного элемента на наборэлементов.Отмеченные свойства так или иначе присутствуют в большинстве работ. Хочет-ся ещё заметить, что в работе [4] фактически впервые существенно использоваласьнекоммутативность группы. Более того, представленный протокол не являлся пере-носом известных протоколов теоретико-числового характера. Подобные переносы, на-пример, в матричные группы уже были известны, но не дали толчка для последующегоразвития.В последующей работе автора совместно с С.Ю. Ерофеевым «О построении воз-можно односторонних функций на основе алгоритмической неразрешимости проблемыэндоморфной сводимости в свободных метабелевых группах» мы перейдём к конкрет-ным предложениям. В качестве платформы для построения криптографических при-митивов, систем и протоколов выбираем свободные метабелевы группы. Свободнаяметабелева группа Mn ранга n, где n - натуральное число, определяется как фактор-группа Fn/F^ свободной группы Fn ранга n по второму коммутанту F". Напомним,что коммутантом G' произвольной группы G называется её подгруппа, порождённаявсеми коммутаторами [g, f ] элементов группы G. Подгруппа G' нормальна в груп-пе G, фактор-группа G / G ' по ней абелева. Второй коммутант G" определяется каккоммутант от коммутанта (G')'. Он также нормален в группе G. Группа G называетсяметабелевой, если G" тривиален. В этом случае коммутант G' абелев, а группа G яв-ляется расширением абелевой нормальной подгруппы G' с помощью абелевой фактор-группы G / G ' . Отсюда её название.Группа Mn называется свободной метабелевой группой ранга n, потому что в нейесть базис Xn = {ж1 , . . . , ж п } , состоящий из n элементов, такой, что любое отобра-жение этого базиса Xn ^ G в произвольную метабелеву группу G однозначно про-должается до гомоморфизма Mn ^ G. Говорят также, что группа Mn - свободнаягруппа ранга n многообразия всех метабелевых групп A2 . Базис Xn называют множе-ством свободных порождающих группы Mn . О многообразиях групп см. монографиюХ. Нейман [10].В качестве алгоритмической проблемы возьмём проблему E ( M n ) эндоморфной сво-димости в группе Mn . Известно [11, 12], что она алгоритмически неразрешима придостаточно большом n ^ n0. Основываясь на её алгоритмической неразрешимости,укажем метод построения функции fn : Mn ^ Mn , претендующей на роль односто-ронней функции. Наконец, используя платформу Mn и функцию f n , предложим про-токол аутентификации с нулевым разглашениемпользователя в системе. Подобныйпротокол уже предлагался в [13], причём также со ссылкой на работу автора [12].Однако так просто воспользоваться группами и функциями из [12] в данном случаенельзя. Мы покажем, что для криптостойкости протокола аутентификации необходимаалгоритмическая неразрешимость более сильной проблемы двукратной эндоморфнойсводимости.Важно отметить, что алгоритмическая неразрешимость проблемы эндоморфнойсводимости E(Mn ) при n ^ n0, установленная в [12], базируется на алгоритмическойнеразрешимости 10-й Проблемы Гильберта о существовании алгоритма, определяю-щего по произвольному уравнению вида d(Z1 , . . . , Zk) = 0, где d(Z1 , . . . , Zk) -многочленс целыми коэффициентами, имеет ли это уравнение решение в целых числах. Алгорит-мическая неразрешимость 10-й Проблемы Гильберта установлена Ю. В. Матиясевичемв [14] (полное доказательство в [15], см. также [16]).В данной работе мы показываем, что диофантов язык является достаточно уни-версальным. На нем записываются функции и уравнения, фигурирующие во многихкриптографических системах и протоколах, в том числе в системе RSA и протоколах,основанных на понятии дискретного логарифма в мультипликативных группах конеч-ных полей. Диофантов язык позволяет объединять эти системы и протоколы в единоецелое, что даёт возможность ввести в рассмотрение диофантову криптографию.В заключение отметим, что построение криптографических систем и протоколов,основанных на неразрешимых и трудноразрешимых проблемах, осуществлялось мно-гими авторами (см., например, монографии [1, 2], обзор [8], статьи [17-21]).1. Бесконечные группы и алгоритмические проблемыРассмотрим постановку алгоритмических проблем только для групп, хотя аналогиэтих проблем легко формулируются и для других алгебраических и не только алгеб-раических систем. Заметим, что истоки этих проблем лежат в топологии.1.1. П о с т а н о в к а а л г о р и т м и ч е с к и х п р о б л емВ самых общих чертах алгоритмическая проблема выглядит следующим образом.Имеется теоретико-групповое свойство P, которое может относиться как к отдельнымэлементам, так и к наборам элементов, к подгруппам или подмножествам группы,к различным группам и т. п. Требуется определить, обладают ли свойством P указан-ные объекты. Более точно проблема формулируется как следующий вопрос: существу-ет ли алгоритм, определяющий за конечное число шагов, удовлетворяет объект Oсвойству P или нет?При постановке проблемы упоминание алгоритма часто опускается. Говорят, чтопроблема алгоритмически разрешима (или просто разрешима), если такой алгоритмсуществует, и неразрешима в противном случае.При постановке алгоритмической проблемы предполагается, что группа, её элемен-ты, подгруппы, подмножества, словом, объекты, для которых ставится проблема, за-даны каким-либо эффективным образом. Способов эффективного задания существуетдовольно много. Далее опишем некоторые из них.Классические алгоритмические проблемы теории групп сформулированы в началеXX столетия Максом Деном. Они ставились для класса конечно определённых групп.Это означает, что группа G, для которой ставится проблема, задана своим конечнымпредставлением видаP ( G ) = (жь . . . , ж г а | Г 1 , . . . , Г т ) . (1)Иначе говоря, группа G является фактор-группой F n / R свободной группы с ба-зисом (множеством свободных порождающих элементов) { x 1 , . . . , x n } относительнонормального замыкания R = нз(г1 , . . . , rm) , то есть минимальной нормальной под-группы группы Fn , содержащей элементы r 1 , . . . , rm. Элементы r 1 , . . . , rm записывают-ся в виде групповых слов от порождающих x 1 , . . . , Напомним, что групповое словозаписывается как слово от элементов ,... ,x±±1. Элементы r 1 , . . . , rm называютсяопределяющими словами. Иногда представление (1) записывают в видеP ( G ) = ( X 1 , . . . , Xn | r1 = l , . . . , rm = 1 ) . (2)Смысл задания остается тем же самым, равенства r = 1 для i = 1 , . . . , m называютопределяющими соотношениями группы G.Через H' обозначим коммутант группы H, то есть подгруппу, порождённуюв группе H всеми коммутаторами её элементов. Коммутант H' является нормальнойподгруппой группы H, фактор-группа H/H' по которой абелева. Более того, комму-тант- наименьшая подгруппа с этим свойством, то есть если фактор-группа H /Nпо какой-либо нормальной подгруппе N группы H абелева, то N обязательно содер-жит H'.Элементы нормального замыкания R = нз(г1 , . . . , rm) допускают описание какгрупповые слова следующего вида:U = П ( r j ) j , (3)где ij G { 1 , . . . , m } ; gj G F„; ej = ±1 для j = 1 , . . . , k.Естественно определяется канонический гомоморфизм Fn ^ G, переводящий про-извольный элемент g группы Fn в элемент gR группы G. Группа G имеет каноническоемножество порождающих элементов y^ = ЖiR для i = 1 , . . . , n. Любой элемент g груп-пы G можно поэтому записать в виде группового слова g = g ( y 1 , . . . , yn) . Однако частопорождающие y^ группы G обозначают теми же буквами ж^, что и их прообразы. Эле-мент g записывается в виде g ^ , . . . , жп).Классические алгоритмические проблемы Дена формулируются следующимобразом.1. П р о б л е м а равенства. Определить по двум групповым словам g = g ^ , . . . , жп)и f = f ( ж 1 , . . . , жп), записывают ли они один и тот же элемент группы G, заданной сво-им конечным представлением (1) или (2). Другими словами, верно ли, что в группе Gсправедливо равенство g = f. Иногда, чтобы указать группу, пишут g =g f.Рассмотрение проблемы равенства может быть сведено к случаю, когда один изэлементов равен 1. Действительно, равенство g =g f выполнено тогда и только тогда,когда g f - 1 =g 1. Оно может быть также перенесено в группу Fn , поскольку равен-ство g =g 1 равносильно тому, что слово g = g ^ ! , . . . ^ ^ как элемент группы Fnпринадлежит нормальной подгруппе R.Первые примеры конечно определённых групп с неразрешимой проблемой равен-ства были построены в 50-е годы XX столетия П. С. Новиковым в [22, 23]. Впоследствиитаких примеров стало достаточно много.2. П р о б л е м а с о п р я ж ё н н о с т и . Определить, задают ли два слова g = g ^ , . . . , жп)и f = f ( ж 1 , . . . , жп) сопряжённые элементы группы G. Другими словами, существуетли элемент h группы G, такой, что gh =g f.Разрешимость проблемы сопряжённости в группе G, очевидно, влечет разреши-мость в G проблемы равенства. Действительно, элемент g группы G равен 1 тогда итолько тогда, когда g сопряжён с 1. Обратное утверждение в общем случае неверно.Существуют конечно определённые группы, в которых проблема равенства разреши-ма, а проблема сопряжённости неразрешима. Первые примеры групп с неразрешимойпроблемой сопряжённости, некоторые из которых имеют разрешимую проблему ра-венства, построены в [23].3. П р о б л е м а и з о м о р ф и з м а . Определить по двум представлениям конечно опре-делённых групп G и H, изоморфны эти группы илинет.Неразрешимость проблемы изоморфизма в классе конечно определённых группустановлена С. И. Адяном [24].Отметим ещё одну проблему, которая хотя и не была явно сформулирована Деном,но впоследствии стала одной из основных.4. П р о б л е м а в х о ж д е н и я . Определить для произвольного элемента g данной ко-нечно определённой группы G и произвольной её конечно порождённой подгруппы H,принадлежит g подгруппе H или нет.Проблему вхождения часто называют обобщённой проблемой равенства. Очевидно,что её разрешимость влечет разрешимость проблемы равенства, равносильной про-блеме вхождения в тривиальную подгруппу. Выделяют также проблему вхожденияв фиксированную конечно порождённую подгруппу.Известные результаты и открытые проблемы алгоритмического характера в теориигрупп освещены в обзорах [25-27].В некоторых важных классах групп классические алгоритмические проблемы раз-решимы. Например, все они разрешимы в классах свободных и конечно порождён-ных абелевых групп. Многие проблемы разрешимы в классах нильпотентных и поли-циклических групп. Имеются важные результаты о разрешимости алгоритмическихпроблем в матричных группах. Большое внимание уделено разработке практическихалгоритмов решения алгоритмических проблем в группах (см. по этому поводу моно-графии [28, 29] и обзорную статью [30]).Таким образом, первоначально при постановке алгоритмических проблем рассмат-ривались только конечно определённые группы, элементы которых записываются в ви-де групповых слов. Впоследствии класс групп, для которых ставятся алгоритмическиепроблемы, был расширен как за счёт включения в него рекурсивно определённых групп,в которых множество порождающих элементов конечно, а множество определяющихсоотношений может быть бесконечным рекурсивно перечислимым множеством, таки за счёт конечно порождённых подгрупп каких-нибудь известных хорошо заданныхгрупп. Например, группа может быть задана своим конечным порождающим множе-ством в матричной группе над конструктивным полем или более общо - над кольцом.Группа может также быть задана как конструктивный объект в смысле теории моде-лей. Она может определяться и другими эффективными способами.Класс конечно порождённых матричных групп над конструктивными кольцамипредставляет особый интерес. Проблема равенства в таких группах, очевидно, раз-решима. Однако другие проблемы даже в достаточно просто устроенных матричныхгруппах могут быть неразрешимыми.Одним из самых известных является пример К. А. Михайловой матричной груп-пы с неразрешимой проблемой вхождения, описанный в работе [31]. Эта группа естьпрямое произведение G = F2 х F2 двух копий свободной группы ранга 2. Она допуска-ет точное представление матрицами порядка 4 над кольцом целых чисел Z. Опишемодно из возможных таких представлений. Хорошо известно (см., например, [32, 33]),что представление (оно называется представлением Санова) группы F2 матрицамипорядка 2 над Z, заданное на порождающих элементах x 1 , x 2 группы F2 следующимотображением, точное:Точное представление группы G матрицами 4-го порядка соответствует схемесогласно которой первая копия группы F2 представляется верхней левой клеткой, авторая - нижней правой (остальные матричные элементы в представлении множите-лей группы G, как у единичной матрицы).Неразрешимость проблемы вхождения в группе G основывается на существовании2-порождённой конечно определённой группы с неразрешимой проблемой равенства.Пусть такая группа K задана представлением P ( K ) = (x1, x2 | r 1 , . . . , rm) . Рассмотримв группе G подгруппу H, порождённую элементами вида f1 = (x1 , x 1 ) , f2 = (x2 , x 2 ),= (rj, 1) для i = 1 , . . . , m. Легко показать, что элемент g = ($', 1) принадлежит Hтогда и только тогда, когда принадлежит нормальной подгруппе R = НЗ(Г1, . . . , rm)группы F2. Неразрешимость проблемы равенства в группе K = F 2 / R влечет неразре-шимость проблемы вхождения в подгруппу H группы G.2. Неразрешимые и трудноразрешимые алгоритмические проблемыкак основа для построения криптографических систем и протоколовКлассические алгоритмические проблемы Дена уже неоднократно предлагались вкачестве основы для построения на группах криптографических примитивов, системи протоколов. Традиционно наибольшее внимание привлекает в этой связи проблемасопряжённости. В уже упоминавшейся работе М. Аншеля и др. [4] основой крипто-стойкости протокола служит трудноразрешимость проблемы сопряжённости в группахкос Артина. Заметим, что проблема сопряжённости в них разрешима. Это установленов работе Гарсайда [34]. Тем не менее, так как эффективный алгоритм для её решениядо сих пор не найден, эта задача продолжает считаться трудноразрешимой (см. пуб-ликации [19, 35, 36]). Проблема равенства фигурирует в работах [37-39]; проблемавхождения - в работе [18]. Этот список - только малая часть работ, обсуждающих ис-пользование алгоритмических проблем в криптографии.2.1. П р о б л е м ы п о и с к аАбсолютное большинство работ в криптографии, основанной на группах, в которыхрассматриваются трудноразрешимые и неразрешимые проблемы, связано с решениемтак называемых проблем поиска (англ. вариант - search problems). Например, еслив основе криптографического примитива лежит проблема сопряжённости, то обычно,как это происходит, например, в протоколе Аншель - Аншеля- Голдфельда, известно,что данные элементы или наборы элементов, если речь идёт о наборах, сопряжены.Задача заключается в эффективном нахождении сопрягающего элемента. В общихчертах, если алгоритмическая проблема ставится для объекта O относительно свой-ства P, то проблема поиска выясняет в случае, если O обладает свойством P, до-казательство, или ещё говорят - свидетельство этого, справедливость которого лег-ко проверить. Например, если известно, что элемент f группы G принадлежит под-группе H, порождённой элементами h1 , . . . , h k , то требуется найти запись f в видегруппового слова от этих элементов. Для проблемы равенства, аналогично, требует-ся найти выражение слова u = u ( x 1 , . . . , x n ) от порождающих элементов x 1 , . . . , x nсвободной группы Fn , записывающего тривиальный элемент группы G = Fn / R , гдеR = НЗ(Г1, . . . , rm) -его выражение в виде (3). Это, конечно, можно сделать простымперебором, но сейчас речь идёт о реальных вычислениях, когда такой перебор уже неможет рассматриваться как эффективный.Если алгоритмическая проблема, взятая за основу криптографического примити-ва, не допускает полиномиального алгоритма, то не существует также полиномиаль-ного ограничения длины входа от длины наблюдаемого выхода, значит, нельзя орга-низовать полиномиальный перебор возможных входов, основываясь на такой оценке.Если же основная алгоритмическая проблема неразрешима, то невозможно вообщедать какую-либо оценку длины входа, зная длину выхода. В этом случае неприменимметод «грубой силы», то есть полного перебора.Это рассуждение носит, конечно, самый общий характер. В теории сложности по-добные вопросы получают строгое обоснование. Этому в основном посвящена моно-графия [2].3. О сложности алгоритмических проблеми соответствующих им проблем поискаСовременная теория сложности зародилась в 70-е годы XX столетия. Для нас важ-ное значение имеет прежде всего понятие временной сложности. Действительно, крип-тография, основанная на группах, как, впрочем, и всякая другая область, ориентиро-ванная на практическое использование, должна заботиться о реальном времени вы-числений в разрабатываемых ею протоколах. Значит, нам небезразлично, сколь долгобудет работать алгоритм. В то же время при практическом использовании разрабаты-ваемых протоколов различные входящие в них параметры, в том числе ключи, выбира-ются случайным образом. Значит, необходимо заботиться не только о сложности в худ-шем случае, когда проблему нельзя эффективно решить при каких-то специфическихданных, но и о сложности, проявляющейся при случайном выборе данных. Здесь раз-рабатываются два основных подхода, связанные с определением понятий сложностив среднем и генерической сложности. Перейдём к общему схематическому описанию,отсылая за деталями к монографиям [1, 2, 40], сборнику [41] и статьям [42-45].Итак, рассматриваем три основных вида сложности:- сложность по худшему случаю;- сложность в среднем;- генерическую сложность.О классическом понятии сложности по худшему случаю см., например, моногра-фию [40]. Класс сложности C определяется спецификацией модели вычислений (длянас это многоленточная машина Тьюринга), типом вычислений (то есть использовани-ем либо детерминированной, либо вероятностной машины Тьюринга), а также ресур-сами, объём которых необходимо контролировать (обычно это время работы алгорит-ма, пространство, занимаемое данными, или же то и другое). Данные спецификациипозволяют определить функцию сложности f (n), где n - размер входа, оценивающуюобъём необходимых ресурсов для вычисления соответствующего ему выхода. Мы неприводим точного определения, замечая только, что оно позволяет говорить о ли-нейной, полиномиальной или экспоненциальной сложности алгоритма. Как правило,считается, что линейные, квадратичные и в иных случаях полиномиальные для малыхстепеней алгоритмы достаточно быстры, а экспоненциальныемедленны. Конечно, этовсе относительно и требует конкретизации в каждом отдельном случае.Кратко остановимся на понятии сложности в среднем. Для её определения необхо-димо, чтобы на пространстве всех возможных входов была задана функция распреде-ления вероятностей или хотя бы какая-нибудь аддитивная неотрицательная функция.При её задании сложность в среднем чаще всего оценивается математическим ожида-нием объёма ресурсов, необходимым для работы алгоритма на случайно выбранномвходе. Опять же можно говорить о линейной, полиномиальной и экспоненциальнойсложности в среднем. На конечных множествах, как правило, задают равномернуюфункцию распределения. В бесконечном случае вопрос о задании такой функции ста-новится более тонким. Например, задача определения «случайного» элемента группырассматривалась многократно. Даже для конечных групп этот вопрос решается дале-ко не очевидным путём. Действительно, что считать случайным выбором? Уже давностало понятным, что при учёте алгебраической структуры группы её элементы как быстановятся «неравноправными» (см. по этому поводу [46]).В работе [47] предложен следующий возможный общий подход к построению об-суждаемого распределения на бесконечной конечно порождённой группе. Пусть груп-па G наделена функцией натуральнозначной длины l : G - N, такой, что множество Srвсех элементов g группы G длины l(g) = r для любого натурального числа r конечно.Считаем также, что So = {1}. Функция l в конкретных случаях может называть-ся функцией размера, сложности и т. п. Множество Sr естественно называть сферойрадиуса r. Аналогичным образом определяется шар Br радиуса r, состоящий из всехэлементов g группы G, для которых l(g) ^ r. Затем берётся одна из функций рас-пределения f : N U { 0 } -У R, определённая на множестве натуральных чисел с нулем.Например, это может быть функция Пуассона, биномиального или экспоненциальногораспределения. Предполагается только её невырожденность, т. е. что для любого r G Nвыполняется f (r) = 0. Для задания функции распределения вероятностей p : G - [0,1]для любого r полагаем p(Sr ) = f (r). Далее для любого g G Sr полагаем p(g) = 1 / f (r),т. е. все элементы сферы Sr считаются равновероятными. Это определяет функциюраспределения вероятностей на всей группе G, что, в свою очередь, даёт возможностьговорить о сложности в среднем алгоритма.Обычно в качестве значения l(g) для элемента g конечно порождённой группы Gс фиксированным конечным множеством X порождающих элементов берётся длинакратчайшей записи элемента g в виде группового слова от этих порождающих. Рассто-янием d(g, f) между элементами g и f группы G считается значение l ( g f - 1 ) . Группа Gтаким образом превращается в метрическое пространство, изоморфное графу Кэли,соответствующему выбранной системе порождающих элементов. Данная метрика на-зывается словарной; длина элемента относительно неё есть его расстояние от 1.Понятие сложности вычислений в среднем относительно возможных практиче-ских приложений в криптографии, основанной на группах, обладает рядом недо-статков. Во-первых, возникает вопрос адекватного выбора функции распределенияf : N U { 0 } - [0,1]. Во-вторых, алгоритм может оказаться таким, что он работаетчрезвычайно долго только на малой доле возможных входов, а на остальных входахон достаточно быстр. Усреднённое время его работы будет в этом случае не показа-тельным, так как при случайном выборе «плохие» входы будут встречаться крайнередко. Хочется привести в этой связи аналогию с симплекс-методом. В работе [48] по-казано, что «плохие» входы для него очень специфичны, поэтому их пренебрежимомало. Это объясняет тот факт, что на практике симплекс-метод вполне хорошо себязарекомендовал; он широко используется, в то время как знаменитый полиномиаль-ный алгоритм Хачияна [49] имеет в основном теоретическое значение. Более точно,А. М. Вершик и П. В. Спорышев в [50] и независимо С. Смейл в [51] показали, чтосимплекс-алгоритм работает с линейной сложностью на множестве полной меры.По описанным выше причинам представляется особенно важным понятие генери-ческой сложности. Для его введения необходимо, чтобы на множестве всех входовбыла определена мера со значениями в [0,1]. Это не обязательно должна быть функ-ция распределения вероятностей. Генерическим называется множество полной меры,дополнение к которому имеет меру 0. Работа [45] представляет точное определениегенерической сложности. В ней же установлено, что для широкого класса конечно по-рождённых групп классические алгоритмические проблемы равенства, сопряжённостии вхождения имеют линейную сложность при их ограничении на некоторое генериче-ское подмножество (см. также работу [52]).Перейдём к определениям. Рассмотрим множество всех слов (включая пустое сло-во) Е* в конечном алфавите Е, состоящем не менее чем из двух букв. Это множествоявляется свободным моноидом со множеством свободных порождающих Е. Так как наэлементах Е* естественно определено понятие длины, можно ввести для любого неот-рицательного целого числа r понятия сферы Sr и шара Br радиуса r, как это объясненовыше. Очевидно, что эти множества конечны и непусты.Пусть V - произвольное подмножество моноида S*. Относительной плотностьюмножества V в сфере Sr называется отношение- (V ) = ™ . (4)где | | означает число элементов.Аналогично вводится понятие относительной плотности множества V в ша-ре Br:|V n Br|РВГ ( V ) = |B | . (5)Будем использовать для определения асимптотической плотности функцию (5),хотя совершенно аналогично можно дать определение, основываясь на функции (4).Определение 1. Асимптотической плотностью подмножества V моноида S*называется верхний пределP ( V ) = N R N P B R ( V ) . (6)Если в (6) существует предел, то он обозначается через p(V) и называется стро-гой асимптотической плотностью множества V. В этом случае нас интересует ско-рость сходимости к пределу p(V) последовательности { p B r ( V ) } r e N . Будем говорить,что сходимость последовательности экспоненциально быстрая, если существуют чис-ла 0 ^ а < 1 и C ^ 0, такие, что для любого r имеет место оценка|p(V) - рБг (V)| ^ Car.Определение 2. Подмножество V множества S* называется генерическим, еслиp(V) = 1, и строго генерическим, если сходимость pBr (V) p(V) экспоненциальнобыстрая.Если V - генерическое множество, то дополнение к нему V' = S* \ V называетсяпренебрежимым. В этом случае p(V') = 0.Определения 1 и 2 легко распространяются на случай, когда вместо множества S*рассматривается множество (S*)k наборов из k элементов этого множества для k ^ 2.кДлиной набора g = ( g 1 , . . . , gk) считаем сумму длин его компонент: /(g) = /(gj).i=1Можно использовать также другое определение, согласно которому/(g) = max{/(g^) : i = 1 , . . . , k}.Часто алгоритмические проблемы в группах трактуют как подмножества видаD С (S*)k для некоторого алфавита S и натурального числа k. Например, если в каче-стве S взять множество символов, обозначающих порождающие элементы группы Gи формальные обратные к ним, то элементы моноида S* могут рассматриваться какгрупповые слова от порождающих элементов группы G. Рассмотрим подмножествоD1(G) С S*, определяющее в группе G тривиальный элемент. Проблема равенствав группе G - э т о вопрос о принадлежности произвольного слова u Е S* подмноже-ству D1 ( G ) . Проблема сопряжённости на этом языке записывается как D (G) С (S*)2и состоит из таких пар (u,v) слов в алфавите S, которые определяют сопряженныев группе G элементы. Проблема вхождения относительно подгруппы H, порождён-ной элементами h 1 , . . . , h k - 1 , имеет вид DH ( G ) С (E*)k, DH = {(u, h 1 , . . . , h k - 1 ) } , гдеu определяет элемент подгруппы H. При этом подгруппа H считается фиксирован-ной. Можно считать также, что фиксировано множество { h 1 , . . . , h k - 1 } порождающихеё элементов. В этом случае на вход работы алгоритма должно подаваться слово u.Если рассматривать проблему вхождения в группе G, то элементы h1 , . . . ,hk- 1 ужене должны считаться фиксированными. При этом, поскольку число k в общем слу-чае не ограничено, проблему вхождения необходимо рассматривать как подмножествобесконечной степени (Е*)т е.Аналогичным образом можно записать широкий круг алгоритмических проблемотносительно конечно порождённых групп.Определение 3. Алгоритм A решает алгоритмическую проблему D С (E*)k с ге-нерической сложностью C, если существует генерическое подмножество V С (E*)k,такое, что на любом входе из V алгоритм A работает со сложностью C. Если мно-жество V можно выбрать строго генерическим, то говорят, что алгоритм A решаетпроблему D со строго генерической сложностью C.Обращаем внимание на тот факт, что алгоритм A может быть частично опреде-лённым, то есть он может оказаться неопределённым на некоторых входах, которыеможно включить в дополнение V' генерического множества V из определения 3. Мо-жет так получиться, что проблема D в целом на группе G алгоритмически нераз-решима, а в то же время она генерически разрешима с приемлемой сложностью C.Опыт показывает, что это случается довольно часто и для широкого круга алгорит-мических проблем (см. по этому поводу [53, 54]). Опять же можно привести аналогиюс симплекс-методом из линейного программирования, который на обсуждаемом языкеоказывается генерически быстрым.В практических приложениях выбор данных осуществляется, как правило, случай-ным образом. Если генерическая сложность какого-либо алгоритма незначительна, тоалгоритм практически всегда применим и достаточно быстр, и может быть использо-ван в практических приложениях.4. Диофантова криптографияДиофантовым уравнением от n переменных называется выражение видаd « 1 , . . . , < n ) = 0, (7)где d(Z1 , . . . , С™) - многочлен с целыми коэффициентамиот обозначенных независимыхкоммутирующих переменных. Множество всех таких многочленов составляет кольцоЛп = Z [ ( 1 , . . . , Zn]. Кольцо Лт при m ^ n естественно вложено в кольцо Лп. Объедине-ние всех таких колец обозначим через Л = Z[Z1 , . . . , Zn , . . . ] .На Втором математическом конгрессе, состоявшемся в 1900 г. в Париже, выдаю-щийся математик Д. Гильберт изложил свои знаменитые 23 математические проблемыдля математиков XX столетия. Впоследствии их стали называть Проблемами Гиль-берта. Среди этих проблем присутствовала 10-я Проблема о существовании эффек-тивной процедуры, определяющей за конечное число шагов, имеет ли произвольноедиофантово уравнение целочисленные корни. Говоря современным языком, 10-ю Про-блему Гильберта можно перефразировать следующим образом: существует ли алго-ритм, определяющий по произвольному диофантову уравнению (7) его разрешимостьв целых числах.Алгоритмическая неразрешимость 10-й Проблемы Гильберта установленаЮ. В. Матиясевичем в работах [14, 15]. Тем самым им были успешно завершены уси-лия многих математиков, из которых наиболее весомый вклад в решение проблемывнесли Д. Робинсон, М. Девис и Х. Путнам.Вернемся к криптографии. Обычно криптографическая система основывается натрудноразрешимой математической проблеме, часто теоретико-числового характера.Приведём список наиболее популярных проблем такого сорта и покажем, что с каж-дой из таких проблем можно связать диофантово уравнение таким образом, что лю-бое решение этого уравнения даёт возможность эффективно выписать решение со-ответствующей проблемы и наоборот, решение проблемы приводит к эффективномурешению соответствующего диофантова уравнения. Так как любое конечное множе-ство диофантовых уравнений, более того, любое множество диофантовых уравненийот ограниченного числа переменных, которое, как известно из теоремы Гильберта, эк-вивалентно своей конечной подсистеме, равносильно одному диофантову уравнению,которое легко получается из левых частей уравнений вида (7), если взять квадратыэтих левых частей и приравнять их сумму к 0, то можно эффективно сопоставлять лю-бому конечному мно

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

криптография, основанная на группах, алгоритмическая проблема, проблема поиска, генерическая сложность, диофантов язык, диофантова криптография, свободная метабелева группа, проблема эндоморфной сводимости, group-based cryptography, algorithmic problem, search problem, generic complexity, diophantine language, diophantine cryptography, free metabelian group, endomorphism problem

Авторы

ФИООрганизацияДополнительноE-mail
Романьков Виталий АнатольевичОмский государственный университет им. Ф. М. Достоевского, г. Омскпрофессор, доктор физико-математических наук, заведующий кафедройromankov48@mail.ru
Всего: 1

Ссылки

Myasnikov A., Shpilrain V., and Ushakov A. Group-based cryptography. (Advances courses in Math., CRM, Barselona). Basel, Berlin, New York: Birkhauser Verlag, 2008. 183 p.
Myasnikov A., Shpilrain V., and Ushakov A. Non-commutative cryptography and complexity of group-theoretic problems. (Amer. Math. Soc. Surveys and Monographs). Providence, RI: Amer. Math. Soc., 2011. 385 p.
www.grouptheory.info/PersonalPages/Shpilrain,Vladimir/CryptologyePrintArchive
AnshelI., AnshelM., and Goldfeld D. An algebraic method for public-key cryptography // Math. Res. Lett. 1999. V. 6. P. 287-291.
Марков А. А. Основы алгебраической теории кос // Труды Матем. ин-та АН СССР. 1945. Т. 16. С. 3-54.
Dehornoy P. Braids and self-distributivity. (Progress in Math. 192). Basel, Berlin, New York: Birkhauser Verlag, 2000. 623 p.
Лин В. Я. Косы Артина и связанные с ними группы и пространства // Итоги науки и техн. Алгебра. Геометрия. Топология. Т. 17. М.: ВИНИТИ, 1983. С. 159-227.
Dehornoy P. Braid-based cryptography // Group theory, statistics and cryptography. Contemp. Math. V.360. Providence, RI: Amer. Math. Soc., 2004. P. 5-33.
Mahlburg K. An overview of braid group cryptography. 2004. www.math.wisc.edu/~boston/ mahlburg.pdf
Нейман Х. Многообразия групп. М.: Мир, 1974. 264 с.
Романьков В. А. О неразрешимости проблемы эндоморфной сводимости в свободных нильпотентных группах и в свободных кольцах // Алгебра и логика. 1977. Т. 16. №4. С.457-471.
Романьков В. А. Об уравнениях в свободных метабелевых группах // Сиб. матем. ж. 1979. Т. 40. №3. С. 671-673.
Grigoriev D. and Shpilrain V. Zero-knowledge autentification schemes from actions on graphs, groups and rings // Ann. Pure Appl. Logic. 2010. V. 162. P. 194-200.
Матиясевич Ю. В. Диофантовость перечислимых множеств // Докл. АН СССР. 1970. Т. 191. №2. С. 279-282.
Матиясевич Ю. В. Диофантово представление перечислимых предикатов // Изв. АН СССР. Сер. матем. 1971. Т. 35. №1. С. 3-30.
Матиясевич Ю. В. Десятая проблема Гильберта. М.: Наука, 1993. 223 с.
Shpilrain V. and Zapata G. Using decision problems in public key cryptography // Groups. Complexity. Cryptology. 2009. V. 1. P. 33-40.
Shpilrain V. and Zapata G. Using the subgroup membership problem in public key cryptography // Contemp. Math. V. 418. Providence, RI: Amer. Math. Soc., 2006. P. 169-179.
Shpilrain V. and Zapata G. Combinatorial group theory and public key cryptography // Applicable Algebra in Engineering Communication and Computing. 2006. V. 17. P. 291-302.
Kurt Y. A new key exchange primitive based on the triple decomposition problem // Preprint: http://eprint.iacr.org/2006/378
Birget J.-C., Magliveras S., and Sramka M. On public-key cryptosystems based on combinatorial group theory // Tatra Mountains Math. Publ. 2006. V. 33. P. 137-148.
Новиков П. С. Об алгоритмической неразрешимости проблемы тождества слов в теории групп // Труды Матем. ин-та АН СССР. 1955. Т. 44. С. 3-143.
Новиков П. С. Неразрешимость проблемы сопряженности в теории групп // Изв. АН СССР. Сер. матем. 1954. Т. 18. №6. С. 485-524.
Адян С. И. Неразрешимость некоторых алгоритмических проблем в теории групп // Труды Моск. матем. общества. 1957. Т. 6. С. 231-298.
Ремесленников В. Н., Романьков В. А. Теоретико-модельные и алгоритмические вопросы теории групп // Итоги науки и техн. Алгебра. Геометрия. Топология. Т. 21. М.: ВИНИТИ, 1983. С. 3-79.
Адян С. И., Дурнев В. Г. Алгоритмические проблемы для групп и полугрупп // Успехи матем. наук. 2000. Т. 55. С. 3-94.
Miller III C. F. Decision problems for groups - survey and reflections // Algorithms and Classification in Combinatorial Group Theory. Berlin, Heidelberg, New York: Springer Verlag, 1992. P. 1-60.
Sims C. C. Computation with finitely presented groups. Cambridge: Cambridge Univ. Press, 1994. 604 p.
HoltD.F., EickB., and O'Brien E. A. Handbook of computational group theory. London: Chapman & Hall/CRC, 2005. 414 p.
Detinko A., Eick B., and Flannery D. Computing with matrix groups // London Math. Soc. Lect. Notes Ser. 2011. V.387. P. 256-270.
Михайлова К. А. Проблема вхождения для прямых произведений групп // Докл. АН СССР. 1958. Т. 119. С. 1103-1105.
Каргаполов М. И., Мерзляков Ю. И. Основы теории групп. М.: Лань, 2009. 288 с.
Курош А. Г. Теория групп. М.: Физматгиз, 2008. 808 с.
Garside F. A. The braid group and other groups // Quart. J. Math. 1969. V. 20. No. 78. P. 235-254.
Gebhardt V. Conjugacy search in braid groups from a braid-based cryptography point of view // Applicable Algebra in Engineering Communication and Computing. 2006. V. 17. P. 219-238.
Gebhardt V. A new approach to the conjugacy problem in Garside groups // J. Algebra. 2005. V.292. P. 282-302.
Petrides G. Cryptoanalisis of the public key cryptosystem based on the word problem on the Grigorchuk groups // LNCS. 2003. V. 2898. P. 234-244.
Magyarik M. R. and Wagner N. P. A public key cryptosystem based on the word problem // LNCS. 1985. V. 196. P. 19-36.
Fine B., Habeeb M., Kahrobaei D., and Rosenberger G. Survey and open problems in noncommutative cryptography // JP J. Algebra, Number Theory and Applications. 2011. V. 21. P. 1-40.
Papadimitriou C. Computation complexity. Boston: Addison-Wesley, 1994. 523 p.
Computational complexity theory / eds. S. Rudich and A. Wigderson. Amer. Math. Soc. Institute for Advanced Study, IAS/Park City Math. Series. V. 10. Providence, RI: Amer. Math. Soc., 2004. 389 p.
Gurevich Y. Average case comleteness // J. Comput. Syst. Sci. 1991. V. 42. P. 346-398.
Levin L. Average case complete problems // SIAM J. Comput. 1986. V. 15. P. 285-286.
Kapovich I., Myasnikov A., Shupp P., and Shpilrain V. Average-case complexity and decision problems in group theory // Adv. Math. 2005. V. 190. P. 343-359.
Kapovich I., Myasnikov A., Shupp P., and Shpilrain V. Generic-case complexity, decision problems in group theory and random walks // J. Algebra. 2003. V. 264. P. 665-694.
Celler F., Leedham-Green C. R., Murray S. H., et al. Generating random elements of a finite group // Comm. Algebra. 1995. V.23. No.3. P. 4931-4948.
BorovikA., Myasnikov A., and Shpilrain V. Measuring sets in infinite groups // Contemp. Math. V. 298. Providence, RI: Amer. Math. Soc., 2002. P. 21-42.
Klee V. and Minty G. How good is the simplex algorithm? // Inequalities. Proc. Third. Symp., Univ. California. California: Academic Press, 1972. P. 159-175.
Хачиян Л. А. Полиномиальный алгоритм в линейном программировании // Докл. АН СССР. 1979. Т. 244. №5. С. 1093-1096.
Вершик А. М., Спорышев П. В. Ограничение среднего числа шагов в симплекс-методе и проблемы асимптотической интегральной геометрии // Докл. АН СССР. Т. 271. № 5. С.1044-1048.
Smale S. On the average number of steps of the simplex method of linear programming // Math. Programming. 1983. V. 27. P. 241-262.
Gilman R., Myasnikov A. G., Miasnikov A. D., and Ushakov A. Report on generic case complexity // Вестник Омского университета. Спец. вып.: Комбинаторные методы алгебры и сложность вычислений. 2007. С. 103-110.
Cook S. A. and Mitchell D. G. Finding hard instances of the satisfiability problem: A survey // Satisfiability problem: Theory and Applications. V. 35. Providence, RI: Amer. Math. Soc., 1997. P. 1-17.
Kellerer H., Pferschy U., and Pisinger D. Knapsack Problems. Berlin, New York: Springer Verlag, 2004. 546 p.
Ерофеев С.Ю. Диофантовость дискретного логарифма // Прикладная дискретная математика. Приложение. 2011. №4. С. 31-32.
Ерофеев С. Ю. Диофантовость дискретного логарифма // Вестник Омского университета. 2010. №4. С. 13-15.
Goldreich O. Foundations of cryptography. Cambridge: Cambridge Univ. Press., 2001. V1. 451 p.; 2004. V.2. 798 p.
Ерофеев С. Ю. Схемы построения двушагово односторонних функций // Вестник Омского университета. 2011. №4. С. 15-18.
Рыбалов А. Н. О генерической неразрешимости десятой проблемы Гильберта // Вестник Омского университета. 2011. №4. С. 19-22.
Тимошенко Е. И. Эндоморфизмы и универсальные теории разрешимых групп. Новосибирск: Изд-во НГТУ, 2011. 327 с.
Myasnikov A., Roman'kov V., Ushakov A., and VershikA. The word and geodesic problems in free solvable groups // Trans. Amer. Math. Soc. 2010. V.362. P. 4655-4682.
Vassileva S. Polynomial time conjugacy in wreath products and free solvable groups // Groups. Complexity. Cryptology. 2011. V. 3. P. 105-120.
Романовский Н. С. О некоторых алгоритмических проблемах для разрешимых групп // Алгебра и логика. 1974. Т. 13. №1. С. 26-34.
Тимошенко Е. И. Алгоритмические проблемы для метабелевых групп // Алгебра и логика. 1973. Т. 12. №2. С. 232-240.
Носков Г. А. О сопряженности в метабелевых группах // Математические заметки. 1982. Т. 31. №4. С. 495-507.
Вентура Э., Романьков В. А. Проблема скрученной сопряженности для эндоморфизмов метабелевых групп // Алгебра и логика. 2009. Т. 48. №2. С. 157-173.
Baumslag G., Cannonito F., and Robinson D. J. S. The algorithmic theory of finitely generated metabelian groups // Trans. Amer. Math. Soc. 1994. V. 344. P. 629-648.
Groves J. R. J. and Miller III C. F. Recognizing free metabelian groups // Illinois J. Math. 1986. V.30. No. 2. P. 246-254.
Baumslag G., Mikhailov R., and Orr K. E. A new look at finitely generated metabelian groups // arXiv math. Group Theory. 2012. No. 1203.5431. 17 p.
Hall P. Nilpotent groups // Canad. Math. Cong. Summer Sem. Vankuver: University of Alberta, 1957. P. 12-30.
Холл М. Теория групп. М.: ИЛ, 1962. 467 с.
Stroud P. Ph. D. Thesis. Cambridge, 1966. 121 p.
Segal D. Words: notes on verbal width in groups // London Math. Soc. Lect. Notes. V. 361. Cambridge: Cambridge Univ. Press, 2009. 215 p.
Алламбергенов Х. С., Романьков В. А. Произведения коммутаторов в группах // Докл. АН Уз. ССР. 1984. Т. 4. С. 14-15.
Jones J. Universal diophantine equation // J. Symbolic Logic. 1982. V. 47. No. 3. P. 549-571.
 Диофантова криптография на бесконечных группах | ПДМ. 2012. № 2(16).

Диофантова криптография на бесконечных группах | ПДМ. 2012. № 2(16).

Полнотекстовая версия