マックエリス暗号

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

この暗号方式は，線形符号の復号困難性（これはNP困難であることが知られている）に基づいている^[3]．復号に用いられる秘密鍵は，効率的に復号可能で $t$ 個のエラーを訂正可能な誤り訂正符号である．マックエリスによるオリジナルの方式は，二元ゴッパ符号（標数が２である有限体上の種数0の曲線で定義されるゴッパ符号）を用いている．この符号はPattersonによるアルゴリズムにより，効率的に復号できる．^[4] 暗号化に用いる公開鍵は，秘密鍵である符号を一般的な線形符号に「偽装」することで得られる．このために，符号の生成行列 $G$ を，二つのランダムに選ばれた可逆行列 $S$ と $P$ によって攪乱する．（具体的な方法については下を参照のこと．）

この暗号化方式には，別の符号を用いた複数のバリエーションが存在するが，多くは安全性が低く，構造的攻撃によって破ることができる．

ゴッパ符号を用いたマックエリス暗号は現在のところ解読されていない．最も効率の良い攻撃方法として知られているのは information-set decodingアルゴリズムを用いるものである．2008年の論文には，攻撃手法と修正方法が示されている．^[5] 別の論文では，量子コンピュータに対して安全にするためには，鍵サイズを４倍に延ばす必要があることが示されている．これは，量子コンピュータによって information set decoding が効率化できるからである.^[6]

マックエリス暗号の利点 --- 例えばRSA暗号などと比較して --- として，暗号化と復号が速いことが挙げられる．^[7] 長い間，マックエリス暗号でデジタル署名は生成できないだろうと考えられてきた．しかし，マックエリス暗号の双対版であるNiederreiter暗号を用いると署名方式を構築することができる．マックエリス暗号の一番大きな欠点は，公開鍵と秘密鍵が大きな行列であることである．標準的なパラメータにおいては，公開鍵は512KB（キロバイト）である．

暗号化方式

マックエリス暗号は，鍵を生成する確率的アルゴリズム，暗号化をする確率的アルゴリズム，復号アルゴリズムの，３つのアルゴリズムから成る．マックエリス暗号を用いる全てのユーザは，共通のセキュリティパラメータ $n,k,t$ を用いる．

鍵生成

暗号の原理は，鍵生成者アリスが，効率的な復号アルゴリズムが分かっている符号 $C$ を（何らかの線形符号の族から）選び，符号 $C$ を公開するが復号アルゴリズムは秘密に保つ，というものである．符号 $C$ の復号には，符号 $C$ の生成行列の知識だけではなく，符号の族から $C$ を選び出したときに用いたパラメータを必要とする．例えば，二元ゴッパ符号においては，復号にはゴッパ多項式とcode locatorsが必要である．したがって，アリスは適切に難読化された $C$ の生成行列を公開することができる．

より具体的には，鍵は以下のように生成される．

アリスは，何らかの符号の族（例えば，二元ゴッパ符号．この族には多数の符号が含まれている必要がある．）から， $t$ ビット誤りを効率的に訂正可能な二元 $(n,k)$ -符号 $C$ を選ぶ．効率的な復号アルゴリズムを $A$ とする．また，符号 $C$ の生成行列（の一つ）を $G$ とする．線形符号は多くの生成行列を持つが，大抵の場合，自然な生成行列の選択が存在する．そのような生成行列は $A$ を明らかにしてしまう場合があるため，秘密にしておかなければならない．
アリスは， $k\times k$ の正則行列 $S$ をランダムに選ぶ．
アリスは $n\times n$ の置換行列 $P$ をランダムに選ぶ．
アリスは $k\times n$ 行列 ${\hat {G}}=SGP$ を計算する．
アリスの公開鍵は $({\hat {G}},t)$ であり，秘密鍵は $(S,P,A)$ である．なお，復号アルゴリズム $A$ は符号 $C$ の選択に使ったパラメータによって定まるため，このパラメータのみを記憶すれば良い．

暗号化

ボブがメッセージ $m$ をアリスに送りたいとしよう．アリスの公開鍵＝暗号化のための鍵が $({\hat {G}},t)$ であるならば，ボブは以下のように $m$ を暗号化する．

ボブはメッセージ $m$ を長さ $k$ のビット列として表現する．
ボブは，ベクトル $c^{\prime }=m{\hat {G}}$ を計算する．
ボブは， $n$ ビットのベクトルであり，ちょうど $t$ 個の要素が１（残りは０）であるようなベクトル $z$ をランダムに生成する．（つまり，ベクトル $z$ の長さは $n$ で重みが $t$ ．）^[1]
ボブは暗号文として $c=c^{\prime }+z$ を計算する．

復号

暗号文 $c$ を受け取った時，アリスは次のようにして復号して元のメッセージを得る．

