２の拡大体上で考えたLWE暗号もどき2

エラー入り多元連立１次方程式を解く問題に基づく公開鍵暗号

公開鍵：スクランブル行列Sでランダム化したした$[k,n]=[k,2k]-$Gopa符号のK*K生成行列A。
（$A$は単位行列$I$を左側に持っているが、それを削除した状態で公開し、符号語を作るときに暗号化する側が追加して$[I:A]$符号として計算するものとする）
秘密鍵：スクランブル行列S、Goppa符号の生成既約多項式ｇ

暗号化：ｍは要素数２K個の平文とする。いまｍを暗号化したいとする。
まずAを使って、ランダムベクトル２K個を符号化する。
こうすることで２K＊２Kのサイズの符号語を成分とする行列Fができる。

Fを転置した$F^{T}$をの右からｍをかけて右辺に２K個の値ｂを計算する。
大きさ２Kの行列の各列に、ハミング重みK/2のエラーeをいれたとすると、
$(F^{T} \oplus e,F^{T}m=b)=c$
となり、ｃは行列型の暗号文とする。
暗号文ｃのサイズは、平文のサイズをｎとすると$n^2+n$である。

復号
受信者は暗号文ｃの列を検査行列にかけ、シンドロームを計算する。
シンドロームにスクランブル行列Sの逆行列$S^{−1}$をかけて正しいシンドロームを復元する。
シンドロームからエラーeを計算し、列から取り除く。
これを２K回繰り返して、正しい連立方程式Bを得る。
ｍを未知の変数とすると、$Bm=b$からガウスの消去法を使ってｍが求められる。
しかし、$S,g$を知らなければエラーの入った多元連立１次方程式を解く必要がある。
或いは間違った値$ｍ’$が出てきてしまう。これを防止するためにAEADの仕組みを使う必要がある。