What is the post-quantum security of encryptions schemes based on transpositions?

alpominth

4/19/24, 5:19 AM

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?

247

1 + 0

post-quantum-cryptography

transposition-cipher

grovers-algorithm

Score:4

Crypto

forest

4/19/24, 5:49 AM

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.

+ 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: What is the post-quantum security of encryptions schemes based on transpositions?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.