１．Golay符号でミニチュア耐量子計算機暗号を作る
この記事は誤り訂正符号を知っている人向きです。
少なくとも生成多項式は何かとか、シンドロームとは何かという復号法についてイメージが出来る人向けです。
ガッツリ勉強したい人はこの本がおすすめです。
HQCは符号系の耐量子公開鍵暗号で、NISTのコンペで採用され、今後5年かけて将来の暗号規格として定着するものと考えられる。
HQCに関してはこちら！
符号と暗号を知らなければならないので、割とハードルが高いかも知れない。
今どきの符号はいくらでも誤り確率を減らすことが出来るので暗号には使えないかも知れないが、この暗号では敢えて訂正能力が有限なブロック符号を使って暗号を作っていると言えないだろうか。
で、HQCというのはHamming Quasi-Cycric Codesの略なのだが、代数的な復号法があるのかないのか詳しく書かれていない。（BM法で出来るのかも知れない。）
なのでRMRS符号（リードマラー符号とリードソロモン符号の連接符号）を使った場合をイメージしている。
まず使う符号は何でもいいとして、この暗号の面白いところは、秘密鍵を持たないと訂正能力以上のエラーを復号しなければならなくなり、秘密鍵を知らないという時点でお手上げとなるからだ。
ベクトル同士の積には畳み込み積（convolution）というものを使っている。
これは勘違いかも知れないのだが、エラーを消せるというのはとても斬新な発想だと思う。
で、今回のテスト実装では、エラーを消す方向で実装している。
いわば暗号文に細工をして、情報理論的にも効果があるように仕組まれているのではないか。
古くから知られている符号系の公開鍵暗号で、PQCの最終候補にも残ったMcEliece暗号と違って公開鍵の構造は秘密でなくても構わない。
使う符号に制限がないのだから、リードソロモン符号（とリードマラー符号）でいいということになる。
仕様書には使うべき符号としてリードソロモン符号の生成多項式が明記されているし、システムパラメータとして公開されている。
若しエラーを減らすことで復号可能にするというアイデアなら、小さな符号を使っても安全になりそうだ。
そこで今回はGolay符号という長さ23のバイナリ完全符号を使ってそのデモンストレーションをする。
ここでHQCの勘所である過剰なエラーを使って、暗号文にどのような細工をするかを見る。
まず、公開鍵を$pk$、秘密鍵を$sk$とする。すると、
$$pk=(h,s=x+h\oplus y),sk=(x,y)$$
である。ここで、$\oplus$はベクトルの畳み込み積であるとする。
暗号化は以下のようにする。
$$r=(r_1,r_2)$$
$$u=r_1+h\oplus r_2, v=mG+s\oplus r_2+e$$
復号手順は以下の通り。
$$v-u\oplus y=mG+(x+h\oplus y)\oplus r_2+e-(r_1+h\oplus r_2)\oplus y$$
$$=mG+x\oplus r_2-y\oplus r_1+e$$
Golay符号の生成多項式は$g(x)=x^{11}+x^9+x^7+x^6+x^5+x+1$であるので、メッセージ多項式にこの多項式をかけるだけで符号化出来る。
またWikipediaによると、バイナリ完全Golay符号は$x^{23}-1$からも構築できるので、巡回符号の一種でもある。
さて、ここで問題なのはエラー$xr_2-yr_1+e$である。
このベクトルは最終的に暗号文に残されるエラーなので、このエラーベクトルのハミング重みが一定以下になる必要がある。
$$wt(xr_2-yr_1+e)\leq3$$
でなければならない。
そして、エラー$h\oplus r_2\oplus y$は最終的には消える。
復号法は仕様書にバーレカンプをやるように書いてある。
エラーを入れて送信された暗号文（これは受信語でもある）からシンドロームを計算し、あとはシンドロームエラーのルックアップテーブルを使って代数的な処理なしに復号できる。
Golay符号はシンドローム空間が全部埋まっていて、重み３以下の全てのエラーベクトルとシンドロームの対応表が１対１に無駄なく対応付けられている。
この時、ルックアップテーブルのサイズは11bit=2048個である。
sage: G=codes.GolayCode(GF(2),extended=False)
sage: G.parity_check_matrix()
[1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 0 0 1 0]
[0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 0 0 1]
[0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 1 1 0]
[0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 1 1]
[0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 1 1 1]
[0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 1 1 0 1 0 1 0 1]
[0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 0 1 1 1 1 0 0 0]
[0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 0 1 1 1 1 0 0]
[0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 0 1 1 1 1 0]
[0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 0 1 1 1 1]
[0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 0 0 1 0 1]
sagemathによる、バイナリ完全Golay符号のパリティ検査行列。
符号の次元が11次元になり2048個のエラーに対応できる。
正確さを書いているかも知れないが、随時修正していく。
以上の設定でGolay符号を使ったHQCを作ってみた。
Golay符号の訂正能力は3個だけなので、$h\oplus r_2\oplus y$を消した後、最終的にハミング重み3以下のエラーにならなければならない。
ここで消えるエラーをどう生成するか悩んでいるのだが、なにかいい方法があればここで続きを書いてみたい。
２．コードを書いてみた
こんなの出来ました。
（ポインタがわからない）
本当は連接符号にするほうがいいのだろうけど、面倒なのでゴーレイ符号短髪で生きます。
エラーは足し算をxorで、掛け算をconvolutionで実装したらいい感じのエラーベクトルが出来ました。
convolutionの意味なんですが、この演算を実行すると、例えば３２ビット整数の各ビット位置に１が立つ確率を均等にできるらしいです。
それだけなんですが、実装してみて秘密鍵の情報が漏れるのではないかと気になります。
なのでベクトルの畳み込みは、ビット位置の情報を隠すためだ考えられます。（畳み込みの逆演算は出来るのかとか）
重みを適度に減らすことで、おもすぎるエラーベクトルの発生を少なくすることが出来ました。
一応復号まで出来ているので、残るの作業は安全性の証明です。
まず畳み込み演算の場合に、HQCのGolayバージョンで復号失敗確率を最小にするパラメータを考えます。
そして、鍵に対する安全性を考えます。
予定としては、公開鍵から秘密鍵を推測できるかということを、畳み込み乗算（合成積）の場合で考察します。
数学やらねば。
それでも、復号失敗確率は１％くらいで出来るようになりました。
完全符号とはいえ訂正可能なバイナリエラーのハミング重みはたかだか３なので、もっと性能のいい符号を使うべきだと思います。
wt(t)=3 wt(r)=6 wt(s)=6,wt(u)=6,wt(v)=6
wr(x)=1 wt(h)=5 wt(r1)=1,wt(r2)=1,wt(y)=1,wt(e)=1
Pub_key=(h,s)
s= 0,0,1,1,0,0,0,1,0,0,0,1,1,0,0,1,0,0,0,0,0,0,0,
h= 0,1,1,0,0,0,1,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,
Secret_key=(x,y)
x= 0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,
y= 0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
cipher =(u,v)
u= 0,0,0,0,0,0,0,0,0,1,1,0,0,0,1,0,0,0,0,1,0,1,1,
v= 0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,1,1,0,0,1,1,0,0,
r=(r_1,r_2)
r1=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,
r2=0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
e= 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,
v-uy=
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,1,
you are lucky.
10110011000110000000000
golay= 101011100011
text = 11111111
encode=00001100101100010100001
v =00110011000110000000000
v-uy =10011110101100010100001
syndy =10010010000000000000000
cipher=00111111101010010100001
decode=11111111
times=0 wt(xr_2-r_1y+e)=3
gistのプログラムによる、バイナリ出力サンプルです。
ご覧のとおりランダムビットのように見える暗号文から平文が復号できてます。
３．一般化リードソロモン符号とリスト復号を使う
リスト復号は高速で性能のいい復号法らしいです。
今まではシンドロームとエラーベクトルの対応表を使って復号してましたが、ちょっと冒険してリスト復号を覚えてみたくなりました。
実装には上の本を参考に使いました。
実装した感じどこがリストなのという謎が残りました。
で、ちょっと実装できたのですが、うまく行かない場合もあり考え中です。
McEliece直筆のリスト復号の教本があるのでそれを印刷して読んでいます。
シンドロームを使わないで補間多項式というものを計算することで、受信語だけから送信語を復号できます。
暗号を理解するためにHQCを実装しているわけですが、ちょっとオリジナルと違うことをしています。
まず素体上の一般化リードソロモン符号を使うこと、そして復号にはリスト復号を使うことです。
こういう実装をした場合の安全性を評価することが目標です。
オリジナルのHQCとは何かが違うのだろうけど、安全性に問題がなければこのままで行こう。
リードソロモンもごっぱ符号の中に含まれるので、単に生成多項式と定義体の違うGoppa符号を２つ使っているというイメージが正確かも。
なぜ素体を使うのかというと、拡大体よりシンプルに実装できるのと、バイナリ符号と組み合わせることで異なる代数系の演算と組み合わせでIDEAと同じようなセキュリティが実現できるのではないかと勝手に期待しています。
拡大体で高速に復号するためには高度な実装技術が必要なので、シンプルにしたのです。
リスト復号は直接送信語を計算できるので、エラーを計算して受信語から取り除くという手間がいりません。
送信語を決定できるので、復号原理もシンプルでエラーの値も同時に分かります。
エラーのハミング重みがわからくても、繰り返す必要がないので１回で確実に複合できるという利点があります。
しかし外符号にバイナリ符号を使う場合には、エラーの重みを指定する必要があります。
コレはマックエリス暗号と同じような制約です。
しかし二段目の復号に対してはエラーの重みが予測できません。
これはインターリーバを使う場合に必然となります。
ここで重みｔ以下のエラーベクトルを一括訂正できるリスト復号の利点がでてきます。
RMRSみたいに、バイナリ符号とリードソロモンを組み合わせた連接符号を使うことで性能的にもいいと思う。
バイナリ符号ならパターソン復号法が使えるので、通常よりも復号失敗確率が減るのではないかと期待していますが、違っているかも知れません。
暗号の安全性を保証するために、HQCではランダムなエラーを使う必要があります。
おそらく、バーレカンプを使う理由は電力解析に弱いからだと思われる。
で、１段めで複合できなかったエラーがどのように伝搬するのかを考える必要があります。
でも多分リスト復号を使えばなんとかなりそうな気もするんですが。
暗号の安全性に関しては現在勉強中です。
４．隣の国のPQC
韓国版PQCであるPALOMAという方式がかなり面白いので、規約でない多項式を使ったバイナリGoppa符号（Geometric Goppaとは違う）と組み合わせることが出来るのではないかと画策中です。
この暗号の面白いところは、今までの殆どの符号系暗号で既役なGoppa多項式（Goppa符号の生成多項式のこと）が使われていたのだが、復号法を改良して規約じゃない場合でもきちんと複合できるようにしたというところである。
これでどのようなGoppa多項式でも暗号に使えると言えないだろうか。
更に素体上にも拡張できると面白いのだが、私にはわからない。
そしてリスト復号とパターソン復号の頂上対決やいかに？
というわけで何がどうなるか、今後の展開をお楽しみに。
補遺
HQCについて
HQCの公開鍵暗号のベクトルの一つに準巡回構造を持つベクトルを使っているということをAIのコパイロットが言っています。
まあ本当かどうかはもう少し詳しく論文を読むしかないのですが、こんなマニアックなことはAIでもよくわからないようですね。
復号誤り率を厳密に計算するために、そのような構造を持つベクトルを公開鍵にしているということらしいです。
リスト復号について
リスト復号というイメージから言って、最小距離内で訂正可能な符号語のリストがドバっと送られてくるイメージだったのですが、実際にはハミング重みがT以下のエラーを訂正した後の符号語が１つ決まるという感じで良さそうだった。それ以上のエラーについても復号できるかも知れないけど、一意性が無くなりそうで嫌なのでそうします。
つまり、明示的にエラーの数$T+\epsilon$を示さないと、そのようなエラーは訂正できないということだろうか。
HQCの復号アルゴリズムはLDPCと同じ系統の繰り返し復号である
これはよく知らないので調べてから書きます。
秘密鍵がなくても符号の構造が明らかな場合は（ブロック符号など）平文が露呈する場合がある
以下随時加筆していきます。