Zenn
😺

PQCを支える格子問題とその応用

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

なぜ、格子問題が重要なのか

格子問題という言葉を聞いたことはありますか？
「格子柄」や「格子状の模様」といったイメージを思い浮かべる方もいるかもしれません。

実はこの「格子」を数学的に扱う格子問題こそが、次世代の暗号技術を支える基盤となっています。
　
これまでの暗号は、素因数分解や楕円曲線といった数学的な難問を解きにくいことを安全性の根拠にしてきました。しかし、量子コンピュータの登場によって、これらの問題は短時間で解けてしまうと考えられており、従来の暗号は安全ではなくなるリスクを抱えています。

この脅威に対抗するために登場したのが、PQC（耐量子計算機暗号） です。
(PQCの概要については、こちらの記事で詳しく解説しています。)

2024年8月、NIST（アメリカ国立標準技術研究所）は次世代の暗号標準としてML-KEM、ML-DSA、SLH-DSAを選定しました。ML-KEM、ML-DSAは、数学的に難しい格子問題を採用し、安全性を保証しています。

したがって、ML-KEMやML-DSAの仕組みを正しく理解するには、その土台となる格子問題を知ることが欠かせません。この記事では、格子とは何か、そして格子問題が暗号技術にどのように活用されているのかを、分かりやすく解説していきます。

格子とは？

格子とは、簡単に言うと、「規則正しく並んだ点の集合」です。イメージとしては、結晶の原子の配置を思い浮かべるとわかりやすいと思います。

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

格子の定義

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)を基底とすると、全ての格子点は(a,b)(a,bは整数)と表せます。ここで基底を(-1,0)と(0,1)に変えても、生成される格子は全く同じです。

格子の種類

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

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

  2. q-ary格子
    これは、法(モジュロ)qの世界で定義される格子です。LWE問題、SIS問題といった格子暗号の根幹を理解するために不可欠な概念です。通常の格子が無限に広がるのに対し、q-ary格子はqの倍数で周期的に繰り返される構造を持ちます。すなわち、値は0からq-1で繰り返される構造です。

  3. イメージ格子とカーネル格子
    これらの格子は、ある行列Aを用いて定義される特殊な格子で、格子暗号の根幹をなすLWE問題とSIS問題を幾何学的な格子問題へと結びつける重要な役割を果たします。

    • イメージ格子：行列Aに整数ベクトルをかけた結果として得られる点の集合です。この格子は、LWE問題と深く関わっています。

      A \in Z_q^{m×n}を考えます。ここでZ_qは法qの整数環、つまりqで割ったあまりの世界(q-ary格子)です。
      行列Aのイメージ格子L(A)は、以下の式で定義されます。

      L(A) ：=　{y \in Z^m | ∃s \in Z^n s.t y≡As(mod q)}

      これは、行列Aの列ベクトル(n次元)を基底として、線形結合して得られるベクトル(m次元)を、法qで考えた集合です。
      この式は、別の見方もできます。イメージ格子は、行列Aの列ベクトルによって張られる通常の格子と、すべての成分がqの倍数である点の集合（つまり、q倍された標準格子Z_q^m）の和集合として捉えることもできます。

      L(A)　=　{As+qz : s \in Z^n,z \in Z^m}

      この式は、LWE問題における「秘密の格子点Asに、ノイズを加えた点」という構造を視覚的に理解する上で役立ちます。

    • カーネル格子：行列Aに非ゼロ整数ベクトルをかけたときに、結果がゼロベクトルになるようなベクトルの集合です。この格子は、SIS問題と深く関わっています。

      n x m 行列A \in Z_q^{n×m}を考えます。
      行列A^⊥のカーネル格子L(A)は、以下の式で定義されます。

      L^⊥(A) := {x \in Z^m | Ax=0(mod q)}

      これは、行列Aにかけたときに、法qの世界で結果がゼロベクトルになるような、すべての整数ベクトルxの集合(m次元)です。
      このカーネル格子の特徴として、長さが極端に短い非ゼロベクトルが存在する可能性があります。後で詳しく解説するSIS問題は、まさにこの「短いベクトル」を見つけることを目標としています。

    LWE問題、SIS問題、格子と問題の関係について、後ほど紹介しますが、ここでは「そういうもの」として飲み込んでください。

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

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

    元の格子Lが「密」(基底ベクトルが短い)であるほど、その双対格子L^⊥は「疎」(基底ベクトルが長い)になります。前途のカーネル格子とイメージ格子は、実は互いに双対な関係にあります。この性質は、LWEとSISの間の双対性を理解する上で非常に重要です。

格子の難しさ：格子問題の紹介

