Skip to content
検索結果に戻る

格子暗号 (Lattice-Based Cryptography)

提唱者
Miklós Ajtai
年
1996
種類
public-key cryptosystem based on lattice hardness
系統
Post-quantum cryptography

この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む

文字サイズ

何をする手法か?

格子暗号は、格子問題、特に最短ベクトル問題 (SVP) および誤差付き学習 (LWE) の計算上の困難性からその安全性が導かれる暗号方式の一種である。1996年にMiklós Ajtaiによって初めて提案された格子ベースのアプローチは、ポスト量子暗号の主要な候補として注目を集めている。量子コンピュータに対して脆弱なRSAやECCとは異なり、格子問題は量子アルゴリズムに対しても困難であり続けると考えられている。

手法の背後にある直感

格子とは、基底ベクトルの整数線形結合によって形成される、ユークリッド空間の離散部分群である。格子暗号は、2つの問題間のギャップを利用する。格子内の短いベクトルを見つけることは計算上困難であるが、追加情報(秘密基底)があれば、短いベクトルは迅速に見つけることができる。公開鍵暗号は、困難な基底を公開し、容易な基底を秘密に保つことによって構築される。誤差付き学習のパラダイムにおける小さなランダムノイズの追加は、問題を解くのが困難なノイズのある線形システムに似せることで、セキュリティをさらに強化する。

歴史学

Ajtaiによる1996年の基礎的な研究は、格子の困難性を暗号と結びつけた。Regevによる2005年の誤差付き学習 (LWE) フレームワークは、格子暗号の実用的かつ汎用的な基盤を提供した。現在の暗号インフラストラクチャに対する量子コンピューティングの脅威が学術機関や政府機関によって認識された後、この分野は加速した。2022年、NISTはポスト量子暗号アルゴリズムを標準化し、格子ベースのスキーム(暗号化にはCRYSTALS-Kyber、署名にはCRYSTALS-Dilithium)を主要な推奨事項として選択した。

使うべき場面

格子暗号は、将来の量子コンピュータからの攻撃に対して安全であり続けるように設計されたシステムに不可欠である。長期的な機密性を持つ機密データ、政府および軍事通信、そして数十年にわたって安全性を維持する必要があるインフラストラクチャに推奨される。標準化されたポスト量子アルゴリズム(NISTは最近ML-KEMとML-DSAを標準化した)が成熟するにつれて、格子方式は現代の暗号システムにおいて主流になりつつある。

限界と注意点

  • 従来のRSAやECCと比較して、鍵と暗号文のサイズが大きい。ストレージと伝送のオーバーヘッドが増加する
  • RSAやECCよりも新しく、展開実績が少ないため、実世界の展開経験は限られている
  • 一部の格子ベースのスキームには、セキュリティに大きく影響する微妙なパラメータ選択があり、不適切なパラメータは壊滅的な結果をもたらす可能性がある

出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。

強み

  • 量子コンピュータ攻撃(Shorのアルゴリズムを含む)への耐性があると考えられている
  • よく研究された格子問題に基づく強力な数学的基盤
  • 同じフレームワーク内で暗号化とデジタル署名の両方をサポート
  • 現代のハードウェアに対して合理的な計算コストで利用可能な実用的な実装

応用

  • 将来の量子復号に対して通信を保護するためのポスト量子トランスポートセキュリティ
  • 数十年にわたって秘密を保つ必要がある文書およびデータの長期アーカイブ暗号化
  • 量子脅威に耐性のある政府および軍事通信システム
  • 量子耐性セキュリティのために設計されたブロックチェーンおよび暗号通貨システム
  • 量子耐性が設計要件であるIoTおよび組み込みシステム
  • 暗号移行期間中の格子アルゴリズムと従来のアルゴリズムを組み合わせたハイブリッド暗号システム

使い方

使い方

1

格子の次元n、法q、および誤差分布を選択する。秘密の短い基底を生成し、格子変換を用いてそれから公開基底を導出する。

2

公開鍵は困難な格子基底から導出される。計算上の観点からは、秘密基底に関する情報は一切提供しない。

3

暗号化するには、平文を公開基底ベクトルのノイズのある線形結合に追加し、ノイズ付き格子点を作成する。

4

秘密の短い基底を使用して、ノイズ付き格子点を還元し、平文を抽出する。

よくある落とし穴

  • 格子パラメータ(次元、法、誤差分布)の選択は自明ではない。標準のNIST承認パラメータの使用を強く推奨する
  • 格子演算に対するサイドチャネル攻撃(タイミング、電力解析)には慎重な実装が必要。定数時間アルゴリズムが不可欠
  • 格子ベースアルゴリズムと古典的アルゴリズムを不適切に混合すると、予期せぬ脆弱性を持つハイブリッドシステムが作成される可能性がある

よくある質問

誤差付き学習 (LWE) 問題とは何か?

LWEは、有限体上のノイズのある線形方程式が与えられる計算問題である。a・x + e (mod q) の形式の方程式が与えられ、ここでaはランダム、xは秘密、eは小さなノイズであり、eを知らずにxを復元することは計算上困難である。

なぜ格子ベースの鍵はRSAの鍵よりも大きいのか?

格子基底とその基底をエンコードする行列は、単一の合成数よりも多くの情報を含んでいる。格子基底を暗号学的にエンコードするにはより多くのビットが必要だが、最近のスキームでは表現が最適化されている。

格子問題は量子耐性があるか?

SVPやLWEのような格子問題に対して、古典的アルゴリズムよりも高速な量子アルゴリズムは知られていないが、これは活発な研究分野である。格子問題の困難性は、量子コンピュータでも生き残ると推測されている。

格子暗号に関するNISTの推奨事項は何か?

NISTは、FIPS 203およびFIPS 204において、暗号化のためのML-KEM(モジュール格子ベース鍵カプセル化メカニズム)および署名のためのML-DSA(モジュール格子ベースデジタル署名アルゴリズム)を主要なポスト量子アルゴリズムとして標準化した。

今日、格子暗号を使用できるか?

はい。多くの現代の暗号ライブラリは、NIST標準化格子アルゴリズムをサポートしている。機密性の高いデータを長期間保持する必要がある組織は、移行計画を開始すべきである。

関連する手法

参考文献

  1. Ajtai, M. (1996). Generating hard instances of the short basis problem. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pp. 99-108.

    出版物の文献を開く
    コピーしました。
  2. Regev, O. (2005). On lattices, learning with errors, hard instances, and public key cryptography. In Proceedings of STOC 2005, pp. 84-93.

    出版物の文献を開く
    コピーしました。