マックエリス暗号

マックエリス暗号（McEliece_cryptosystem）は、暗号理論において，公開鍵暗号方式の一つであり，1978年にロバート・マックエリス（Robert McEliece）によって提案された。 この暗号方式は，最初の確率的な暗号方式であり，一つの平文から異なる暗号文が生成される．この暗号方式は暗号コミュニティにおいてあまり注目を浴びてこなかったが，ショアのアルゴリズムを用いた攻撃で破ることができないため，耐量子暗号の候補の一つとなっている．
この暗号方式は，線形符号の復号困難性（これはNP困難であることが知られている）に基づいている．復号に用いられる秘密鍵は，効率的に復号可能でformula_1 個のエラーを訂正可能な誤り訂正符号である．マックエリスによるオリジナルの方式は，二元ゴッパ符号（標数が２である有限体上の種数0の曲線で定義されるゴッパ符号）を用いている．この符号はPattersonによるアルゴリズムにより，効率的に復号できる． 暗号化に用いる公開鍵は，秘密鍵である符号を一般的な線形符号に「偽装」することで得られる．このために，符号の生成行列 formula_2 を，二つのランダムに選ばれた可逆行列 formula_3 と formula_4 によって攪乱する．（具体的な方法については下を参照のこと．）
この暗号化方式には，別の符号を用いた複数のバリエーションが存在するが，多くは安全性が低く，構造的攻撃によって破ることができる．
ゴッパ符号を用いたマックエリス暗号は現在のところ解読されていない．最も効率の良い攻撃方法として知られているのは information-set decodingアルゴリズムを用いるものである．2008年の論文には，攻撃手法と修正方法が示されている． 別の論文では，量子コンピュータに対して安全にするためには，鍵サイズを４倍に延ばす必要があることが示されている．これは， 量子コンピュータによって information set decoding が効率化できるからである.
マックエリス暗号の利点 --- 例えばRSA暗号などと比較して --- として，暗号化と復号が速いことが挙げられる． 長い間，マックエリス暗号で デジタル署名 は生成できないだろうと考えられてきた．しかし，マックエリス暗号の双対版であるNiederreiter暗号を用いると署名方式を構築することができる．マックエリス暗号の一番大きな欠点は，公開鍵と秘密鍵が大きな行列であることである．標準的なパラメータにおいては，公開鍵は512KB（キロバイト）である．
暗号化方式.
マックエリス暗号は，鍵を生成する確率的アルゴリズム，暗号化をする確率的アルゴリズム，復号アルゴリズムの，３つのアルゴリズムから成る．マックエリス暗号を用いる全てのユーザは，共通のセキュリティパラメータ formula_5 を用いる．
鍵生成.
暗号の原理は，鍵生成者アリスが，効率的な復号アルゴリズムが分かっている符号 formula_6 を（何らかの線形符号の族から）選び，符号 formula_6 を公開するが復号アルゴリズムは秘密に保つ，というものである．符号formula_6の復号には，符号formula_6の生成行列の知識だけではなく，符号の族からformula_6を選び出したときに用いたパラメータを必要とする．例えば，二元ゴッパ符号においては，復号にはゴッパ多項式とcode locatorsが必要である．したがって，アリスは適切に難読化された formula_6の生成行列を公開することができる．
より具体的には，鍵は以下のように生成される．
暗号化.
ボブがメッセージ formula_29 をアリスに送りたいとしよう．アリスの公開鍵＝暗号化のための鍵が formula_25 であるならば，ボブは以下のように formula_29 を暗号化する．
復号.
暗号文 formula_42 を受け取った時，アリスは次のようにして復号して元のメッセージを得る．
復号の正当性の証明.
暗号化と復号の手順より，formula_51 が成り立ち，formula_4 が置換行列であるためformula_53 は重み formula_1 のベクトルである．
ゴッパ符号 formula_2 は最大 formula_1 個のエラーを訂正することができ，ベクトル formula_57 と formula_58 との距離は高々 formula_1 である．したがって，復号アルゴリズムによって正しい符号語 formula_60 が得られる．
formula_3 の逆行列をかけることで，formula_62 が得られ，これはボブが送ったメッセージに等しい．
鍵のサイズ.
初めの論文でマックエリスはパラメータとして formula_63 を提案していた． その場合，公開鍵のサイズは 524*(1024-524) = 262,000 ビットである． 最近の解析により，80ビット安全を達成するためのパラメータとしては，標準的な代数的復号を使う場合は formula_64，ゴッパ符号に対するリスト復号を用いる場合はformula_65 とすることが提案されており，公開鍵長はそれぞれ 520,047ビット，460,647ビットとなる． 量子コンピュータでの解読に耐性を持たせるためには，ゴッパ符号を用いる場合は formula_66 とすることが提案されており，公開鍵長は 8,373,911ビットになる．
攻撃手法.
攻撃者は公開鍵 formula_67 を知っているが秘密鍵は知らず，手に入れた暗号文 formula_68 から平文を復元したい．このような試みは（事実上）不可能であるべきである．
マックエリス暗号に対する攻撃手法は，大きく２系統に分かれる．
総当たり攻撃 / 非構造的な攻撃.
攻撃者は，公開されている行列 formula_69 が formula_70 符号 formula_71 の生成行列であり，その符号は formula_1 個のエラーを訂正できる，という事実を知っている．
符号formula_71 は，特定の符号の族から選ばれた何らかの構造を持った符号を難読化したものであるが，攻撃者はそのような事実を無視して，任意の線形符号に対する復号の方法を使うことができる．そのようなアルゴリズムとしては，符号の各符号語をチェックする方法，シンドローム復号法，information set decodingなどがある．しかし，一般の線形符号の復号はNP困難であることが知られており，上述の方法はすべて指数的な実行時間を必要とする．
2008年に，BernsteinとLangeとPetersは，オリジナルのマックエリス暗号に対する実用的な攻撃を与えたが，それはSternによる Information Set Decodingを用いたものである． 最初にマックエリスが提案したパラメータを使った場合，攻撃は 260.55 回のビット演算で実行できる．その攻撃は完全に並列化できるため（ノード間の通信は必要ない），そこそこのコンピュータクラスターを使えば数日で攻撃が完了する．
構造的攻撃.
攻撃者は formula_6 の構造を復元し，それによって効率的な復号アルゴリズム formula_15 か，あるいは他の十分効率的な復号アルゴリズムを見つけようとすることもできる．
このようなことが攻撃者にできるかどうかは，formula_6をどのような符号の族から選ぶかで決まる．マックエリス暗号で利用する符号族として多くの符号族が提案され，そのうちのほとんどのもの（例えばリード・ソロモン符号）に対しては，効率的な復号アルゴリズムが見つかっており，全く安全ではない．
最初に提案された二元ゴッパ符号は，構造的攻撃によって未だ破られていない数少ない符号族の一つである．