積符号というのは符号理論の知る人ぞ知る符号である。
この記事では、この符号を如何にして暗号が構成されるのかを確認したい。
この話題はAIとの会話から思いついたものだ。
２つの符号があるとする。
この２つは任意でいいが、クロネッカー積と呼ばれる計算から生成行列が作られる。
ハミングハミング積符号の場合、長さ４９＝７＊７の符号語を得る。
このときこの符号語は、行から見ても列から見てもハミング符号の符号語である。
復号は繰り返し復号と呼ばれる、再帰的復号の元祖である。
ブロック符号でも繰り返し復号が出来るというので、ワタシ的にはツボである。
で、今回はこの正方形をした２次元符号語Cを使って暗号を作ってみる。
まず２次元符号語を７＊７の正方形符号とする。
更にこの符号の左からバイナリ正則行列をかけてランダム化する。
次に、右から置換行列をかける。
$G'=SGP$とする。
G'を乱数化した積符号の生成行列とし、公開する。
秘密の２次元バイナリエラーベクトルを(x,y)とする。
このランダム化した積符号$G'$に平文$m$を左からかけ、更にエラーを加える。
暗号化：
$v=mG'+sr_2+e$
$u=r_1+hr_2$
$c=(u,v)$
ここで、$v-uy$は
$mG'+sr_2+e-(r_1+hr_2)y$
$=mG'+(x+hy)r_2-r_1y-r_2hy+e$
$=mG'+xr_2+yr_1 +e$
$c=m(SGP)+xr_2+yr_1+e$
バージョン１（McEliece型）
復号：
秘密鍵$(x,y)$を使って、過剰なエラー$hyr_2$を消した後通常の誤り訂正を行う。
$c'=cP^{-1}=mSG+xr_2P^{-1}+yr_1P^{-1}+eP^{-1}=mSG+e'$
繰り返し復号を使ってエラー$e'$を消す。検査行列を$H$と置くと、
$c'H=e'H=syn$
$Decode(S^{-1}syn)=e'$
$c'+e'=mG$
ここで$G$は組織符号なので$m$がわかる。
バージョン２（Niederreiter型）
$v=r_3G'+sr_2+m$
$u=r_1+hr_2$
$c=(u,v)$
復号：
$v-uy$
$=RG'+sr_2-(r_1+hr_2)y+m$
$=RG'+(x+hy)r_2-r_1y-r_2hy+m$
$=RG'+xr_2+yr_1 +m$
$c=R(SGP)+xr_2+yr_1+m$
ここで、
$deg(x)>deg(yr_1+m)$
$deg(y)>deg(m)$
とすると、
$cH=syn$
$decode(syn)=m'$
$=xr_2+yr_1+m$
$m' \pmod x=yr_1+m=m"$
$m" \pmod y=m$
攻撃法は考え中。