アリスは $P$ の逆行列 $P^{-1}$ を計算する．
アリスは ${\hat {c}}=cP^{-1}$ を計算する．
アリスは復号アルゴリズム $A$ を使って ${\hat {c}}$ を復号し，復号結果 ${\hat {m}}$ を得る．
アリスは $m={\hat {m}}S^{-1}$ を計算する． $m$ が元のメッセージである．

復号の正当性の証明

暗号化と復号の手順より， ${\hat {c}}=cP^{-1}=m{\hat {G}}P^{-1}+zP^{-1}=mSG+zP^{-1}$ が成り立ち， $P$ が置換行列であるため $zP^{-1}$ は重み $t$ のベクトルである．

ゴッパ符号 $G$ は最大 $t$ 個のエラーを訂正することができ，ベクトル $mSG$ と $cP^{-1}$ との距離は高々 $t$ である．したがって，復号アルゴリズムによって正しい符号語 ${\hat {m}}=mS$ が得られる．

$S$ の逆行列をかけることで， $m={\hat {m}}S^{-1}=mSS^{-1}$ が得られ，これはボブが送ったメッセージに等しい．

鍵のサイズ

初めの論文でマックエリスはパラメータとして $n=1024,k=524,t=50$ を提案していた．^[1] その場合，公開鍵のサイズは 524*(1024-524) = 262,000 ビットである．最近の解析により，80ビット安全を達成するためのパラメータとしては，標準的な代数的復号を使う場合は $n=2048,k=1751,t=27$ ，ゴッパ符号に対するリスト復号を用いる場合は $n=1632,k=1269,t=34$ とすることが提案されており，公開鍵長はそれぞれ 520,047ビット，460,647ビットとなる．^[5] 量子コンピュータでの解読に耐性を持たせるためには，ゴッパ符号を用いる場合は $n=6960,k=5413,t=119$ とすることが提案されており，公開鍵長は 8,373,911ビットになる．^[8]

攻撃手法

攻撃者は公開鍵 $({\hat {G}},t)$ を知っているが秘密鍵は知らず，手に入れた暗号文 $c\in \mathbb {F} _{2}^{n}$ から平文を復元したい．このような試みは（事実上）不可能であるべきである．

マックエリス暗号に対する攻撃手法は，大きく２系統に分かれる．

総当たり攻撃 / 非構造的な攻撃

攻撃者は，公開されている行列 ${\hat {G}}$ が $(n,k)$ 符号 ${\hat {C}}$ の生成行列であり，その符号は $t$ 個のエラーを訂正できる，という事実を知っている．

符号 ${\hat {C}}$ は，特定の符号の族から選ばれた何らかの構造を持った符号を難読化したものであるが，攻撃者はそのような事実を無視して，任意の線形符号に対する復号の方法を使うことができる．そのようなアルゴリズムとしては，符号の各符号語をチェックする方法，シンドローム復号法，information set decodingなどがある．しかし，一般の線形符号の復号はNP困難であることが知られており，^[3]上述の方法はすべて指数的な実行時間を必要とする．

2008年に，ダニエル・バーンスタインとLangeとPeters^[5]は，オリジナルのマックエリス暗号に対する実用的な攻撃を与えたが，それはStern^[9]による Information Set Decodingを用いたものである．最初にマックエリスが提案したパラメータを使った場合，攻撃は 2^60.55 回のビット演算で実行できる．その攻撃は完全に並列化できるため（ノード間の通信は必要ない），そこそこのコンピュータクラスターを使えば数日で攻撃が完了する．

構造的攻撃

攻撃者は $C$ の構造を復元し，それによって効率的な復号アルゴリズム $A$ か，あるいは他の十分効率的な復号アルゴリズムを見つけようとすることもできる．

このようなことが攻撃者にできるかどうかは， $C$ をどのような符号の族から選ぶかで決まる．マックエリス暗号で利用する符号族として多くの符号族が提案され，そのうちのほとんどのもの（例えばリード・ソロモン符号）に対しては，効率的な復号アルゴリズムが見つかっており，全く安全ではない．

最初に提案された二元ゴッパ符号は，構造的攻撃によって未だ破られていない数少ない符号族の一つである．

参考文献

