耐量子計算機暗号HQCを参考に多項式暗号を作ってみた
HQCでは4つのベクトルを使って公開鍵を構成する。
つまり、大きな素体上の多項式x,yを秘密とし、hをランダム多項式の係数ベクトルとする。
鍵生成：
ベクトルはすべて多項式の係数であるものとする。
公開鍵はpk=(h,s=x+hy)であり、秘密鍵はsk=(x,y)である。
暗号化は以下のようにする。
暗号化；
ランダム多項式の係数ベクトルr=(r_1,r_2)とし、u=(r_1+hr_2)とすると、
v=sr_2+eとすると暗号文cはc=(u,v)となる。
復号：復号は以下のようにする。
f_0(\alpha+\gamma_i)=v-uy=xr_2-r_1y+m=r_1y+m=f_0 \pmod y +m=0+m=m
または、
f_1(\beta+\gamma_j)=v-uy=xr_2+m=f_1(\beta)=0+m=m
受信者はx,yを知っている。ここで秘密多項式に含まれる1次式の会をx=\alpha, y=\betaとして、f_0,f_1にそれぞれ代入することで、平文mを得ることができる。
x,yが既約多項式の場合は
f_0(\alpha) \pmod y +m=0+m=m
のように、合同式の計算によって平文多項式
mを計算するものとする。
f(\alpha)=r_1y+e,f(\beta)=xr_2となる。そこでこのn次多項式2式にf_0(\gamma_i)+f_1(\gamma_j)+m,i \neq jとなるようなn個のGF(P),|P|_2=256 - bit上の値をn個入れてn次多項式をラグランジュ補完で多項式で再構成する。
f_0,f_1が再構成できたところで、出てきた多項式に\alpha,\betaを再代入して、平文mの多項式を得る。
ここでは、平文太公式mの係数ベクトルを平文とする。
多項式の字数は非常に大きなものを想定しているが、この暗号の安全性の評価をしていないので、ここでは仮にn=256とおいて実験する予定である。
後日、続きを書きます。
ラグランジュ多項式補間を復号アルゴリズムに用いる暗号方式になると思われる。
Discussion