GGH Cryptosystem

babai's_rounding

鍵生成

parameter

d：↑で出てきたように \vec{v_i}の値は \lbrack -d, d \rbrackだったりする

\delta：暗号化に使うパラメータ。誤差の大きさ

V = \begin{pmatrix} v_1 \ v_2 \ \vdots \ v_n \end{pmatrix}として格子 Lの基底とする。このとき v_iは短いベクトルで、具体的には kI + Eのように選ぶ（where k = \lceil \sqrt{n} + 1 \rfloor, E_{i,j} \in { -4, \dots, +3}

さらに要素が整数かつ、 \det(U) = \pm 1であるような Uを適当に選ぶ（ Vと同様に n \times nの行列）

つまり UはXXX行列（なんだっけ…名前をど忘れした）

public keyは W = UV

暗号化

平文 \vec{m} \in {0, 1}^n （実はもうちょっとサイズに差があってもいい）

ランダムなベクトル r \in { -\delta, \dots, \delta }^n。これはperturbation vector （摂動ベクタ）と呼ばれる

暗号 \vec{e} = \vec{m}W + \vec{r}

復号

徐に良い基底 { \vec{v_1}, \dots, \vec{v_n} }を持ってきて、 \vec{e}に対してbabai's_roundingする。すると \vec{m}Wがわかるので \vec{m}もわかる

{\vec{v_1}, \dots, \vec{v_n} }がいい基底というのはどこに登場したのかな

Alternative GGH Cryptosystem

\vec{e} = \vec{m}W + \vec{r}とする代わりに \vec{e} = \vec{r}W + \vec{m}とする手もある

すると \vec{r}Wがわかるので \vec{e} - \vec{r}W = \vec{m}