Новые формы задания скрытой задачи дискретного логарифмирования

Аннотация

Предлагаются новые варианты задания задачи дискретного логарифмирования в скрытой группе, которая представляет интерес для построения постквантовых криптографических протоколов и алгоритмов. Данная задача формулируется над конечными ассоциативными алгебрами с некоммутативной операцией умножения. В известном варианте данная задача формулируется как суперпозиция операций возведения в степень и автоморфного отображения алгебры, представляющей собой конечное некоммутативное кольцо с глобальной двухсторонней единицей, и называется конгруэнц логарифмированием. Ранее было показано, что последняя задача, заданная в конечной алгебре кватернионов, сводится к задаче дискретного логарифмирования в конечном поле, которое является расширением простого поля, над которым задана конечная алгебра кватернионов, и дальнейшие исследования задачи конгруэнц логарифмирования как примитива постквантовых криптосхем следует проводить в направлении поиска новых ее носителей, для которых такое сведение окажется вычислительно нереализуемым. В данной статье представлен ряд новых конечных ассоциативных алгебр, обладающих существенно различающимися свойствами в сравнении с алгеброй кватернионов, в частности в них отсутствует глобальная двухсторонняя единица. Это отличие потребовало новой формулировки задачи дискретного логарифмирования в скрытой группе, отличной от варианта конгруэнц логарифмирования. Предложено несколько вариантов такой формулировки, в которых используются локальные единицы различных типов. Рассматриваются левые, правые и двухсторонние локальные единицы, в качестве которых выступают обратимые и необратимые элементы алебры. Предложены два общих способа построения конечных ассоциативных алгебр с некоммутативным умножением. Первый способ относится к заданию алгебр, имеющих произвольное натуральное значение размерности m > 1, второй  к заданию алгебр произвольных четных размерностей. Впервые разработаны алгоритмы цифровой подписи, основанные на вычислительной трудности задачи дискретного логарифмирования в скрытой группе.

Abstract

There are introduced novel variants of defining the discrete logarithm problem in a hidden group, which represents interest for constructing post-quantum cryptographic protocols and algorithms. This problem is formulated over finite associative algebras with non-commutative multiplication operation. In the known variant this problem, called congruent logarithm, is formulated as superposition of exponentiation operation and automorphic mapping of the algebra that is a finite non-commutative ring. Earlier it has been shown that congruent logarithm problem defined in the finite quaternion algebra can be reduced to discrete logarithm in the finite field that is an extension of the field over which the quaternion algebra is defined. Therefore further investigations of the congruent logarithm problem as primitive of the post-quantum cryptoschemes should be carried out in direction of finding new its carriers. The present paper introduces novel associative algebras possessing significantly different properties than quaternion algebra, in particular they contain no global unit. This difference had demanded a new definition of the discrete logarithm problem in a hidden group, which is different from the congruent logarithm. There are proposed several variants of such definition, in which it is used the notion of the local unite. There are considered right, left, and bi-side local unites. Two general methods for constructing the finite associative algebras with non-commutative multiplication operation are proposed. The first method relates to defining the algebras having dimension value equal to a natural number m > 1, and the second one relates to defining the algebras having arbitrary even dimensions. For the first time the digital signature algorithms based on computational difficulty of the discrete logarithm problem in a hidden group have been proposed.