Finite Non-Commutative Associative Algebras as Carriers of Hidden Discrete Logarithm Problem

Аннотация

Статья рассматривает новые конечные алгебры, представляющие интерес в качестве носителей задачи дискретного логарифмирования в скрытой группе. В частности, предложены новые 4-мерные и 6-мерные конечные некоммутативные алгебры с ассоциативной операцией умножения и описаны их свойства. Также предложен общий метод
задания конечных некоммутативных ассоциативных алгебр произвольной четной размерности mge 2. Некоторые из рассмотренных алгебр содержат глобальную двухстороннюю единицу, а другие не содержат такой единицы. В последнем случае элементы алгебры обратимы локально относительно некоторой локальной двухсторонней единицы, действующей в рамках некоторого подмножества элементов алгебры. Для алгебр последнего типа выведены формулы, описывающие множества правосторонних, левосторонних и двухсторонних локальных единиц. Также представлены алгебры, содержащие большое множество глобальных левосторонних (правосторонних) единиц при отсутствии в них глобальной двухсторонней единицы. Поскольку известные формы задания крытой задачи дискретного логарифмирования используют обратимость элементов алгебры относительно глобальной двухсторонней единицы, были предложены новые формы задания этой вычислительно трудной задачи. Результаты статьи могут быть использованы для разработки криптографических алгоритмов и протоколов с открытым ключом, включая постквантовые криптосхемы. Впервые предложена схема цифровой подписи, основанная на скрытой задаче дискретного логарифмирования.