2
$\begingroup$

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?

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

2 Answers 2

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
8
  • $\begingroup$ 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. $\endgroup$
    – Riva11
    Commented Aug 22, 2020 at 2:09
  • $\begingroup$ @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). $\endgroup$
    – Mark Schultz-Wu ♦
    Commented Aug 22, 2020 at 2:36
  • $\begingroup$ 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. $\endgroup$
    – Mark Schultz-Wu ♦
    Commented Aug 22, 2020 at 2:37
  • $\begingroup$ 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 $\endgroup$
    – Riva11
    Commented Aug 27, 2020 at 0:40
  • $\begingroup$ 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. $\endgroup$
    – Mark Schultz-Wu ♦
    Commented Aug 27, 2020 at 0:43
3
$\begingroup$

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?

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ 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$). $\endgroup$
    – fgrieu ♦
    Commented Aug 19, 2020 at 7:30
  • $\begingroup$ @fgrieu, of course, I was trying to understand why this strange setup. $\endgroup$
    – kodlu
    Commented Aug 19, 2020 at 9:22
  • $\begingroup$ 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. $\endgroup$
    – Riva11
    Commented Aug 19, 2020 at 13:36
  • 2
    $\begingroup$ 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. $\endgroup$
    – kodlu
    Commented Aug 19, 2020 at 23:25
  • $\begingroup$ ok @kodlu i edited the question $\endgroup$
    – Riva11
    Commented Aug 20, 2020 at 13:56

Your Answer

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