規則正しく並んだ点の集合が格子であると説明してきましたが、この単純に見える「格子」には非常に手強い数学的難問が隠されています。
格子点の中から特定の条件を満たす点を見つけること、これこそが、解くことが難しいとされる理由です。

その理由は、格子の基底にあります。
先ほど、同じ格子でも異なる基底があると述べましたが、基底には、「良い」(直交に近い)基底と、「悪い」(互いに非常に傾いた)基底が存在します。悪い基底で定義された格子は、一見すると不規則な点の集まりに見え、目的の点を見つけることが困難になります。

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

ここでは、格子暗号の安全性を支える代表的な格子問題について紹介します。

  • 代表的な格子問題（NP困難[1]）

    • SVP(最短ベクトル問題)：格子Lの基底の中で一番近い(原点に最も近い)非ゼロベクトルを見つける問題。
    • CVP(最近ベクトル問題)：格子点ではない、任意の目標点に最も近い格子点を見つける問題。
    • BDD(有界距離復号問題)：CVPの特殊なバージョンで、目標点が格子に非常に近いことを保証されている条件下のCVP。
    • SIVP(最短独立ベクトル問題)：SVPの拡張版で、格子の次元と同じm個の互いに線型独立な最短ベクトルを見つける問題。
    • USVP(一意最短ベクトル問題)：SVPの特殊ケースで、格子にただ一つだけ、非常に短いベクトルが存在する場合にそのベクトルを見つける問題。

  • 近似問題：NP困難を正確に解くのは難しいため、近似的に解く問題です。

    • r-SVP(エルミート最短ベクトル問題)：SVPの緩和版で、SVPが最短ベクトルを求めるのに対し、それのa倍(aは1より大きい)以下のベクトルを見つける問題。
    • GapSVP(判定版最短ベクトル問題)：長さの閾値が与えられたときに、最短ベクトルがその閾値より短いかどうかを判断する問題。

格子問題から暗号が生まれる：LWE問題とSIS問題

LWE問題(Learning With Errors)

LWE問題は、ノイズ付き連立方程式を解く問題として知られています。
秘密のベクトルs \in Z_q^nに対して、ランダムに生成された行列A \in Z_q^{m×n}と小さなノイズeを使って、ベクトルbを生成します。

b=As+e (mod q)

ここで、Z_q=Z/qZは、「整数環Zを法qで割った環」を意味します。
公開されているのはAとbだけです。この情報から、秘密のベクトルs(n次元)を特定することがLWE問題の目的です。ノイズeがなければ、簡単に解くことができてしまう連立方程式ですが、この小さなノイズが、問題を難しくしています。
ノイズeは離散ガウス分布に近いものからサンプリングされます。[2]

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

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

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

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

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

  • LWE問題と格子問題の関係

    なぜ、このLWE問題の困難さが、格子問題の難しさにつながるのでしょうか。

    その鍵は、LWE問題が、「任意の目標点に最も近い格子点を探す問題(CVP)」 として捉え直せるからです。

    先ほどのイメージ格子の定義を思い出してみましょう。 イメージ格子L(A)は、行列Aに整数ベクトルsをかけた結果Asで構成される、規則正しい点の集合でした。

    L(A)　=　{As+qz : s \in Z^n,z \in Z^m}

    この式のAsの部分は、まさに格子点を表しています。LWE問題で与えられるb=As+eという式は、この格子点Asに、小さなノイズeが加わったものとみなすことができます。つまり、bは、イメージ格子の点から少しずれた任意の目標点なのです。

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

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

SIS問題(Short Integer Solution)

SIS問題は、LWE問題と表裏一体の関係にある問題です。SIS問題は、短い整数解を見つける問題として知られています。
公開された行列Aに対して、以下の式を満たすような、長さが短い非ゼロの整数ベクトルxを見つけることがSIS問題の目的です。

Ax=0(mod q)

この問題も、一見すると簡単な連立方程式のように見えます。しかし、解が無数に存在する中で、特に「短い」という条件を加えることで、問題の難易度が飛躍的に上がります。

  • SIS問題と格子問題の関係

    なぜ、SIS問題は難しいのでしょうか。
    その鍵は、SIS問題が 「格子の最短ベクトルを見つける問題(SVP)」 として捉え直せるからです。
    先ほど、行列Aに整数ベクトルをかけてゼロになるような点の集合をカーネル格子と呼ぶことを説明しました。

    L^⊥(A) := {x \in Z^m | Ax=0(mod q)}

    この定義をSIS問題の式と比べると、その関係は明らかです、SIS問題で探しているベクトルxは、まさにカーネル格子に属する点なのです。
    そして、SIS問題の目的は、その中でも 「最も短い非ゼロベクトル」 を見つけることです。この「格子の最短ベクトルを見つける」という幾何学的な問題こそが、SVPです。
    したがって、SIS問題は、カーネル格子の中で最も短いベクトルを探す問題と等しく、このSVPが非常に難しいため、SIS問題も解くことが難しいと考えられています。

