マックエリス暗号のソースを表示

'''マックエリス暗号'''（McEliece_cryptosystem）は、[[暗号理論]]において，[[公開鍵暗号]]方式の一つであり，1978年にロバート・マックエリス（[[Robert McEliece]]）によって提案された<ref name="McEliece2">{{cite journal|last=McEliece|first=Robert J.|year=1978|title=A Public-Key Cryptosystem Based On Algebraic Coding Theory|url=https://ipnpr.jpl.nasa.gov/progress_report2/42-44/44N.PDF|journal=DSN Progress Report|volume=44|pages=114-116|bibcode=1978DSNPR..44..114M}}</ref>。 この暗号方式は，最初の確率的な暗号方式であり，一つの平文から異なる暗号文が生成される．この暗号方式は暗号コミュニティにおいてあまり注目を浴びてこなかったが，[[ショアのアルゴリズム]]を用いた攻撃で破ることができないため，[[耐量子暗号]]の候補の一つとなっている<ref name="quantum-fourier2">{{cite conference|year=2011|mr=2874885|conference=Advances in cryptology --- CRYPTO 2011|isbn=978-3-642-22791-2|volume=6841|series=Lecture Notes in Computer Science|editor1-last=Rogaway|editor1-first=Philip|doi=10.1007/978-3-642-22792-9_43|publisher=Springer|title=McEliece and Niederreiter cryptosystems that resist quantum Fourier sampling attacks|location=Heidelberg|pages=761-779|last3=Russell|first3=Alexander|last2=Moore|first2=Cristopher|last1=Dinh|first1=Hang|doi-access=free}}</ref>．

この暗号方式は，[[線形符号]]の復号困難性（これは[[NP困難]]であることが知られている）に基づいている<ref name="intractability">{{cite journal|last1=Berlekamp|first1=Elwyn R.|last2=McEliece|first2=Robert J.|last3=Van Tilborg|first3=Henk C.A.|year=1978|title=On the Inherent Intractability of Certain Coding Problems|journal=IEEE Transactions on Information Theory|volume=IT-24|issue=3|pages=384-386|doi=10.1109/TIT.1978.1055873|mr=0495180}}</ref>．復号に用いられる秘密鍵は，効率的に復号可能で<math>t</math> 個のエラーを訂正可能な[[誤り訂正符号]]である．マックエリスによるオリジナルの方式は，二元[[ゴッパ符号]]（標数が２である有限体上の種数0の曲線で定義される[[ゴッパ符号]]）を用いている．この符号はPattersonによるアルゴリズムにより，効率的に復号できる．<ref name="Patterson">{{cite journal|author=N. J. Patterson|year=1975|title=The algebraic decoding of Goppa codes|journal=IEEE Transactions on Information Theory|volume=IT-21|issue=2|pages=203-207|doi=10.1109/TIT.1975.1055350}}</ref> 暗号化に用いる公開鍵は，秘密鍵である符号を一般的な線形符号に「偽装」することで得られる．このために，符号の[[生成行列]] <math>G</math> を，二つのランダムに選ばれた可逆行列 <math>S</math> と <math>P</math>  によって攪乱する．（具体的な方法については下を参照のこと．）

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

ゴッパ符号を用いたマックエリス暗号は現在のところ解読されていない．最も効率の良い攻撃方法として知られているのは [[information-set decoding]]アルゴリズムを用いるものである．2008年の論文には，攻撃手法と修正方法が示されている．<ref name="fix">{{cite book|last1=Bernstein|journal=Proc. 2nd International Workshop on Post-Quantum Cryptography|isbn=978-3-540-88402-6|url=https://eprint.iacr.org/2008/318|doi=10.1007/978-3-540-88403-3_3|pages=31-46|volume=5299|series=Lecture Notes in Computer Science|title=Attacking and defending the McEliece cryptosystem|first1=Daniel J.|date=8 August 2008|first3=Christiane|last3=Peters|author2-link=Tanja Lange|first2=Tanja|last2=Lange|citeseerx=10.1.1.139.3548}}</ref> 別の論文では，量子コンピュータに対して安全にするためには，鍵サイズを４倍に延ばす必要があることが示されている．これは， 量子コンピュータによって information set decoding が効率化できるからである.<ref>{{cite conference|first=Daniel J.|last=Bernstein|year=2010|title=Grover vs. McEliece|url=https://cr.yp.to/codes/grovercode-20091123.pdf|publisher=Springer|location=Berlin|series=Lecture Notes in Computer Science|volume=6061|conference=Post-quantum cryptography 2010|mr=2776312|pages=73-80|doi=10.1007/978-3-642-12929-2_6|editor1-first=Nicolas|editor1-last=Sendrier|isbn=978-3-642-12928-5}}</ref>

マックエリス暗号の利点 --- 例えば[[RSA暗号]]などと比較して --- として，暗号化と復号が速いことが挙げられる．<ref>{{cite web|url=https://bench.cr.yp.to/ebats.html|title=eBATS: ECRYPT Benchmarking of Asymmetric Systems|date=2018-08-25|website=bench.cr.yp.to|access-date=2020-05-01}}</ref> 長い間，マックエリス暗号で [[デジタル署名]] は生成できないだろうと考えられてきた．しかし，マックエリス暗号の双対版である[[Niederreiter cryptosystem|Niederreiter]]暗号を用いると署名方式を構築することができる．マックエリス暗号の一番大きな欠点は，公開鍵と秘密鍵が大きな行列であることである．標準的なパラメータにおいては，公開鍵は512KB（キロバイト）である．

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

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

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

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

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

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

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

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

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

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

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

== 鍵のサイズ ==
初めの論文でマックエリスはパラメータとして <math>n=1024, k=524, t=50</math> を提案していた．<ref name="McEliece2" /> その場合，公開鍵のサイズは 524*(1024-524) = 262,000 ビットである． <!--{{clarify |date=May 2016 |reason= 524*1024 = 536576. The numbers do match the "standard form" from the generator matrix article. If that is the case, please clarify.}}．--> 最近の解析により，80ビット安全を達成するためのパラメータとしては，標準的な代数的復号を使う場合は <math>n=2048, k=1751, t=27</math>，ゴッパ符号に対するリスト復号を用いる場合は<math>n=1632, k=1269, t=34</math> とすることが提案されており，公開鍵長はそれぞれ 520,047ビット，460,647ビットとなる．<ref name="fix" /> 量子コンピュータでの解読に耐性を持たせるためには，ゴッパ符号を用いる場合は <math>n=6960, k=5413, t=119</math> とすることが提案されており，公開鍵長は 8,373,911ビットになる．<ref name="PQcrypto-initial">{{cite web|url=https://pqcrypto.eu.org/docs/initial-recommendations.pdf|title=Initial recommendations of long-term secure post-quantum systems|author=Daniel Augot|date=2015-09-07|work=PQCRYPTO: Post-Quantum Cryptography for Long-Term Security|display-authors=etal|access-date=2020-07-30}}</ref>

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

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

=== 総当たり攻撃  / 非構造的な攻撃 ===
攻撃者は，公開されている行列 <math>\hat G</math> が <math>(n,k)</math> 符号 <math>\hat C</math> の生成行列であり，その符号は<!-- combinatoriallyに --> <math>t</math> 個のエラーを訂正できる，という事実を知っている．

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

2008年に，[[ダニエル・バーンスタイン]]とLangeとPeters<ref name="fix" />は，オリジナルのマックエリス暗号に対する実用的な攻撃を与えたが，それはStern<ref>{{cite book|author=Jacques Stern|year=1989|title=A method for finding codewords of small weight|journal=Coding Theory and Applications|series=Lecture Notes in Computer Science|publisher=Springer Verlag|volume=388|pages=106-113|doi=10.1007/BFb0019850|isbn=978-3-540-51643-9}}</ref>による Information Set Decodingを用いたものである． 最初にマックエリスが提案したパラメータを使った場合，攻撃は 2<sup>60.55</sup> 回のビット演算で実行できる．その攻撃は完全に並列化できるため（ノード間の通信は必要ない），そこそこのコンピュータクラスターを使えば数日で攻撃が完了する．

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

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

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

== 参考文献 ==
<references />

== 外部リンク ==

* {{cite book|ref={{harvid|Handbook of Applied Cryptography|1996}}|title=Handbook of Applied Cryptography|publisher=CRC Press|year=1996|chapter-url=http://cacr.uwaterloo.ca/hac/|author1=Alfred J. Menezes|author2=Scott A. Vanstone|author3=A. J. Menezes|author4=Paul C. van Oorschot|chapter=Chapter 8: Public-Key Encryption|isbn=978-0-8493-8523-0|url-access=registration|url=https://archive.org/details/handbookofapplie0000mene}}

* {{cite web|url=https://www.sciencedaily.com/releases/2008/10/081028132303.htm|title=Quantum Computers? Internet Security Code Of The Future Cracked|date=2008-11-01|work=[[Science Daily]]|publisher=[[Eindhoven University of Technology]]|access-date=2020-07-30}}

* {{cite web|url=https://classic.mceliece.org/|title=Classic McEliece|access-date=2020-07-30}} (Submission to the NIST [[Post-Quantum Cryptography Standardization]] Project)<!--
{{Cryptography navbox | public-key}}
{{Use dmy dates|date=March 2011}}

[[Category:Public-key encryption schemes]]
[[Category:Code-based cryptography]]
[[Category:Post-quantum cryptography]]
-->

{{デフォルトソート:まつくえりすあんこう}}
[[Category:暗号]]