😺

格子問題とその基本問題

に公開
暗号
耐量子計算機暗号
pqc
格子問題
pqcアルゴリズム
idea

はじめに

現在広く利用されている暗号技術は、量子コンピュータの登場によって安全性が揺らぐ可能性があると指摘されています。この問題への解決策として二つのアプローチが注目を集めています。一つは、量子コンピュータでも解けない計算問題に基づいた「耐量子計算機暗号（PQC）」 です。もう一つは、量子力学の原理を利用する「量子暗号（QKDなど）」 です。

私はこれらの最先端の暗号技術に強い関心があり、独学で得た知識を体系的に整理するために、記事シリーズとしてまとめています。

本記事では、その中でも特に重要な基盤である格子問題に焦点を当てて整理していきます。
格子問題のイメージや直感的な理解から始め、暗号で重要となるLWE問題やSIS問題にも触れ、最終的にこれらがPQCアルゴリズム(例：ML-KEMやML-DSA)の土台としてどのように応用されているかを整理していきます。

なお、PQCやQKD、従来の暗号技術について詳しく知りたい方は、以下の記事もあわせてご覧ください。

格子とは

格子とは、直感的には「規則正しく並んだ点の集合」です。結晶の中で原子が一定の間隔で並んでいる様子に近いです。

数学的には、格子は以下のように定義されます。

格子の定義

n次元ユークリッド空間R^n上でm個の線型独立なベクトルb_1,b_2,...,b_m (m≦n)を使って、次のように表される点の集合を 格子L と定義します。

L = L(b_1,b_2,...,b_m) := {Σ_{i=1}^m a_ib_i :a_i \in Z, b_i \in B(n x m)}

これは、n次元 m個のベクトルb_iを、全て整数係数で線型結合して得られる全ての点の集合を意味します。この時、ベクトルb_1,b_2,...,b_mは、格子Lの基底と呼ばれます。
同じ格子でも基底の取り方(必ずm本)は一つではありません。

基底の定義
・線形独立である
・空間全体を表現できる
・空間の次元xと基底を構成するベクトルの数x'は同じ(x=x')

重要ポイント

  • 整数係数であること
    実数係数なら空間全体を埋め尽くしてしまいますが、整数に限定することで格子点が離散的に並びます。
  • 基底は一意ではない
    一つの格子でも、基底の取り方は複数存在します。
    例えば2次元の場合、(1,0),(0,1)を基底にしても、(-1,0),(0,1)を基底にしても、生成される格子は同じです。

格子の種類

格子にはいくつかの種類があり、それぞれ異なる役割を担っています。

  1. Z^n上の格子
    これは、最も基本的な格子です。全ての成分が整数であるn次元ベクトルで構成される、点の集合です。

  2. q-ary格子
    法(モジュロ)qの世界で定義される格子です。LWE問題、SIS問題など、格子暗号の中核を理解するために欠かせません。無限に広がる通常の格子とは異なり、qを法とした周期的な構造を持っています。

  3. 双対格子
    ある格子Lに対して、特別な関係を持つもう一つの格子を双対格子L^⊥ と呼びます。
    双対格子は、元の格子Lのベクトルと内積をとると、必ず整数になるようなベクトルの集合です。

    L^⊥={x \in R^n：<x,y> \in Z, ∀y \in L}

    元の格子Lが「密」(基底ベクトルが短い)であるほど、その双対格子L^⊥は「疎」(基底ベクトルが長い)になります。後述するカーネル格子とイメージ格子は双対な関係にあります。

格子問題

格子問題とは、格子上で定義される特定の計算問題を指します。これらの問題の多くは、古典コンピュータでは解くのが非常に難しい(NP困難であると信じられている)一方で、量子コンピュータでも効率的に解くことができないと考えられています。

格子問題には様々な種類がありますが、代表的なものをいくつか挙げます。

  1. 最短ベクトル問題(SVP：Shortest Vector Problem)
    • 問題：与えられた格子Lに対して、ゼロベクトル以外の最も短いベクトル(原点から最も近い格子点)を見つけ出す問題。
  2. 最近ベクトル問題(CVP:Closest Vevtor Problem)
    • 問題：与えられた格子Lと、格子上にない任意の点vに対して、vに最も近い格子点を見つけ出す問題。
  3. 近似最近ベクトル問題(Gap-CVP)
    • 問題：CVPの近似版で、最近ベクトルが特定の距離内にあるかどうかを判定する問題。

