格子暗号を学ぶにあたって学んだことを要約した。暇なら読んでくれ。
今までの暗号方式として以下の2つが挙げられる。
- RSA 暗号: 素因数分解
-
楕円曲線暗号: 楕円曲線離散対数問題
- それぞれそこに安全性をおいていたが、量子計算機により容易に解かれることが示された。
そこで現れたのが格子暗号である。格子は以下の式で定義される。
-
L{b1, b2, b3, …, bn}={v∈Z^n :v=x_1*b_1+x_2*b_2+…+x_n*b_n} -
b1, b2, b3, …, bnは一次独立なベクトルである。 -
{b1, b2, b3, …, bn}を基底(basic)と呼ぶ。 -
nを格子の次元(dimension) -
n個の基底ベクトルを行ベクトルにもつn*nの行列をBと表し、格子Lの基底行列と呼ぶ。 -
整数全体の集合を
Zで表す。
<最短ベクトル問題>
-
n次元格子Lの基底{b1, b2, b3, …, bn}が与えられたとき、格子上の最短な非零ベクトルv∈Lを見つけるという問題。
<最近ベクトル問題>
-
n次元格子Lの基底{b1, b2, b3, …, bn}と目標ベクトルWが与えられたとき、目標ベクトルwに最も近い格子ベクトルv∈Lを見つける問題。
<格子暗号の仕組み>
- 行列
B, Cを考える。それぞれ3*3の行列とする。 -
B, Cの行ベクトルは{b1, b2, b3}, {c1, c2, c3}となり、同一の3次元格子L`を生成する。B, CはLの異なる2つの基底行列となる。 - ちなみに、
BC^-1がユニモジュラ行列だったら同じ格子を生成する。
Bを公開鍵、Cを秘密鍵とする。仕組みを記す。
- 平文ベクトル
m={m1, m2, m3}を暗号化することを考える。 - 使用者は小さい(
Bが10^7桁に対して1桁程度の)乱数ベクトルe={e1, e2, e3}を適当に選んで公開鍵用の基底行列Bを用いて暗号化ベクトルw=mB+eを生成する。 - この暗号化ベクトルに対して、秘密鍵用の基底行列
Cを持つ複合者は格子ベクトルv=「wC^-1」Cを計算することで平文ベクトルに関する格子ベクトルmBを正しく復元できる。 - 「」に入るベクトルは各成分を最近似整数に丸め込んだ整数ベクトルとする。
- さらに基底行列
Bを用いて、vB^-1の計算により平文ベクトルmを正しく複合できる。
<良い基底と悪い基底>
この2つに関して明確な定義はない。
- 良い基底: 各ベクトルが短くかつ互いのベクトルが直行に近い基底のこと
- 悪い基底: 各ベクトルが長くかつ互いのベクトルが平行に近い基底のこと
良い基底を用いると、「wC^-1」Cを解くことで、最近ベクトル問題を解くことができる。悪い基底行列と暗号化ベクトルから目的の格子ベクトルvの復元は難しい。
- ただし、低次元の格子なら悪い基底→良い基底と変換できてしまうので一般的に高次元の格子が利用される。
<格子基底簡約>
- 任意の基底
{b1, b2, b3, …, bn}が与えられたとき、同じ格子を生成する良い基底に変換する操作のこと。 - LLL(Lenstrn Lenstra Lova’sn)基底簡約という代表的なアルゴリズムが存在する。
- BKZ(Block-Korkine-Zolotareff)基底簡約というLLLを一般化したアルゴリズムも存在する。
<安全性評価に関して>
- 上記から分かるように悪い基底(公開鍵)から良い基底(秘密鍵)に変換するにあたり必要な計算時間がその暗号の安全性となる。