このように、LWE問題とSIS問題は、それぞれイメージ格子とカーネル格子という異なる種類の格子に変換できる、双対的な関係にあります。この両方の問題の困難さが、格子暗号の安全性を保証する土台となっているのです。

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

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

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

LWE問題の応用と安全性

LWE問題の応用

  • Ring-LWE問題：LWE問題はベクトルと行列を扱いますが、Ring-LWE問題は、係数が整数である多項式を扱います。
    「Ring」は 「環」を意味し、Ring-LWEは　「多項式環」R_q という特殊な数学的構造上で定義されます。

    • Ring-LWEの多項式環」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]の範囲の整数(Z_q)です。
      • また、x^n≡-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)を見つけるのがこの問題の目的です。

  • Module-LWE問題：Ring-LWEの多項式の世界を、LWEのベクトル・行列の世界に拡張したものです。Ring-LWEの効率性を保ちつつ、LWEの柔軟なセキュリティを兼ね備えるために開発されました。

    Module-LWEは、複数の多項式を要素 とするベクトルや行列を扱います。

    kはModule-LWEにおける多項式の数を表します。これは格子暗号プロトコルの重要なパラメータで、kの値が大きいほど、鍵のサイズは大きくなりますが、セキュリティレベルは高くなります。

    b(x)=A(x)s(x)+e(x)(mod q)
    A(x)：多項式を要素とする行列(k x k)
    s(x)：多項式を要素とする秘密ベクトル(k x 1)
    　　s(x)=(s_1(x),...,s_k(x))^T と表されます。
    b(x)：多項式を要素とする公開ベクトル(k x 1)
    e(x)：多項式を要素とするノイズベクトル(k x 1)

    各ベクトルや行列の要素は、Ring-LWEで登場した多項式環R_qの多項式です。

    このように、Module-LWEは、LWEの持つセキュリティ利点とRing-LWEの持つ効率的な利点を兼ね備えた、格子暗号の最先端といえます。
    NISTによって標準化されたML-KEMは、このModule-LWEの困難性を利用しているのは、まさにこのためです。

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

格子の難しさで説明したように、格子問題が解くのが難しいのは、格子を構成する基底が「悪い」(互いに非常に傾いた)場合に、不規則な点の集まりに見え、その幾何学的な構造を解読することが難しくなるからです。

そこで格子問題に挑むには、この「悪い」基底を「良い」(直交に近い)基底に変換する格子基底簡約アルゴリズムが用いられます。このアルゴリズムは、攻撃者が暗号を解読しようとする際に使われるだけでなく、格子暗号の安全性を評価するためにも不可欠です。もし、これらのアルゴリズムが効率的に格子問題を解いてしまうなら、その暗号は安全ではないと判断されるからです。

  • グラム・シュミット直交化
    格子基底簡約アルゴリズムを理解する上で、重要な基礎となるのがグラム・シュミット直交化です。

    これは、与えられた複数のベクトルを、長さが1で互いに直行する(垂直な)ベクトルの組に変換する手法です。
    与えられた線型独立なベクトル集合B={b_1​,b_2​,…,b_n​} \in R^mに対して、直行ベクトル集合 B^*={b^*_1​,b^*_2​,…,b^*_n​}を構成する手順は以下の通りです。

    1. b^*_1=b_1
    2. 二つ目以降のベクトル

      b^*_k=b_k−∑^{k−1}_{j=1}μ_{k,j}b^*_j (k=2,…,n)

    3. 係数μ_{k,j}

      μ_{k,j​}=⟨b_k​,b_j^∗​⟩/||b^*_j||​

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

  • LLLアルゴリズム
    LLLアルゴリズムは、格子基底簡約アルゴリズムの代表格です。与えられた格子の 「悪い」基底を、多項式時間で「それなりに良い」基底に変換します。

    具体的には、隣り合う基底ベクトルの交換と、グラム・シュミット直交化を用いて、以下の2つの条件を満たすように基底を調整します。

    • サイズ簡約（Size-reduced）: 基底ベクトル間の係数が小さくなるように調整します。
    • Lovász条件: 隣り合う基底ベクトルが一定の角度を保つようにします。

    これらの条件を満たすまで処理を繰り返すことで、元の基底よりも直交性が高く、短いベクトルを含む新しい基底を生成します。LLLは比較的速く実行でき、SVPやCVPを近似的に解くことができます。

  • BKZアルゴリズム
    BKZアルゴリズムは、LLLアルゴリズムをさらに強力にしたものです。LLLが隣り合う2つのベクトルだけを考慮するのに対し、BKZは基底ベクトルをいくつかの 「ブロック」 に分割し、そのブロック内で最適なベクトルを見つけ出そうとします。

    このブロック単位での最適化が、BKZの強さの鍵です。BKZは、ブロック内でSVPを解くことで、LLLよりも格段に「良い」基底を生成し、より短いベクトルを見つけることができます。

    計算量はLLLよりもはるかにかかりますが、その強力さから、現代の格子暗号の安全性を評価する際のベンチマークとして広く使われています。もし特定の格子暗号が、BKZアルゴリズムでも解読されないほど難しいと判断されれば、その暗号は安全だと考えられます。