なぜ、格子問題が暗号に利用されるのか

格子には、非常に手強い数学的難問が隠されています。具体的には、格子点の中から特定の条件を満たす点を見つけることは、非常に難しいとされています。その鍵は、格子の基底にあります。

前述のように、同じ格子でも基底の取り方は複数存在しますが、基底には「良い」(直交に近い)ものと、「悪い」（互いに非常に傾いた）ものが存在します。悪い基底で定義された格子は、一見すると不規則な点の集まりに見え、目的の点を見つけることが極めて困難になります。

すなわち、この「悪い基底」で隠された、格子の持つ幾何学的な構造を解き明かすことこそが、格子問題の本質であり、その難しさの根源です。つまり、格子問題が解けることは、格子暗号の安全性が破られることを意味します。

LWE問題とSIS問題

LWE問題、SIS問題とは、格子問題(SVP,CVPなど)を「暗号で使いやすい計算問題」に落とし込んだ問題形式です。すなわち、格子問題の形のままでは暗号プロトコルで使いずらいため、入力・出力を「線形代数の形」にした問題です。

LWE問題(Learning With Errors、誤差付き学習)

LWE問題は、ノイズ（誤差）を含む線型方程式の連立方程式から、元の秘密の係数を解読する数学的な問題です。

秘密ベクトルs \in Z_q^nに対して、ランダムに生成された行列A \in Z_q^{m×n}と小さなノイズeを使って、ベクトルbを生成します。

b=As+e (mod q)

  • 秘密ベクトル：ランダムな整数ベクトル　 s \in \mathbb{Z}_q^n
  • 入力：(A,b)
    • A：ランダムな整数行列 A \in \mathbb{Z}_q^{m×n}
    • b：b=As+e (mod q)
  • 問題：与えられた(A,b)から、秘密ベクトルsを見つけ出すこと。

小さなノイズeは、問題の構造を崩し、単純な線形方程式の連立方程式から数学的に非常に難しい格子問題へと変形させます。ノイズeは離散ガウス分布に近いものからサンプリングされます[1]。

LWE問題の二つのバージョン

LWE問題の難しさを表す方法として、次の二つがよく使われます。

  • 探索LWE：公開されているAとbから、秘密ベクトルsを解く問題です。
  • 判定LWE：公開されているAとbが、「上のLWEの式で計算されたデータ」か「ランダムに生成されたデータ」かを判別する問題です。LWEの式で生成されたデータは、ランダムなデータと見分けがつかないことを安全性の基盤としています。

多くの格子暗号では、この判定LWEの困難さが安全性の根拠となります。もし攻撃者がLWEの出力をランダムなデータと区別できてしまうと、暗号文を「本物」と「偽物」とで区別できてしまい、暗号システムが破られる可能性があります。

したがって、LWE問題の「難しさ」を証明する際、この判定LWEの困難性が、探索LWEの困難性と同等である(またはより難しい)ことが、重要な理論的証明となっています。

LWE問題と格子問題の関係

前途のように、LWE問題は格子問題を暗号で使いやすいようにした問題形式です。実際に、LWE問題は 「任意の目標点に最も近い格子点を探す問題（CVP）」 として捉え直すことができます。

LWE問題の式b = As + eにおいて、この式の As の部分は、まさに格子点を表しています。そして、b はこの格子点 As に、小さなノイズ e が加わったものと見なせます。つまり、b は「イメージ格子上の点から少しずれた目標点」なのです。

LWE問題を解いて秘密の s を特定するということは、この目標点 b から、最も近い格子点 As を見つけ出すことにほかなりません。そして、この「任意の目標点に最も近い格子点を探す」という幾何学的な問題こそが、CVPなのです。

このように、LWE問題は単なる数学的な方程式の問題であると同時に、幾何学的な格子問題へと変換できるのです。そして、このCVPが非常に解くことが難しいとされています。

イメージ格子の役割

イメージ格子は、線形代数の形をしたLWE問題の難しさを、幾何学的な性質を持つCVPの難しさに結びつける役割を果たします。
これは、抽象的な線形代数の問題を、具体的な幾何学の問題として捉え直すための概念です。そして、LWE問題の安全性はCVPによって保証されています。

SIS問題(Short Integer Solution、短整数解問題)

SIS問題は、与えられた行列の零空間の中でゼロベクトルではない、かつ全ての要素が小さい（短い）短い整数解を見つける問題です。

