この順列は安全ですか？

Question

ベクトルをしましょう ${\bf d} \in \{ \pm 1 \}^n$送信したいメッセージになります。私のシステムでは、${\bf d}$ を掛ける $n \times n$ フーリエ行列 ${\bf F}$、 次のように

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

どこ

$$ {\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}$$ 秘密の順列を実行します $P$ ために ${\bf x}$ ただし、合法的な当事者のみが順列を知っており、 $P$ 送信ごとに変更されます。

1. 乗算しますか ${\bf F}$ 拡散するのに役立ちますか？

2. これは実際に壊れやすいですか？

3. もしそうなら、どのような暗号解読を使用できますか？

Answer 1

掛ける $F$助けることはできません。それは公に知られており、簡単に反転できます。したがって、敵は簡単に元に戻すことができ、単に並べ替えられた入力を残すことができます$\mathbf{Px}$。

さらに、入力の並べ替えはIND-CPAで保護できません。これは、置換行列がノルムを不変のままにするためです。つまり、次のようになります。

$$\lVert \mathbf{Px}\rVert_p = \lVert \mathbf{x}\rVert_p$$ どんな場合でも $p$-ノルム（「$\ell_0$-norm」、つまりハミング重み）。これは、周波数分析を使用して、入力を並べ替えるだけで暗号化を攻撃できることを意味します。一般に、これらの暗号は転置式暗号として知られています。

Answer 2

述べたように、これは問題があります。その複素行列の確率分布を指定する必要がありますが、複素体は無限大です。これは、検出/量子化メカニズムも注意深く定義する必要があることを意味します。

では、なぜ複素数なのか？