MDSマトリックス

MDS 行列(最大距離分離可能) は、暗号化に有用な特定の拡散特性を持つ関数を表す行列です。技術的には、有限体上の行列が からへの線形変換の変換行列であり、の異なる 2 つの組が 以上の要素で一致しない場合、その行列は MDS 行列となります。同様に、すべての組の集合はMDS コード、つまりシングルトン境界に到達する線形コードです。 ${\displaystyle m\times n}$${\displaystyle A}$ ${\displaystyle K}$ ${\displaystyle f(x)=Ax}$${\displaystyle K^{n}}$${\displaystyle K^{m}}$${\displaystyle (m+n)}$${\displaystyle (x,f(x))}$${\displaystyle n}$${\displaystyle (m+n)}$${\displaystyle (x,f(x))}$

を単位行列と結合して得られる行列とします。このとき、行列がMDS であるための必要十分条件は、から行を削除して得られるすべての部分行列が非特異であることです。これは、次のことにも相当します。行列のすべての部分行列式はゼロ以外です。このとき、バイナリ行列(つまり、2 つの要素を持つ体上の行列) は、すべての要素 を持つ 1 つの行または 1 つの列のみを持たない限り、MDS にはなりません。 ${\displaystyle {\チルダ {A}}={\begin{pmatrix}\mathrm {I} _{n}\\\hline \mathrm {A} \end{pmatrix}}}$ ${\displaystyle \mathrm {I} _{n}}$${\displaystyle A}$${\displaystyle A}$${\displaystyle n\times n}$ ${\displaystyle m}$${\displaystyle {\tilde {A}}}$${\displaystyle A}$${\displaystyle A}$${\displaystyle 1}$

リード・ソロモン符号はMDS プロパティを持ち、暗号化アルゴリズムで使用される MDS 行列を取得するために頻繁に使用されます。

セルジュ・ヴォードネーは、暗号プリミティブでMDS行列を使用して、彼がマルチパーミュテーションと呼ぶもの、同じ特性を持つ必ずしも線形ではない関数を生成することを提案しました。 ^{[1]これらの関数は、彼が}完全拡散と呼ぶもの、つまり入力を変更すると少なくとも出力が変化するものを持っています。彼は、不完全拡散を利用してマルチパーミュテーションではない関数を暗号解読する方法を示しました。 ${\displaystyle t}$${\displaystyle m-t+1}$

MDS 行列は、 AES、SHARK、Square、Twofish、Anubis、KHAZAD、 Manta 、Hierocrypt、Kalyna、Camellia、 HADESMiMCなどのブロック暗号、およびストリーム暗号MUGIと暗号ハッシュ関数Whirlpool 、 Poseidon での拡散に使用されます。

• ヴィンセント・ライメン;ジョアン・デーメン;バート・プレニール;アントゥーン・ボセラーズ。エリック・デ・ウィン（1996年2月）。暗号 SHARK (PDF/PostScript)。高速ソフトウェア暗号化に関する第 3 回国際ワークショップ (FSE '96)。ケンブリッジ: スプリンガー・フェルラーク。 99–111ページ。2007 年 3 月 6 日に取得。
• Bruce Schneier、John Kelsey、Doug Whiting、David Wagner、Chris Hall、Niels Ferguson (1998 年 6 月 15 日)。「Twofish 暗号化アルゴリズム」(PDF/PostScript) 。2007 年 3 月 4 日に取得。