計算した結果がゼロになる組み合わせを探すだけでなく、入力した整数の値が全て小さい(短い)という条件を満たす必要があります。この「短い」という制約によって、問題を難しくしています。

Ax=0 \pmod{q}

  • 入力：
    • 行列：A \in Z_q^{n×m}
    • 正の定数：\beta
  • 問題：
    • ゼロベクトルでない、短いベクトルx \in \mathbb{Z}^mで、以下の条件を満たすものを見つけ出すこと。
    • Ax = 0 \pmod{q}
    • ||x|| \leq \beta

計算した結果がゼロになる組み合わせを探すだけでなく、入力した整数の値が全て小さい(短い)という条件を満たす必要があります。この「短い」という制約によって、問題を難しくしています。

SIS問題と格子問題の関係

前途のように、SIS問題は、格子問題を暗号で利用しやすいように設計された問題です。実際に、 「与えられた格子において、ゼロベクトル以外で最も短いベクトルを探す問題（SVP）」 として捉えることができます。

SIS問題の式 Ax = 0 において、この式のAの列ベクトルを、整数係数 x で線形結合した結果がゼロになることを意味します。この条件を満たす x の中で、長さが短く、ゼロベクトルではないベクトルを見つけ出すことは、まさにSVPそのものなのです。

このようにSIS問題は、単なる数学的な方程式の問題であると同時に、幾何学的な格子問題へと変換できるのです。そして、このSVPが非常に解くことが難しいとされています。

カーネル格子の役割

カーネル格子は、線形代数の形をしたSIS問題の難しさを、幾何学的な性質を持つSVPの難しさに結びつける役割を果たします。
これは、抽象的な線形代数の問題を、具体的な幾何学の問題として捉え直すための概念です。そして、SIS問題の安全性はSVPによって保証されています。

LWE問題とSIS問題の関係

LWE問題とSIS問題は、互いに双対の関係にあります。この対称的な性質は、LWE問題は行列の行空間を扱う一方で、SIS問題は行列の零空間を扱うためです。この双対性を活用することで、暗号システムの設計が可能になります。例えば、LWE問題を暗号化に、SIS問題を復号に利用するなど、両者を組み合わせることでより効率的で安全なシステムを構築することができます。

それぞれの関係を整理すると次のような階層になります。

暗号アルゴリズム
 ├─ ML-KEM（KEM）
 └─ ML-DSA（署名）
        ↓ 採用する
数学的問題
 ├─ LWE問題
 └─ SIS問題
        ↓ 成り立つのは
格子の構造(翻訳機)
 ├─ イメージ格子（LWEと関連）
 └─ カーネル格子（SISと関連）
        ↓ 保証する
安全性(格子問題)
 ├─ CVP（最近点問題）
 └─ SVP（最短ベクトル問題）

数学的問題
 ├─ LWE問題
 │     └─ 安全性の根拠：CVP（最近点問題）、SVP（最短ベクトル問題）
 └─ SIS問題
       └─ 安全性の根拠：SVP（最短ベクトル問題）

LWE問題の応用と安全性

Ring-LWE問題

LWE問題がベクトルと行列を扱うのに対して、Ring-LWE問題は係数が整数の多項式を対象とします。「Ring(環)」という名前の通り、この問題は多項式環上で定義されます。

  • 多項式環R_qの定義
    まず、整数環Zを法qで割った環

    Z_q=Z/qZ

    を考えます。
    次に、多項式環Z_q[x]を作り、さらにz^n+1で割った剰余環をとることで次のように定義されます。

    R_q=Z_q[x]/(x^n+1)

    つまり、次数がn未満で、係数が0からq-1の範囲に収まる多項式が要素となります。
    この環では x^n \equiv -1 という関係が成り立つのが特徴です。

  • Ring-LWE問題の定義

    LWE問題と同様に、秘密の多項式s(x) \in R_qを仮定します。

    ランダムに生成された多項式a(x) \in R_qと小さなノイズの多項式e(x)を使って、次のように多項式b(x)を生成します。

    b(x)=a(x)s(x)+e(x)(mod q)

    公開されるのは a(x) と b(x) であり、この情報から秘密の多項式 s(x) を求めることが Ring-LWE問題の目的です。

Ring-LWEの意義と利点