格子に基づく暗号方式

今日では、LWE問題やSIS問題の困難性を利用したさまざまな暗号方式が提案されており、これらの方式はデータの機密性を確保するために格子問題の解きにくさを活用しています。

実際、NISTによって標準化された暗号アルゴリズムでは、ML-KEMがModule-LWE問題の困難性、ML-DSAがModule-SIS問題の困難性を安全性の基盤としています。

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

ML-KEM暗号アルゴリズムの具体的な説明については、こちらの記事で詳しく解説しますが、ここではその土台となるLWE問題に基づく暗号アルゴリズム(Regev暗号[4])の一般的な流れを説明します。

  1. パラメータの準備
    まず、4つのパラメータを用意します。(採用する暗号アルゴリズムであらかじめ決まっています。)

    • n：格子の次元
    • m：基底の数
    • q：法
    • α：ノイズの大きさ
     qが大きい=>誤差が目立ちにくい
 qが小さい=>誤差が目立つ、効率的な計算が可能

 αが大きい=>誤差が大きい、LWE解きにくい
 αが小さい=>誤差が小さい、LWE解きやすい

  2. 秘密鍵の生成

    • ランダムにs \in Z^n_qを選びます。(n次元の列ベクトル)

  3. 公開鍵の生成

    1. ランダムにA \in Z^{m×n}_qを選びます。(m×n行列)
    2. e \in Z^mを離散ガウス分布からサンプリングします。
    3. b=As+e (mod q) を計算します
    4. そして、公開鍵(A,b)を生成します。

  4. 公開鍵で暗号化

    1. 平文 μ \in {0,1} (通常1ビット単位で暗号化)
    2. ランダムにx \in {0,1}^mを選びます。(m次元の列ベクトル)
    3. 暗号文を計算します。
    • u=A^Tx(mod q)(n次元の列ベクトル)
    • v=b^Tx+μ[q/2](mod q)(スカラー値)
      これにより、暗号文c=(u,v)が生成されます。

  5. 秘密鍵で復号化
    復号化は次の式で行います。

    v−⟨u,s⟩=b^T_x+μ⌊q/2​⌋−(A^Tx)^Ts (mod q)

    ここで(A^Tx)^Ts = x^TAs なので、

    v−⟨u,s⟩=x^Te+μ⌊q/2​⌋ (mod q)

    • x^Teは小さいため、μを正しく判定できます。
      • 0に近ければμ=0、
      • q/2に近ければμ=1です。

    ただし、誤差$x^Teが大きすぎると0と q/2 の中間（= 𝑞/4）を超えてしまい、復号に失敗する可能性があります。そのため、復号が正しく行われる条件は次の通りです：

    |x^T∣<q/4

おわりに

この記事では、一見難解に思える「格子」という概念が、量子コンピュータ時代における新しい暗号技術を支えていることを解説しました。

格子問題の解きにくさ、特にLWE問題、Ring-LWE問題やModule-LWE問題、SIS問題の困難性が、なぜ暗号の安全性の鍵となるのか、その背後にある数学的仕組みを少しでも理解していただけたなら幸いです。

また、他の記事では、この格子暗号の理論を基盤として開発された、NIST標準のML-KEMにも焦点を当てています。NTT（数論変換）など、効率的な計算を支える具体的なアルゴリズムについても掘り下げて解説しています。
ML-KEM：格子ベース暗号の理論と原理

脚注

  1. NP困難：Pが多項式時間内で解くことができる問題を指し、NPは解が与えられたら多項式時間内に正しさを検証できる問題を指します。NP困難とは、NPの中で最も難しい問題と同じか、それ以上に難しい問題を指します(NPに属する必要はない)。 ↩︎

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

  3. NTTについてはこちらの記事で解説しています。 ↩︎

  4. Regev暗号：2005年に提案された格子暗号の一種です。 ↩︎

Discussion