ハード格子の問題とは何ですか? 糸 🧵

格子ベースの暗号は、整数q(通常は素数または素数のべき乗)を割った線形方程式系の短いベクトル解sを見つけるという中心的な課題に依存しています。これはSIS(短整数解)問題と呼ばれ、形式は単純ですが量子的・古典的攻撃に対しては難しいと考えられています。

主に2つのバージョンがあります。1つはコミットメントスキームで一方向関数として使われる非同質形式f_A(s) = A * s mod qで、A * s = t (mod q) をAとターゲットtが与えられたときに解くものです...

...そして、ランダム行列Aに対してA * s = 0(qを模して)となる短いsを求める斉次SIS問題です。

コミットメントスキームはSISの厳格性によって拘束力が保証されています。もしA * s = t = A * s'ならば、A * (s - s') = 0であり、異なるs'を見つけることで硬斉次SIS問題が解決されます。

s(小ノルム)の短さは不可欠です。sに境界がなければ、古典線形代数を用いて解は自明である。この規範制限は、量子コンピュータに対してもSISの解法が難しい性質を支えています。

アジタイの1996年の結果は、SIS問題の難易度を最悪ケース格子問題の解決に結びつけ、ポスト量子暗号学の仮定の基盤を形成しました。

SIS問題により、大きな秘密ベクトルs(次元M)からより短いコミットメントtへの圧縮が可能になります。行列Aの次元はN×Mで、Nは通常セキュリティパラメータに結びついているため、簡潔さが必要なゼロ知識証明に魅力的です。

総合すると、SISは述べやすいが解くのは非常に難しく、コミットメント、ゼロ知識証明、そしてより広範なポスト量子セキュリティにおいて基本的な役割を果たしている。