マックエリス暗号
暗号文 c {\displaystyle c} を受け取った時,アリスは次のようにして復号して元のメッセージを得る.
アリスは P {\displaystyle P} の逆行列 P − 1 {\displaystyle P^{-1}} を計算する.
アリスは c ^ = c P − 1 {\displaystyle {\hat {c}}=cP^{-1}} を計算する.
アリスは復号アルゴリズム A {\displaystyle A} を使って c ^ {\displaystyle {\hat {c}}} を復号し,復号結果 m ^ {\displaystyle {\hat {m}}} を得る.
アリスは m = m ^ S − 1 {\displaystyle m={\hat {m}}S^{-1}} を計算する. m {\displaystyle m} が元のメッセージである.
(具体的な方法については下を参照のこと.)
この暗号化方式には,別の符号を用いた複数のバリエーションが存在するが,多くは安全性が低く,構造的攻撃によって破ることができる.
ゴッパ符号を用いたマックエリス暗号は現在のところ解読されていない.最も効率の良い攻撃方法として知られているのは information-set decodingアルゴリズムを用いるものである.2008年の論文には,攻撃手法と修正方法が示されている. 別の論文では,量子コンピュータに対して安全にするためには,鍵サイズを4倍に延ばす必要があることが示されている.これは, 量子コンピュータによって information set decoding が効率化できるからである.
マックエリス暗号の利点 --- 例えばRSA暗号などと比較して --- として,暗号化と復号が速いことが挙げられる. 長い間,マックエリス暗号で デジタル署名 は生成できないだろうと考えられてきた.しかし,マックエリス暗号の双対版であるNiederreiter暗号を用いると署名方式を構築することができる.マックエリス暗号の一番大きな欠点は,公開鍵と秘密鍵が大きな行列であることである.標準的なパラメータにおいては,公開鍵は512KB(キロバイト)である.