格子暗号

デジタル大辞泉

こうし‐あんごう〔カウシアンガウ〕【格子暗号】

読み方：こうしあんごう

公開鍵暗号の一。格子上の点を原点からの複数のベクトルの和で表すとき、意図的に格子をわずかに斜めにずらしてベクトルの和の誤差項を導き、この誤差に暗号文のデータを対応させて公開鍵とする。秘密鍵から公開鍵を計算する際に、この誤差項を混入させることで、秘密鍵を割り出す計算を困難にさせる。また、格子の次元数を大きくすることで、解読の難度を高めることが可能となる。量子コンピューターを用いても解読が困難な耐量子暗号の候補として注目されている。

ウィキペディア

格子暗号

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/01/05 04:49 UTC 版)

格子暗号 (あるいは格子ベース暗号) とは、方式自体あるいは安全性証明において格子を用いる暗号プリミティブを示す一般的用語である。格子ベースの暗号方式 (公開鍵暗号方式や鍵共有方式) は現在、耐量子暗号（英語版）の重要な候補となっている。広く利用されている公開鍵方式である RSAや 楕円曲線暗号、ディフィー・ヘルマン鍵共有は、量子コンピュータ上で実行できるショアのアルゴリズムによって破られるが、いくつかの格子暗号は古典コンピュータと量子コンピュータの両方に対して攻撃耐性があると考えられている。さらに、多くの格子ベースの方式は、良く研究されている何らかの格子問題（英語版） (格子に関連した問題) が効率的に解けないという計算量的な仮定のもとで、安全であると考えられている。

歴史

1996年にミクロス・Ajtai（英語版）は、良く知られた格子問題の困難性を利用した最初の格子暗号の構成を示した^[1]。 シンシア・ドワーク（英語版）は、短整数解問題（英語版） (SIS) と呼ばれる格子問題の平均時の計算困難性が、ある格子問題の最悪時の計算困難性と同等かそれ以上であることを示した^[2]。そして、SIS問題の計算困難性と等価な安全性を持つハッシュ関数を示した。

1998年に、Jeffrey Hoffstein、Jill Pipher、Joseph H. Silvermanの3人は、NTRU暗号と呼ばれる格子ベースの公開鍵暗号方式を提案した^[3]。 しかし、彼らの方式は、最悪時の格子問題を解くことと等価 (あるいはそれ以上) な安全性を持つかどうかは知られていない。最悪時の計算量的困難性の仮定の下で安全性が証明された最初の方式は、2005年にOded Regevによって提案されている^[4]。この論文では、計算困難な問題としてLWE問題（英語版） (Learning with Errors問題) も提案されている。それ以降、多くの後続研究がRegevの安全性証明を改善したり^[5][6] 、方式の効率を改善している ^{[7][8][9][10]}。 さらに多くの研究が、LWE問題や関連した問題を元にして、暗号プリミティブを構築することに専念してきた。例えば、2009年にGentryは初めての 完全準同型暗号方式を提案したが、これは格子問題に基づいている^[11]。提案されたこの暗号方式では、暗号化されたデータは暗号化された状態のままで任意の計算が可能となり、イデアル格子（英語版）を用いGentryによって初めて実現されている^[12]。

数学的な背景

格子（英語版） ${\displaystyle L\subset \mathbb {R} ^{n}}$