# Is this permutation secure?

Let vector $${\bf d} \in \{ \pm 1 \}^n$$ be the message we want to send. In my system, $${\bf d}$$ is multiplied by an $$n \times n$$ Fourier matrix $${\bf F}$$, as follows

$${\bf x} = {\bf F} {\bf d}$$

where

$${\bf F} = \begin{pmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & e^{jw} & e^{j2w}&\cdots & e^{j(n-1)w} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & e^{j(n-1)w} &e^{j2(n-1)w}& \cdots & e^{j(n-1)(n-1)w} \end{pmatrix}$$ We perform secret permutation $$P$$ for $${\bf x}$$ provided that only the legitimate parties know the permutation and $$P$$ changes for every transmission.

1. Does multiplying by $${\bf F}$$ help to diffuse?

2. Is this actually breakable?

3. If so, what kind of cryptanalysis can be used?

• What does "We perform secret permutation $P$" mean? Do we multiply by a permutation matrix? Aug 20 '20 at 14:45
• It is only interleaving of $X$, assume adversary does not know $P$ Aug 20 '20 at 15:04
• So, mathematically speaking, the interleaving is done via $\bf P x$, where $\bf P$ is a permutation matrix, right? Aug 20 '20 at 15:04
• P is randomly generated interleaving $N$ indices from some seed. If the transmitted cipher is $C$, $C(i) =X(P(i)), i=[1,.., N]$ Aug 20 '20 at 15:45

Multiplying by $$F$$ cannot help. It is publicly known, and easily invertible. Therefore an adversary can easily undo it, leaving them with simply the permuted inputs $$\mathbf{Px}$$.

Moreover, permuting the input cannot be IND-CPA secure. This is because permutation matrices leave norms invariant, meaning:

$$\lVert \mathbf{Px}\rVert_p = \lVert \mathbf{x}\rVert_p$$ For any $$p$$-norm (including the "$$\ell_0$$-norm", meaning the Hamming weight). This means that frequency analysis can be used to attack enciphering via solely permuting the input. In general these ciphers are known as transposition ciphers.

• Thanks @Mark, i appreciate if you are aware of a good paper or reference how frequency analysis is used to reveal the random permutation as you mentioned. Aug 22 '20 at 2:09
• @Riva11 This answer contains some information. The basic idea is that if you know the plaintext is formatted a certain way (say "Is correctly spelled english text"), you can use this to mount an attack. The character which occurs most often in the ciphertext is very likely to be one of the most common occurring characters in english text. You can repeat this with "pairs of consecutive characters" or "triplets of consecutive characters" (known as bigrams and trigrams).
– Mark
Aug 22 '20 at 2:36
• There's of course still work to be done after having that technical insight, but the work is rather "elementary" --- a professor I had in undergrad would assign it (with suitable "guidance" in how to break it down into individual parts) as a programming project in an intro to python course.
– Mark
Aug 22 '20 at 2:37
• it does seem some works has been done in context of random and pseudorandom permutation that can be secure so it might be not simply as that Aug 27 '20 at 0:40
• Regardless of how you generate your permutations, $\mathbf{Px}$ will leak the number of 0's which occur in $\mathbf{x}$. This means that it cannot hope to be IND-CPA. Using the standard left/right notion of indistinguishability, submit $\mathbf{x}_0 = 0^n$ and $\mathbf{x}_1 = 1^n$. Then an adversary can easily determine $0/1$ from $\mathbf{Px}_b$ by simply counting the number of 0's in the ciphertext.
– Mark
Aug 27 '20 at 0:43

This is problematic as stated. You need to specify a probability distribution for that complex matrix, but the complex field is infinite. This then implies that you need to also carefully define some detection/quantization mechanism.

So, why complex numbers?

• Addition: it is at least possible to make the system secure. Make F all-zero, except in the diagonal, making that random in $\{-1,1\}$. Then the system become equivalent to a One Time Pad, provided that "$P$ changes for every transmission" (understood as: for each message $d$).
– fgrieu
Aug 19 '20 at 7:30
• @fgrieu, of course, I was trying to understand why this strange setup. Aug 19 '20 at 9:22
• Thanks, the main secrecy method is the permutation. However, i was wondering is the matrix induces vulnerablity or diffusion. It is part of the insecure system. It's values are fixed for a given size and the complex elements can be considered as constants values. So the matrix elements does not change. For clarification, it's IFFT of the information, en.m.wikipedia.org/wiki/DFT_matrix. I wanted to know if the linear relationship can reveal some plaintext deduced from the permutation. Aug 19 '20 at 13:36
• please rewrite the question mathematically, on the basis of the comments above. "it's IFFT of the information" doesn't parse for me. The question should be self-contained. Aug 19 '20 at 23:25
• ok @kodlu i edited the question Aug 20 '20 at 13:56