^ ^a ^b ^c McEliece, Robert J. (1978). “A Public-Key Cryptosystem Based On Algebraic Coding Theory”. DSN Progress Report 44: 114-116. Bibcode: 1978DSNPR..44..114M.
^ Dinh, Hang; Moore, Cristopher; Russell, Alexander (2011). Rogaway, Philip (ed.). McEliece and Niederreiter cryptosystems that resist quantum Fourier sampling attacks. Advances in cryptology --- CRYPTO 2011. Lecture Notes in Computer Science. Vol. 6841. Heidelberg: Springer. pp. 761–779. doi:10.1007/978-3-642-22792-9_43. ISBN 978-3-642-22791-2. MR 2874885。
^ ^a ^b Berlekamp, Elwyn R.; McEliece, Robert J.; Van Tilborg, Henk C.A. (1978). “On the Inherent Intractability of Certain Coding Problems”. IEEE Transactions on Information Theory IT-24 (3): 384-386. doi:10.1109/TIT.1978.1055873. MR0495180.
^ N. J. Patterson (1975). “The algebraic decoding of Goppa codes”. IEEE Transactions on Information Theory IT-21 (2): 203-207. doi:10.1109/TIT.1975.1055350.
^ ^a ^b ^c Bernstein, Daniel J.; Lange, Tanja; Peters, Christiane (8 August 2008). Attacking and defending the McEliece cryptosystem. Lecture Notes in Computer Science. 5299. 31-46. doi:10.1007/978-3-540-88403-3_3. ISBN 978-3-540-88402-6. https://eprint.iacr.org/2008/318
^ Bernstein, Daniel J. (2010). Sendrier, Nicolas (ed.). Grover vs. McEliece (PDF). Post-quantum cryptography 2010. Lecture Notes in Computer Science. Vol. 6061. Berlin: Springer. pp. 73–80. doi:10.1007/978-3-642-12929-2_6. ISBN 978-3-642-12928-5. MR 2776312。
^ “eBATS: ECRYPT Benchmarking of Asymmetric Systems”. bench.cr.yp.to (2018年8月25日). 2020年5月1日閲覧。
^ Daniel Augot (2015年9月7日). “Initial recommendations of long-term secure post-quantum systems”. PQCRYPTO: Post-Quantum Cryptography for Long-Term Security. 2020年7月30日閲覧。
^ Jacques Stern (1989). A method for finding codewords of small weight. Lecture Notes in Computer Science. 388. Springer Verlag. 106-113. doi:10.1007/BFb0019850. ISBN 978-3-540-51643-9

外部リンク

Alfred J. Menezes; Scott A. Vanstone; A. J. Menezes; Paul C. van Oorschot (1996). “Chapter 8: Public-Key Encryption”. Handbook of Applied Cryptography. CRC Press. ISBN 978-0-8493-8523-0. http://cacr.uwaterloo.ca/hac/

“Quantum Computers? Internet Security Code Of The Future Cracked”. Science Daily. Eindhoven University of Technology (2008年11月1日). 2020年7月30日閲覧。

“Classic McEliece”. 2020年7月30日閲覧。 (Submission to the NIST Post-Quantum Cryptography Standardization Project)

[McEliece2-1] McEliece, Robert J. (1978). “A Public-Key Cryptosystem Based On Algebraic Coding Theory”. DSN Progress Report 44: 114-116. Bibcode: 1978DSNPR..44..114M.

[quantum-fourier2-2] Dinh, Hang; Moore, Cristopher; Russell, Alexander (2011). Rogaway, Philip (ed.). McEliece and Niederreiter cryptosystems that resist quantum Fourier sampling attacks. Advances in cryptology --- CRYPTO 2011. Lecture Notes in Computer Science. Vol. 6841. Heidelberg: Springer. pp. 761–779. doi:10.1007/978-3-642-22792-9_43. ISBN 978-3-642-22791-2. MR 2874885。

[intractability-3] Berlekamp, Elwyn R.; McEliece, Robert J.; Van Tilborg, Henk C.A. (1978). “On the Inherent Intractability of Certain Coding Problems”. IEEE Transactions on Information Theory IT-24 (3): 384-386. doi:10.1109/TIT.1978.1055873. MR0495180.

[Patterson-4] N. J. Patterson (1975). “The algebraic decoding of Goppa codes”. IEEE Transactions on Information Theory IT-21 (2): 203-207. doi:10.1109/TIT.1975.1055350.

[fix-5] Bernstein, Daniel J.; Lange, Tanja; Peters, Christiane (8 August 2008). Attacking and defending the McEliece cryptosystem. Lecture Notes in Computer Science. 5299. 31-46. doi:10.1007/978-3-540-88403-3_3. ISBN 978-3-540-88402-6. https://eprint.iacr.org/2008/318

[6] Bernstein, Daniel J. (2010). Sendrier, Nicolas (ed.). Grover vs. McEliece (PDF). Post-quantum cryptography 2010. Lecture Notes in Computer Science. Vol. 6061. Berlin: Springer. pp. 73–80. doi:10.1007/978-3-642-12929-2_6. ISBN 978-3-642-12928-5. MR 2776312。

[7] “eBATS: ECRYPT Benchmarking of Asymmetric Systems”. bench.cr.yp.to (2018年8月25日). 2020年5月1日閲覧。

[PQcrypto-initial-8] Daniel Augot (2015年9月7日). “Initial recommendations of long-term secure post-quantum systems”. PQCRYPTO: Post-Quantum Cryptography for Long-Term Security. 2020年7月30日閲覧。

[9] Jacques Stern (1989). A method for finding codewords of small weight. Lecture Notes in Computer Science. 388. Springer Verlag. 106-113. doi:10.1007/BFb0019850. ISBN 978-3-540-51643-9

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]