Fesenko A. Complexity analysis of the locally commutative mapping inverting problem in classical and quantum models of computation.

The thesis is devoted to the construction of general algebraic model to combine problems which are considered by cryptanalysis of cryptographic systems and protocols with algebraic models, and algebraic problems which are investigated in quantum model of computation. The concept of strongly and weakly locally commutative mappings was introduced and shown that the existence of a one-way function with such properties is a necessary condition to construct many cryptographic protocols which would be secure in complexity-theoretic model. A class of heterogeneous algebraic systems was proposed as a generalization of the commutative symmetric cipher's algebraic model and their properties were analyzed, proving the existence of a reduction the locally commutative mapping inverting problem to algebraic problems such as the hidden action on torsor over abelian group problem. Proved a reduction of proposed problems to the hidden shift problem which allows to construct criteria of effective solution's existence for the locally commutative mapping inverting problem in quantum model of computation.