Уязвимость в квантовой модели вычислений криптопримитивов, основанных на задаче поиска сопрягающего элемента и степени

Abstract

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

Розроблено ефективний алгоритм розв'язання в квантовій моделі обчислень узагальненої задач і дискретного логарифмування за допомогою зведення до абелевої задачі про приховану підгрупу. Запропонований метод дозволяє в квантовій моделі обчислень ефективно розв'язати часткову задачу пошуку елемента спряження та степеня, на складності розв'язання якої в деяких групах ґрунтується стійкість декількох криптографічних систем та протоколів

The paper shows the existence of an efficient algorithm to solve the generalized discrete logarithm problem in quantum computing model by reducing it to the Abelian hidden subgroup problem. The proposed method can also efficiently solve the power conjugacy search subproblem in quantum computing model, on whose complexity in some groups the resistance of several cryptographic systems and protocols is based.