Dihedral Hidden Subgroup Problem Based On Quantum Computing Algorithms

The public key cryptography based on lattice hard problems is regarded as one of the four postquantum cryptography. It has been the center of the new public key cryptography because of itsanti-quantum nature and high efficience.Currently, calculated by the classical mathematical method ofreduction, the shortest vector problem analysis could not be assessed against quantum computingattacks, so it’s very necessary to seek a new method for quantum computation analysis and make theresearch into the security of shortest vector problem.Shor’s algorithm can be transformed into hidden subgroup problem which causes a tremendousupsurge of interest in quantum computing.Regev’s algorithm which transforms the shortest vectorproblem into dihedral hidden subgroup problem wides the application field of quantumcomputing.But dihedral hidden subgroup problem is hard on quantum computing.This paper mainly makes a study of the dihedral hidden subgroup problem based on Kuperbergand the quantum model of the shortest vector problem. In specific work, this paper points out thedisadvantage of the unitary transform which can be solved by the introduction of the period of thefunction based on hidden subgroup problem quantum algorithm, and make an analysis of theapproach.The improved algorithm keeps the good properties of the original Kuperbergalgorithm.According to the analysis of the evolvement approach of Regev’s shortest vector problem todihedral hidden subgroup problem, we put forward a quantum model of the unique shortest vectorproblem and make a comparison with the one based on classical mathematical method and Groverquantum research.This model acquires a preliminary balance on factor and timecomplexity.Meanwhile, on the basis of the existing quantum circuits, this article uses a bottom-upapproach to layer the detailed design of Kuperberg quantum algorithm and the SVP algorithm basedon Kuperberg, which can be used as the accordance of the integrated design for quantum computerchip.