マックエリス暗号
攻撃者は公開鍵 ( G ^ , t ) {\displaystyle ({\hat {G}},t)} を知っているが秘密鍵は知らず,手に入れた暗号文 c ∈ F 2 n {\displaystyle c\in \mathbb {F} _{2}^{n}} から平文を復元したい.このような試みは(事実上)不可能であるべきである.
マックエリス暗号に対する攻撃手法は,大きく2系統に分かれる.
攻撃者は,公開されている行列 G ^ {\displaystyle {\hat {G}}} が ( n , k ) {\displaystyle (n,k)} 符号 C ^ {\displaystyle {\hat {C}}} の生成行列であり,その符号は t {\displaystyle t} 個のエラーを訂正できる,という事実を知っている.
符号 C ^ {\displaystyle {\hat {C}}} は,特定の符号の族から選ばれた何らかの構造を持った符号を難読化したものであるが,攻撃者はそのような事実を無視して,任意の線形符号に対する復号の方法を使うことができる.そのようなアルゴリズムとしては,符号の各符号語をチェックする方法,シンドローム復号法,information set decodingなどがある.しかし,一般の線形符号の復号はNP困難であることが知られており,上述の方法はすべて指数的な実行時間を必要とする.
2008年に,BernsteinとLangeとPetersは,オリジナルのマックエリス暗号に対する実用的な攻撃を与えたが,それはSternによる Information Set Decodingを用いたものである. 最初にマックエリスが提案したパラメータを使った場合,攻撃は 2 回のビット演算で実行できる.その攻撃は完全に並列化できるため(ノード間の通信は必要ない),そこそこのコンピュータクラスターを使えば数日で攻撃が完了する.