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

Аннотация

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