COMPLEXITY OF HIDDEN ABELIAN GROUP ACTION PROBLEM IN QUANTUM COMPUTING MODEL.

The paper first examines the Hidden Abelian Group Action problem's complexity in quantum computing model. This algebraic problem is fundamental in determining the hardness of a one-way function constructed on the basis of commutative and locally commutative maps and ciphers. In fact, finding new one-way functions that will be resistant in quantum computing model is very important for modern cryptography. The main objective of the study is to assess the complexity of the Hidden Abelian Group Action problem by using a reduction to already known problems, such as the Hidden Subgroup problem and the Hidden Shift problem. In this paper, reduction of the Hidden Abelian Group Action problem to the Hidden Shift problem was first shown, and limitations that distinguish them were first demonstrated. As a result, on the one hand, the existing partial solutions to the Hidden Shift problem, and general Kuperberg's subexponential algorithm can be extended to the case of the Hidden Abelian Group Action problem. Moreover, more limitations give more chances to effective general solution to this problem. On the other hand, the reduction and similarity to a known challenge in quantum computing model also indicate the complexity of the Hidden Abelian Group Action problem, which leaves a chance for making a real stand one-way function in quantum computing model based on a locally commutative mapping. [ABSTRACT FROM AUTHOR]