符号系の公開鍵暗号HQCがつい最近PQCに選ばれた。
この暗号は符号は何でもいいが、暗号文に過剰なエラーを加えておき、秘密鍵を知っている人だけがそのエラーの重みを減らすことができる。
そして、その結果誤り訂正可能になる。
McElieceのように符号の構造を隠すのではなく、暗号文に細工をするところが大きな特徴である。
符号にはリードソロモン符号を外符号として、内符号をリードマラー符号を使うなど、かなりマニアックな符号化を使うようだ。
また公開鍵を作るときにエラーベクトル同士の積を撮る場合、Schur積と呼ばれる積を導入しエラーの重みが減るように出来ている。
ここでSchur積とは以下のような演算である。
$$ x*y=(x_1,x_2,x_3,x_4)*(y_1,y_2,y_3,y_4)=(x_1y_1,x_2y_2,x_3y_3,x_4y_4) $$
$h$を$n$bitサイズの公開乱数とし、以下同様に秘密のエラーベクトルを$sk=(x,y)$とする。
公開鍵は$pk=(h,s=x+h*y)$である。（これだけ）
暗号化は次のようにする。
２つのランダムベクトル$r=(r_1,r_2)$を使って$u=r_1+h*r_2$とし、$v=mG+s*r_2+e$とする。
暗号文は$c=(u,v)$である。
$$m=Decode.(v-u*y)$$
ここで、エラーベクトルの重みは、
$$w(x*r_2+r_1*y+e)<t$$
となるのであろう。ここでエラーベクトル$hyr_2$が消えることでエラーベクトルの重みを減らしている。