マックエリス暗号
マックエリス暗号(McEliece_cryptosystem)は、暗号理論において,公開鍵暗号方式の一つであり,1978年にロバート・マックエリス(Robert McEliece)によって提案された。 この暗号方式は,最初の確率的な暗号方式であり,一つの平文から異なる暗号文が生成される.この暗号方式は暗号コミュニティにおいてあまり注目を浴びてこなかったが,ショアのアルゴリズムを用いた攻撃で破ることができないため,耐量子暗号の候補の一つとなっている.
この暗号方式は,線形符号の復号困難性(これはNP困難であることが知られている)に基づいている.復号に用いられる秘密鍵は,効率的に復号可能で t {\displaystyle t} 個のエラーを訂正可能な誤り訂正符号である.マックエリスによるオリジナルの方式は,二元ゴッパ符号(標数が2である有限体上の種数0の曲線で定義されるゴッパ符号)を用いている.この符号はPattersonによるアルゴリズムにより,効率的に復号できる. 暗号化に用いる公開鍵は,秘密鍵である符号を一般的な線形符号に「偽装」することで得られる.このために,符号の生成行列 G {\displaystyle G} を,二つのランダムに選ばれた可逆行列 S {\displaystyle S} と P {\displaystyle P} によって攪乱する.
攻撃者は C {\displaystyle C} の構造を復元し,それによって効率的な復号アルゴリズム A {\displaystyle A} か,あるいは他の十分効率的な復号アルゴリズムを見つけようとすることもできる.
このようなことが攻撃者にできるかどうかは, C {\displaystyle C} をどのような符号の族から選ぶかで決まる.マックエリス暗号で利用する符号族として多くの符号族が提案され,そのうちのほとんどのもの(例えばリード・ソロモン符号)に対しては,効率的な復号アルゴリズムが見つかっており,全く安全ではない.
最初に提案された二元ゴッパ符号は,構造的攻撃によって未だ破られていない数少ない符号族の一つである.