I know that if using Grover's algorithm to break a cipher, one would need to perform (2^[key space])^0.5 queries (the square root of the number of all possible keys).

A simple transposition cipher COULD have their security of (transpositions)! (factorial of the number of transpositions), but how would it be in a post-quantum scenario?

Will the classical security of encryption schemes based on transpositions be reduced by Grover's algorithm?


1 Answer 1


Grover's algorithm is an unstructured search algorithm that finds the input to a black box that results in a particular value. It doesn't matter how that black box is constructed, or what operations it uses.

Grover's algorithm works in $O(\sqrt N)$ where $N$ is the size of the black box's domain. No change to the construction of the black box will change this fact. This is proven to be asymptotically optimal, but that only means that there exist no other general-purpose database search algorithms that are more efficient (by more than a constant factor). That doesn't mean that there won't exist an algorithm, even a classical algorithm, that is more efficient for the particular cipher you are using.

If you mean an actual transposition cipher, and not just a cipher that happens to have transpositions as one of its operations, then it will be horribly insecure, and there won't be any need to resort to any algorithm as difficult to implement as Grover's. Mere frequency analysis is sufficient to break them.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.