代数曲線を使ってメッセージを秘匿する。
$p$を大きな素数とし、$GF(p)$を定義体とする。
以後、この定義体上の楕円曲線を考える。
ここでは、楕円曲線の有限体の場合を考える。（BBGS曲線でもいいかも知れない。）
ここで、大文字のアルファベットは2変数多項式、小文字のアルファベットは1変数多項式を表すものとする。
１．２５６個以上の有理点を持つ楕円曲線を$C$とする。
同様に、この$C$上の256個の点の$x$座標を1次式としてもつ多項式の積を$f_0$とする。
また、大きな素体上で一般の代数曲線の有理点を求めるのは難しいと思われる。
そこで楕円曲線上の有理点をランダムに256個選び、そのx座標を解にもつような1変数多項式が$f_0$である。
２．ランダム代数曲線を$R$、ランダムな1変数多項式を$r$とする。
３．更に、メッセージを表す多項式を$m$とする。
ここで平文を表す多項式が多変数でないのは多変数バージョンのラグランジュ補間を知らないからである。
暗号化
$H$を公開されたランダム2変数多項式とする
$sk=(C,f_0)$
$pk=(H,S=C+Hf_0)$
$U=R+rH$
$V=Sr+m=(C+Hf_0)r+m=Cr+Hf_0r+m$
$c=(U,V)$
復号
$F=(V-Uf_0)=Cr+f_0Hr+m-(R+rH)f_0=Cr+Rf_0+m$
$F(\alpha_{x,y})=m(\alpha_x)-f_0(\alpha_x)r(\alpha_x)=m(\alpha_x)$
ここで、曲線$C$と$f_0$が消えるので、有理点の$x$座標の値だけを代入して得られた数値から、ラグランジュ補間を使って多項式$m$を復元する。
これができるのは秘密の点を知っている人だけである。
パート１と違うのは暗号化に使う秘密鍵が楕円曲線の点であることである。
本当は超楕円曲線のほうがいいと思うが、有理点の計算方法がわからない。
楕円曲線の場合は、特定の座標を持つ1点が求まれば、後は群法則から効率的に他の有理点が計算できるが、大きな素体上の代数曲線でも256個の有理点が計算できればその方がいいと思う。
また、パート1では秘密鍵である1変数関数を知っていれば十分だったが、ここでは曲線の点が秘密鍵になったことで1変数の多項式の剰余では平文が復元できないと思うので、ラグランジュ補間が意味を持つようになるだろう。（Cが明らかな時は剰余でもいいのかも知れない。）
任意の代数曲線を点の座標から復元可能であるような、ラグランジュ補間の２変数バージョンがあればなお良い。
もし。有理点の集合からもとの曲線を復元する方法があれば、多変数バージョンに拡張することができると思う。（予想）