Ring-LWEの最大の特徴は、LWEと同等の安全性を保ちながら、実用面で大幅に改善された点にあります。

  • 鍵サイズの削減

    LWEでは大きな行列 A が必要でしたが、Ring-LWEでは公開鍵として わずか1つの多項式 a(x) を提示するだけで済みます。
    これにより、鍵のサイズは数千〜数万分の1に縮小され、データ通信が格段に効率化されました。

  • 計算速度の向上

    Ring-LWEの演算の中心は「多項式の掛け算」です。これは、LWEの行列-ベクトル積よりもはるかに効率的であり、さらにNTT（数論変換）[2]を用いることで大幅に高速化されます。

    しかし、Ring-LWEの持つ特定の構造は、安全性をさらに高めるための課題も残していました。この課題を克服するために開発されたのが、次に説明するModule-LWEです。

Module-LWE問題

Ring-LWEの効率性とLWEの柔軟なセキュリティ性を組み合わせるために提案された問題です。
イメージとしては、Ring-LWEが「1つの多項式環」で表現していた世界を、LWEのような「ベクトル・行列の構造」に拡張したものです

  • k は、Module-LWEにおける「多項式の数」を表すパラメータです。値が大きいほどセキュリティは高まりますが、その分鍵サイズも大きくなります。

数式で表すと次のようになります：

b(x) = A(x)s(x) + e(x) \pmod q

  • A(x)：多項式を要素とする行列（k \times k）
  • s(x)：秘密ベクトル（k \times 1）、s(x)=(s_1(x),...,s_k(x))^T
  • b(x)：公開ベクトル（k \times 1）
  • e(x)：ノイズベクトル（k \times 1）

ここで扱う各要素は、Ring-LWEと同じく多項式環 R_q に属する多項式です。

Module-LWEの意義と利点
1. Ring-LWEと同等の効率性
計算の中心は多項式演算なので、鍵サイズや計算速度の面でRing-LWEと同等のメリットを持っています。
2. LWEに近い安全性
複数の多項式をベクトル・行列で扱う構造を持つため、単一の多項式環に依存するRing-LWEよりも堅牢とされます。

このようにModule-LWEは、効率性と安全性を両立した格子問題として位置づけられており、
NISTが標準化した ML-KEM も、このModule-LWEの困難性を基盤にしています。

なお、本記事では、格子問題の理解に焦点を当てているため、Module-LWEがML-KEMでどのように使用されているかを知りたい方は、こちらをご覧ください。

格子問題を解くアルゴリズム

前述の通り、格子問題が難しいのは、基底が「悪い」（互いに大きく傾いた）場合に、格子点の並びが不規則に見えてしまい、幾何学的な構造を把握しづらくなるためです。

そこで登場するのが、基底を「悪い」ものから「良い」（直交に近い）ものへ変換する 格子基底簡約アルゴリズム です。
これは攻撃者が暗号を解読しようとする際に用いられるだけでなく、暗号の安全性を評価する上でも不可欠です。もし効率的な簡約アルゴリズムが存在して格子問題を簡単に解けてしまうなら、その暗号は安全とは言えなくなってしまいます。

  • グラム・シュミット直交化

    基底簡約アルゴリズムを理解する上で欠かせない基礎が グラム・シュミット直交化 です。
    これは与えられた複数のベクトルを、互いに直交するベクトル集合へと変換する手法です。
    与えられた線形独立なベクトル集合 B={b_1, b_2,…,b_n} \in \mathbb{R}^m に対して、直交ベクトル集合B'={b'_1,b'_2,…,b'_n}を構成する手順は次の通りです：

    1. b'_1 = b_1

    2. k \geq 2 のとき

    b'_k = b_k - \sum^{k-1}_{j=1} \mu_{k,j} b'_j

    3.係数 \mu_{k,j} は内積で定義されます

    \mu_{k,j} = \frac{\langle b_k, b'_j \rangle}{||b'_j||}

