マックエリス暗号とは？わかりやすく解説

マックエリス暗号（McEliece_cryptosystem）は、暗号理論において，公開鍵暗号方式の一つであり，1978年にロバート・マックエリス（Robert McEliece）によって提案された^[1]。この暗号方式は，最初の確率的な暗号方式であり，一つの平文から異なる暗号文が生成される．この暗号方式は暗号コミュニティにおいてあまり注目を浴びてこなかったが，ショアのアルゴリズムを用いた攻撃で破ることができないため，耐量子暗号の候補の一つとなっている^[2]．

この暗号方式は，線形符号の復号困難性（これはNP困難であることが知られている）に基づいている^[3]．復号に用いられる秘密鍵は，効率的に復号可能で $t$