格子暗号
格子暗号全般について学んだことのメモ
1. 格子問題と安全性について
素因数分解問題や離散対数問題とは違い、格子問題(Lattice Problems)に依拠した安全性を保有する。
最短ベクトル問題や最近ベクトル問題、LWE問題といった格子問題は高次元であればNP困難であることが知られており、格子問題を効率的に解く量子アルゴリズムは存在しないため量子耐性を持つとされる。
最短ベクトル問題
高次元格子において、最も短い非ゼロベクトルを見つける問題
最近ベクトル問題
与えられた任意の点に最も近い格子点を見つける問題
LWE（Learning With Errors）問題
既知の係数ベクトル $ \mathbf{a} と未知の秘密ベクトル $ \mathbf{s} 、小さなエラー項 $ e を含む線形方程式 $ \mathbf{a} \cdot \mathbf{s} + e \mod q が与えられる。
$ \mathbf{a} ：既知のベクトル
$ \mathbf{s} ：未知の秘密ベクトル
$ e：小さなエラー項
$ q：大きな素数
目標は、これらの方程式から秘密ベクトル $ \mathbf{s} を推測することである。
LWE問題の困難性は、エラー項 $ e の存在によって生じる。エラーがなければこれは単なる線形方程式の系であり、容易に解けるが、エラー項の存在により解を見つけることが非常に困難になる。
LWE問題は、量子コンピュータを使用しても効率的に解くことができないとされる。
これはLWE問題が高次元の格子問題に還元でき、これらの格子問題が量子コンピュータに対しても困難であるためである。
真面目に解こうとすればSVP、CVPに帰着してから解を求めることで比較的容易に問題が解ける場合がある。
また、基底同士の交わる角度が直交に近ければ近いほど解くのが簡単になる。このような格子を悪い格子と呼ぶ。格子問題を暗号に用いる場合には、基底の設定に注意する。
Ring-LWE問題
Ring-LWE問題では、係数が整数環 $ \mathbb{Z} または有限体 $ \mathbb{F}_q に属する多項式の環を考える。この環を $ R とする。通常、$ R は $ \mathbb{Z}[x]/(f(x)) または $ \mathbb{F}_q[x]/(f(x)) の形を取る。ここで、$ f(x) は既約多項式。
Ring-LWE問題では、次のような形の方程式を考える：
$ b(x) = a(x) \cdot s(x) + e(x) \mod f(x), \mod q
ここで、
$ a(x) はランダムな多項式で、公開されている。
$ s(x) は秘密の多項式で、ランダムな係数を持つ。
$ e(x) は小さなノイズを持つ多項式。
$ b(x) は結果の多項式。
Ring-LWE問題の主な利点は、効率性とセキュリティ。多項式の環を使用することで、暗号システムはより少ないリソースでより高速に動作することが可能になる。また、Ring-LWEは、従来のLWE問題と同様に、量子コンピュータに対しても強い耐性を持つと考えられている。
Ring-LWE問題は、同型暗号を含む多くの先進的な暗号方式において重要な役割を果たす。特に、効率的な同型暗号システムの構築において、Ring-LWEに基づくアプローチは重要な選択肢となっている。
2.同型暗号への応用
LWE問題を基にした同型暗号では、暗号化されたデータに対する演算が可能。
暗号化
メッセージ $ m を暗号化するために、次のような暗号化関数を使用する：
$ \text{Enc}(m) = \mathbf{a} \cdot \mathbf{s} + e + m \cdot r \mod q
ここで、$ r はランダムなスケーリング係数。
同型演算
暗号化されたメッセージ $ \text{Enc}(m_1) と $ \text{Enc}(m_2) に対して、加算や乗算などの演算を行うことができる。例えば、加算は次のように行われる：
$ \text{Enc}(m_1) + \text{Enc}(m_2) = (\mathbf{a} \cdot \mathbf{s} + e_1 + m_1 \cdot r_1) + (\mathbf{a} \cdot \mathbf{s} + e_2 + m_2 \cdot r_2) \mod q
この結果は、$ m_1 + m_2 の暗号化に相当する。
復号
復号関数は、暗号化されたメッセージから元のメッセージを取り出すために使用される。復号は、秘密鍵 $ \mathbf{s} を使用して行われる。
シンプルにLWE問題の数学的構造がベクトル空間(もしくはイデアル空間)上の演算なので同型暗号と相性良さそう。暗号化が線形性(または多項式性?)を持つように設計されてる(GPTに聞いてみた>ベクトル空間と同型暗号の相性について) 参考文献
↑なんかちょくちょく記述間違ってそう