１．素体上構成したNiederreiter暗号（暫定版）

さー、論文がバンバン増えましたね。
最初は2本だけだったのに今や６本。
結論出せるんでしょうか？？
今回はかなり気合を入れて、論文を一字一句読むつもりなので期待してね！ｗ

Niederreiter暗号は、Classical McEliece暗号の双対方式として知られている。（参考文献）
奇素数及び、奇素数の拡大体で符号を作ると、訂正能力が上がる。
Bernsteinらは奇素数の拡大体を用いてWild McEliece暗号を構成し、従来のMcEliece暗号の公開鍵のサイズを小さくすることができることを示した。
一方、素体上で構成された例が無かったので、素体をNiederreiter暗号に用いた場合の安全なパラメータを算出した。
Bernsteinらの方式では小さな$2< p < 31$までの奇素数を基礎体に持つような拡大体だったので、それより少し大きい$256<p<8192$の範囲の素体を使って構成してみることにした。
ここでは既存の攻撃手法として知られている、総当り攻撃と、公開鍵の代数的構造を使った攻撃の2種類を、素体の場合に限って、その安全性を調べることにする。

２．古典的Goppa符号とは

古典的Goppa符号のパリティ検査行列は、以下のような構造を持つ。

同一人物の名前が付いたGoppa符号とは代数曲線の有理点から構成するものを指しており、古典的な方は１変数多項式の式の値（トレース）から構成するもので若干異なる。
Janwa,MorenoはこのGoppa符号からMcEliece暗号を構成したが、現時点では鍵復元攻撃がGoppa符号を使ったものに対しても有効であるために、古典的Goppa、およびGoppa符号の双方において部分体部分符号を用いたMcEliece暗号のみが安全であると知られている。
ここでは古典的Goppa符号の素体バージョンが安全かを調べる。

McEliece暗号では、古典的Goppa符号が同じパラメータをもつ本質的に異なる多くの符号を構成できる事を利用して、公開鍵暗号のトラップドア関数を実現している。

（しかし、文献によると、$GF(q),q \geq 31$の素体を使った場合はまだ攻撃法が見つかっていないらしい。)

この暗号の利点は、$GF(2^m)$上で符号を構成したときに比べ同等な処理速度と、公開鍵サイズが小さくなることである。
ここで扱う暗号系は、$GF(p)$（$p$は素数）上定義した非既約多項式をGoppa多項式として使ったものになる。

３．公開鍵サイズの縮小

まず、素体上のGoppa符号を構成する。
この符号は潜在的な訂正能力はあるが、既存の方式では上手く性能を引き出すことができない。
つまり、訂正可能なエラーの数を増やすことができないので符号帳を伸ばす方法で攻撃に対抗しなければならない。
その前に、まずバイナリ符号からｑ進符号に変更することでどのように攻撃体制が強化されるのかについて見てみたい。

次に、$GF(3067)$上正則なスクランブル行列$S$をパリティ検査行列$H$にかけて、最後に置換行列$P$をかけて列を入れ替えれば公開鍵の出来上がりである。
つまり、
$$H_{pub}=SHP$$
である。
通常の一般化置換行列を用いて公開鍵を生成した場合に、鍵の構造から生成多項式やスクランブル行列がわかるかどうかが公開鍵の安全性に対する安全性となる。

この時、公開鍵のサイズは$64 *3067 *12=2355456$bitとなる。
参考までに$q=1129 ,953$の場合も載せておく。（準備中）

素体上で構成されたGoppa符号を用いた暗号系は2014年（古っ）の時点では解読されていないようである。（現在どうなっているかは資料が見つからなかった。）
秘密鍵であるスクランブル行列が鍵回復攻撃でも計算できないなら、それを基準に安全であることが言えるだろう。
特に、公開鍵の代数的構造を利用した鍵回復攻撃が素体で構成された場合には適用できるかどうかはまだ分かっていない。
後半ではこのようなスクランブル行列が公開鍵の安全性にとって効果があるかどうかを調べる。

４．ピーターソン復号（準備中）

素体上構成したWild Goppa符号は、比較的簡単に理解できるピーターソン法で復号可能である。
なおNiederreiter暗号はシンドロームが暗号文になる。
また、McElieceバージョンの場合はリスト複号など最新の復号アルゴリズムが存在する。
論文には、訂正能力が$\lceil (q-1)t/2\rceil$であると書かれてあるが、少なくともピーターソン復号法ではそんなに性能が出ない。なのでここでは$\frac{deg(g)}{2}=\frac{k}{2}=t$として訂正可能なエラーの数とする。
文献では訂正能力を上げるために、リスト復号が行われるが、Niederreiter暗号の場合は、暗号文が符号語ではないのでこの方法は使えない。
よってより多くのエラーを入れることで強度を増やすことはできない。
従って、安全であるために、例えば符号長を最大8191まで上げることを視野に入れている。

５．いろいろな攻撃に対するパラメータの比較

ここでは参考文献をもとに、暗号文に対する攻撃と公開鍵に対する攻撃の中で、特に強力な攻撃に対するパラメータを計算する。
特に、符号を構成する素体の元のサイズが、どのように攻撃を難しくするのかに焦点を当ててみたい。
（コードはあるんですが誰も見ないと思うんで自粛）

5.1　総当たり攻撃

力ずくの攻撃で、ランダムなエラーを生成してシンドロームに対応するエラーベクトルを見つける攻撃である。

以下の３つのパラメータを確認する。
$1.[n=3067,k=64,t=32]$
$2.[n=1129,k=128,t=64]$
$3.[n=887,k=256,t=128]$

すると、

$$_{3067} C _{32} > 10^{76}=253bit ≒ 10^{77}$$

$$_{1129} C _{64} > 10^{105}=350bit ≫ 10^{77}$$

$$_{887} C _{128} > 10^{157}=523bit ≫ 10^{77}$$

しかも、この方法では$p$元のエラーを考えなければならないので、$p^t$だけ先の組み合わせの数に乗じたものとなる。

5.2　代数的攻撃（準備中）

公開鍵の代数的な構造に注目して、秘密鍵であるGoppa多項式を求める方式である。
この場合、攻撃に必要な評価式は以下のようになる。
ここで$t$は体の拡大次数らしいがよくわからない。
もし次数なら、素体なので$t=1$である。以下はそのようにして計算されたものである。

Goppa識別攻撃を考慮するとパラメータは、（符号化率$0．79$の場合）
$1. [n=1129,k=892,q=1129,223,446,1,1]$
$2. [n=887,k=700,q=887,175,350,1,1]$
である。

以下ではこの２つのパラメータのときの、代数的構造攻撃を評価する。
（つづく）

参考文献

Marek Repka and Pierre-Louis Cayrel。Chpter 5 Cryptography Based on Error Correcting Codes: A Surevey、Multidisciplinary Perspectives in Cryptology and Information Security、pp.139-141、2014。