格子暗号

ウィキペディア

格子暗号

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

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

歴史

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

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

数学的な背景

格子 $L\subset \mathbb {R} ^{n}$