Searching linear structures of permutation groups with quantum computer

Linear structures of round functions of block ciphers is well-known weakness. Several attacks such as linear or differential cryptanalysis are based on existence of non-trivial linear structures. We also can formulate this problem over symmetric group \(S_n\) $S_n$ since that block cipher is permutation over plaintext/ciphertext alphabet. In this paper we examine complexity of searching linear structures of permutations by applying quantum algorithm, similar to famous Shor’s algorithm. More specifically, we study close relations between searching of linear structures of permutation groups and hidden subgroup problem in symmetric group \(S_n\) $S_n$ .