🌟

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

2022/08/04に公開約700字

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

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

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

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

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

Discussion

ログインするとコメントできます