Constructing of one-way functions based on undecidability of the endomorphism problem in groups.pdf Односторонние функции - неотъемлемая часть криптографических схем и про-токолов. Теоретически их существование до сих пор не установлено. В работахЛ. А. Левина [1, 2] представлена универсальная функция, являющаяся односторонней,если существует хотя бы одна односторонняя функция.Предлагается схема построения односторонней функции в группе с разрешимойпроблемой равенства и неразрешимой проблемой эндоморфной сводимости, а такжепротокол аутентификации на ее основе.Говорят, что в эффективно заданной группе G разрешима проблема эндоморф-ной сводимости, если существует алгоритм, определяющий по любой паре элементовg, f G G, является ли f эндоморфным образом элемента g.Существование группы G с разрешимой проблемой равенства и неразрешимой про-блемой эндоморфной сводимости установлено в работах В. А. Романькова [3, 4]. Аименно доказано, что указанным свойством обладают свободные метабелевы груп-пы Mn достаточно большого ранга n и свободные нильпотентные группы Nrc доста-точно большого ранга r и ступени нильпотентности c ^ 9.В общих чертах схема выглядит следующим образом. В группе G выбираетсяэлемент g, эндоморфные значения которого в фиксированной циклической подгруп-пе (f) кодируются наборами целых чисел a G ZM. Это позволяет определить функцию^ : ZM ^ Z. Свойства группы G позволяют рассматривать ^ как одностороннюю. Дляаутентификации фиксируется открытое значение g G Mn и публикуется значение ^(g)для секретного ^ G End G, ^ О a G ZM. Сессионная аутентификация заключаетсяв выборе ф G End G и публикации h = ^(^(g)). При ответе «0» объявляется ф и прове-ряется равенство для ^(g). При ответе «1» объявляется ^ оф и проверяется равенстводля g.Однако в указанной схеме, предложенной в работе Д. Григорьева и В. Шпиль-райна [5] и основанной на идее В. A. Романькова, имеется существенная слабость.Для ее надежности требуется неразрешимость проблемы эндоморфизма для образов,в частности для

Скачать электронную версию публикации