Computational methods in discrete mathematics

Searching hidden linear structures with quantum computer

M. V. Polyakov, M. A. Pudovkina


Abstract: We present a quantum algorithm for finding hidden linear structures of cryptographic mappings. The presented algorithm is based on solving the Abelian case of the hidden subgroup problem. We show that for a hidden subgroup of the additive group $(V_n, +)$ it is possible to find the subgroup generator with the polynomial number of queries to the quantum oracle.

Keywords: linear structures of mappings, quantum algorithms, hidden subgroup problem, quantum cryptanalysis, Simon's problem.

UDC: 519.7

DOI: 10.17223/2226308X/18/60