代表的な基底簡約アルゴリズム

  1. LLLアルゴリズム
    LLLアルゴリズムは、最も有名な格子基底簡約アルゴリズムの一つです。
    与えられた「悪い」基底を、多項式時間で「ある程度良い」基底に変換することができます。
    具体的には、基底ベクトルの交換とグラム・シュミット直交化を繰り返し、以下の条件を満たすように調整します：
  • サイズ簡約（Size-reduced）：基底ベクトル間の係数が小さくなるように調整
  • Lovász条件：隣り合うベクトルが一定以上の角度を持つように調整
    　　
    この処理を繰り返すことで、直交性が高く、短いベクトルを含む新しい基底が得られます。
    LLLは計算が比較的速く、SVPやCVPを「近似的に」解くことが可能です。
  1. BKZアルゴリズム
    BKZ（Block Korkine-Zolotarev）は、LLLをさらに強力にしたアルゴリズムです。
    LLLが隣接する2本のベクトルしか考慮しないのに対し、BKZでは基底をいくつかの ブロック に分割し、そのブロック内で最適なベクトルを探索します。
    この「ブロック内でSVPを解く」アプローチにより、BKZはLLLよりも大幅に「良い」基底を生成でき、より短いベクトルを見つけられます。
    その分計算量は大きくなりますが、BKZは現代の格子暗号の安全性評価で最も重要なベンチマークとなっています。
    もしBKZを用いても解読できないほど困難であれば、その暗号は「十分に安全」と考えられます。

格子に基づく暗号方式

現在広く研究されている格子暗号は、LWE問題やSIS問題の困難性を安全性の基盤としています。格子問題が効率的に解けないことを利用して、データの機密性を確保する仕組みです。

実際、NISTが標準化した暗号アルゴリズムでは、

  • ML-KEM が Module-LWE問題 の困難性
  • ML-DSA が Module-SIS問題 の困難性

を基盤にしています。

暗号プロトコル
 ├─ 暗号方式（KEM, 署名, 共通鍵暗号）
 │     └─ 暗号アルゴリズム（AES, ML-KEM, ML-DSA など）
 │           └─ 数学的問題（素因数分解、格子問題 など）
 └─ 鍵交換の順序やハンドシェイクの流れ

ここでは、格子暗号の代表例として、LWE問題に基づくRegev暗号（2005年提案）の仕組みを紹介します。
ML-KEMなどの仕組みを理解する土台にもなる部分です。

  1. パラメータの準備

以下の4つのパラメータを用意します。（実際には暗号アルゴリズムごとにあらかじめ決められています。）

  • n：格子の次元
  • m：基底ベクトルの本数
  • q：法（大きな素数）
  • \alpha：ノイズの大きさ

  1. 秘密鍵の生成
    　　
    n次元の秘密ベクトル s \in \mathbb{Z}^n_q をランダムに選びます。

  2. 公開鍵の生成

    1. A \in \mathbb{Z}^{m \times n}_q をランダムに選ぶ
    2. ノイズベクトル e \in \mathbb{Z}^m を離散ガウス分布からサンプリング
    3. b = As + e \pmod q を計算
    4. 公開鍵 (A, b) を出力

  3. 公開鍵で暗号化
    　　
    平文 μ \in {0,1} を暗号化する流れは以下の通りです。

    1. ランダムに x \in {0,1}^m を選ぶ
    2. 暗号文 (u,v) を計算
    • u = A^T x \pmod q \quad (n次元ベクトル)
    • v = b^T x + μ \cdot \lfloor q/2 \rfloor \pmod q \quad (スカラー)

  4. 秘密鍵で復号
    　　
    復号は次の式を用います。

v−⟨u,s⟩=b^Tx+μ⌊q/2⌋−(A^Tx)^Ts \pmod q
　　
ここで (A^Tx)^Ts =x^TAs なので、
v−⟨u,s⟩=x^Te+μ⌊q/2⌋\pmod q
　　
となります。

  • x^T e は「小さい値」なので、μ を正しく判定できます。
    • 0 に近ければ μ=0
    • q/2 に近ければ μ=1

ただし、誤差 x^T e が大きすぎると、0 と q/2 の境界を越えてしまい、復号に失敗します。
そのため、復号が正しく成功する条件は：

∣x^Te∣<q/4

となります。

量子コンピュータの登場により、従来の暗号技術が将来的に危殆化すると指摘される中で、格子問題は「量子コンピュータでも効率的に解けない問題」として強い注目を集めています。実際に、数学的基盤として Module-LWE問題 を採用しているのが NIST標準化の ML-KEM です。より具体的な仕組みについて知りたい方は、ぜひこちらの記事もご覧ください。

参考文献:

  1. https://www.acompany.tech/privacytechlab/lattice-based-cryptography
脚注

  1. 完璧な離散ガウス分布を正確に生成するアルゴリズムの実装は難しいためです。 ↩︎

  2. NTTについてはこちらの記事をご覧ください。 ↩︎

Discussion