ほうがんしに、たてにも よこにも 同じ はばで 点を うって いきます。この 点の ならびを「こうし」と 言います。

紙の 上に 星を 一つ かいて、「この 星に いちばん 近い 点は どれ？」と きかれたら、どうでしょう。目で 見れば、すぐ わかります。

ところが、たてと よこの 2つだけでは なく、点の 場所を あらわす 数が 何百こも ある 世界に なると、話が かわります。いちばん 近い 点を うまく さがす やり方は、見つかって いないと 考えられて います［3］。

あんごうは、この「さがすのが むずかしい」ことを かぎに します。かぎを もっている 人だけが、近い 点を すぐ 見つけられる しくみです。では、同じ 点の ならびを どう 見れば、かんたんに なるのでしょう。

方眼紙に、縦にも横にも同じ間隔で点を打つと、点の並びができます。数学では、こうした「整数の組み合わせで作れる点の集まり」を格子と呼びます［1］。

ここに星印を1つ打って、「星にいちばん近い格子点はどれか」と聞かれたら、2次元の方眼紙なら目で見て分かります。これは最近ベクトル問題（CVP）の、いちばん小さな例です［3］。もう一つ、原点以外でいちばん原点に近い点を探す最短ベクトル問題（SVP）もあります［1］。

ところが、方向が何百もある高次元の格子になると、近い点を見つける効率のよい方法は見つかっていません。SVPは、最短の長さの次元の多項式倍以内という「だいたいの答え」でも、効率よく解ける方法は知られておらず、難しいと考えられています［1］。

暗号はこの「探すのが難しい」問題を鍵に使います。ただ、ここで引っかかるのは、同じ格子なのに、人によっては簡単に探せることです。その差はどこから来るのでしょうか。

格子とは、基底ベクトルの整数係数の線形結合で表せる点すべての集まりである［1］。目標点が格子の外にあるとき、それにもっとも近い格子点を求める問題が最近ベクトル問題（CVP）で、原点以外でもっとも原点に近い点を求める問題が最短ベクトル問題（SVP）である［3］［1］。2次元の方眼紙では、どちらも目で見て答えが出る。

難しさが出るのは次元が大きくなったときだ。SVPは、答えの長さが最短の次元の多項式倍以内という近似解の形でも、効率よく解ける方法は知られておらず、難しいと考えられており、量子コンピューターを使っても同様とされる［1］。ただし、これは「解く方法が知られていない」という意味で、「絶対に解けない」と証明されたわけではない。

暗号が使いたいのは、この「大きな次元で近い点を探す」難しさである。ところが、同じ格子でも、人によって簡単に解けるという差が生まれる。次の章でその差の正体を見る。

点の ならびを つくる ものさしは、2本 あれば 足ります。「右へ 1」と「上へ 1」の 2本を 何回か つかうと、どの 点にも たどりつけます。

じつは、「右へ 3、上へ 1」と「右へ 2、上へ 1」の 2本でも、まったく 同じ 点の ならびが つくれます［1］。

たとえば 点（右へ 7、上へ 3）に いくには、はじめの ものさしなら「右へ 7、上へ 3」と すぐ 分かります。あとの ものさしだと、「3と 1の 2本を 1回、2と 1の 2本を 2回」と、少し めんどうです。

これは 2じげんの 話ですが、じげんが 大きくなると、この めんどうさが とても 大きく なります。こんな わるい ものさしを、短くて 直角に 近い ものさしに 作りなおす やり方も 研究されて いますが、じげんが 大きいと うまく いきません［2］。

だから「よい ものさしを 持って いる 人」と「わるい ものさしだけを 見せられた 人」で、むずかしさが ちがう のです。

格子を作る物差し（基底）は、1通りではありません。たとえば(1,0)と(0,1)でも、(3,1)と(2,1)でも、まったく同じ格子点の集まりができます。後者は、(1,0)を「(3,1)を1回、(2,1)を-1回」で、(0,1)を「(3,1)を-2回、(2,1)を3回」で作れるので確かめられます［1］。

点(7,3)を目指すなら、前者の基底では「7と3」で終わります。後者では「(3,1)を1回、(2,1)を2回」と、少し考える必要があります。2次元ならこの程度ですが、次元が何百にもなると、悪い基底で近い点を探すのは非常に難しくなります。

悪い基底から「短くて互いにほぼ直交する基底」を作る操作を、格子基底簡約といいます。1982年のLLLアルゴリズムは多項式時間で短い基底を見つけますが、最短の基底が得られる保証はなく、保証される近似の程度は次元に左右されます［2］。

この性質から、「よい基底を秘密に持つ人だけが近い点を速く探せる」という鍵の作り方が思いつきます。実際にこの発想でGGH暗号が作られましたが、1999年にNguyenが設計上の欠陥を発表しました［3］。では、物差しとは別の方法で、難しさを守ることはできないのでしょうか。

同じ格子を作る基底は一通りではない［1］。例として2次元で(1,0),(0,1)と(3,1),(2,1)を比べる。後者の行列式は3×1−1×2=1で、(1,0)=1·(3,1)−1·(2,1)、(0,1)=−2·(3,1)+3·(2,1)と書けるから、同じ格子になる。点(7,3)は前者では係数(7,3)がそのまま答えだが、後者では係数(1,2)を求めなければならない。

2次元ではこの差は小さいが、次元が高くなると、短くてほぼ直交する基底があるかどうかで、CVPを解く手間が大きく変わる。このため、与えられた基底から短くほぼ直交する基底を探す格子基底簡約が研究されてきた。1982年のLLL（Lenstra・Lenstra・Lovász）は多項式時間で短い基底を出すが、最短は保証されず、次元が大きいと近似の質が落ちる［2］。アルゴリズムの時間は一般に次元に対して指数以上になる［2］。

そこで、「良い基底を秘密にし、悪い基底を公開する」という鍵の作り方が考えられる。GGH暗号はCVPを土台にこの方向へ進んだが、1999年にNguyenが設計上の欠陥を発表した［3］。物差しを隠すだけの設計では守りきれなかったのである。では、別の隠し方はないのか。次の章で見る。

「ある 数を 3ばいすると 12」なら、ある 数は 4と すぐ 分かります。たくさんの しきを ならべた れんりつほうていしきでも、ときかたは 決まって います［6］。

そこで、しきの 答えに「ほんの 少しの ずれ」を こっそり まぜます。「12ぐらい」と しか 分からない しきを たくさん 見せられても、元の 数を もとめる 上手な やり方は、見つかって いません［6］。

かぎを もっている 人は、元の 数を 知って いるので、計算の 答えと「ずれは 小さい」と いう きまりを 合わせて、0か 1かを よみとれます［6］。

この 考え方を、2005ねんに レーゲフ（Oded Regev）という 人が「LWE」と 名づけて 発表しました［5］。ずれが あるから 安心、では ありません。ずれつきの 式を ときほぐす やり方が、見つかって いない だけです。

秘密の数の組sに行列Aを掛けた結果Gだけを見せられたら、連立方程式を解いてsを求められます。ところが、ここに小さなずれ（誤差e）を足したT=G+eを公開すると、各式に未知のずれが混ざり、同じ方法ではsが求まらなくなります［6］。

受け取り側は、秘密の鍵sを知っています。そのため、計算してもずれが小さいまま残るので、そこから0か1かを読み取れます［6］。鍵を持たない人にとっては、誤差つきの式から効率よくsを求める方法が見つかっていません。

この考え方を、2005年にOded RegevがLWE（Learning With Errors）問題として提案しました。さらに、LWEが、最悪の場合の格子問題（GapSVPやSIVP）と結びついていることを示しています。この結びつきは量子的な手続きを使うものです［5］。

「誤差があるから安全」なのではありません。誤差つきの連立方程式を解く効率のよい方法が、これまで見つかっていない、ということです。では、その「見つかっていない」にどれほど根拠があるのでしょうか。

連立方程式As=Gは、mod qで解けばsが求まる。ところが、小さな誤差eを足したT=G+eを公開すると、各式に未知のずれが混ざるため、同じ方法ではsが求まらない［6］。受け取り側は秘密鍵sで計算すると、小さい誤差の項を残したまま0か1かを判別できる［6］。

この「誤差つき連立方程式」を2005年にOded RegevがLWE（Learning With Errors）問題として提案し、最悪の場合の格子問題（GapSVP・SIVP）に帰着できることと、それに基づく公開鍵暗号を示した。帰着は量子的である。論文は2009年にJournal of the ACMに載った［5］。

注意したいのは、「誤差があるから安全」ではない点だ。正確には、誤差つきの連立方程式を効率よく解く方法が見つかっていない、という状態である［6］。この「見つかっていない」にどれほど根拠があるかを、次の章で見る。

あんごうの かぎは、「ときづらい 問題」で なければ いけません。しかも、たまたま むずかしい 問題が あるだけでは だめで、ふつうに つくった 問題も むずかしい ことが ひつようです。

1996ねんに、アイタイ（Miklós Ajtai）という 人が、「ふつうの 点の ならびで 短い 点が 見つかるなら、いちばん むずかしい 点の ならびの 問題も とける」と いう つながりを しめしました［4］。これが こうしあんごうの はじまりと 言われます。

また、2013ねんに、日本の NICTと 日立が、825じげんの 点の ならびで いちばん 短い 点を 見つける 問題を、ふつうの サーバーで 5.5日で とけたと 発表しました［9］。あんごうが やぶられた のでは ありません。かぎの じげんを どのくらい 大きくすれば よいかを 考える ざいりょうに なります。

暗号の鍵にする問題は、特別に難しい問題が1つあるだけでは足りません。ふつうに作った問題でも難しい必要があります。1996年にMiklós Ajtaiは、ランダムな格子で短いベクトルを見つけられるなら、最悪の場合の格子問題も解けてしまう、という関係を示しました。これが格子暗号の出発点とされています［4］。

難しさを試す実験もあります。2013年1月に、情報通信研究機構（NICT）と日立が、格子の最短ベクトル問題で、世界で初めて825次元の問題を市販の汎用サーバーで5.5日かけて解いたと発表しました［9］。これは暗号が破れたという話ではなく、「どの大きさの次元なら解ける時代か」を測る目安になる記録です。ここで紹介する記録は2013年の出来事に限ります。

素因数分解と離散対数には、量子コンピューターで効率よく解くアルゴリズムが知られています。一方、格子問題を効率よく解く量子アルゴリズムは、今のところ知られていません［3］。この違いが、格子が次の標準に選ばれた理由の一つです。

暗号に使う問題は、特定の難しい例が一つあるだけでは足りず、無作為に作った問題も難しい必要がある（平均ケース）。1996年にAjtaiは、ランダムな格子で短いベクトルを見つけられるなら最悪の場合の格子問題も解けてしまう、という最悪ケースから平均ケースへの帰着を示した。そのため、Ajtaiの結果が格子暗号の出発点とされる。ただしAjtai自身が最初の公開鍵暗号を作ったのではなく、公開鍵方式は1997年のAjtai–Dworkが最初である［4］。

実験の側からは、2013年1月にNICTと日立が、SVPで世界で初めて825次元の問題を市販の汎用サーバーで5.5日で解いたと発表した。この種の問題は格子暗号の安全性評価の根拠となる［9］。暗号が破れた記録ではなく、「どの次元までなら解ける」という実測であり、鍵に使う次元を決める目安になる。ここで述べるのは2013年時点の事実で、その後の記録の更新は扱わない。

量子コンピューターに関しては、素因数分解と離散対数には効率のよい量子アルゴリズムが知られているのに対し、格子問題を効率よく解く量子アルゴリズムは現時点で知られていない、とチュートリアルは述べる［3］。これは安全の証明ではなく「知られていない」であり、将来の研究で変わりうる。この状況で、標準化の議論が進んだ。

2024ねん 8月13日、アメリカの NISTという きかんが、りょうし コンピューターに 強い あんごうの きまりを 3つ 発表しました［7］。

そのうち 2つは、ここまで 見てきた 点の ならび（こうし）を つかった 方式です。「かぎを 安全に 分けあう 方式」と「しょめいの 方式」で、どちらも 点の ならびの むずかしさに よって います［7］。

のこる 1つは、ちがう 考え方の 方式です。

こうしの 方式は、りょうし コンピューターを もつ 相手にも 安全だと 考えられて います。でも「考えられて いる」は、「ぜったい」と いう 意味では ありません［8］。

ほうがんしの 小さな 点の ならびから 始まった 話が、ネットの かぎを まもる きまりにまで なりました。

2024年8月13日、アメリカ国立標準技術研究所（NIST）は、耐量子暗号の最初の標準3つを発表しました。FIPS 203のML-KEMは鍵共有、FIPS 204のML-DSAは署名、FIPS 205のSLH-DSAも署名です［7］。

ML-KEMはCRYSTALS-Kyber、ML-DSAはCRYSTALS-Dilithiumがもとになっていて、この2つが格子に基づく方式です。SLH-DSAはハッシュを使う別の考え方の方式です［7］。

ML-KEMの安全性は、前の章のLWEの仲間であるModule-LWE問題の難しさに依っています。量子コンピューターを持つ相手にも安全と信じられていて、ML-KEM-512・768・1024の3種類のうち、番号が大きいほど安全性が高く、性能は下がります［8］。「信じられている」は、証明されているという意味ではありません。

方眼紙の小さな点の並びから始まった考え方が、ネットの鍵を守る標準にまでなりました。その入口は、自分の手でも確かめられます。

NISTは2024年8月13日に最初の耐量子暗号の標準3つを発表した。FIPS 203（ML-KEM、鍵共有）、FIPS 204（ML-DSA、署名）、FIPS 205（SLH-DSA、署名）である［7］。ML-KEMはCRYSTALS-Kyber、ML-DSAはCRYSTALS-Dilithiumがもとで、この2つが格子に基づく。SLH-DSAはハッシュベースで、格子とは別の仮定に立つ［7］。

FIPS 203によれば、ML-KEMの安全性はModule Learning With Errors問題の難しさに依り、量子コンピューターを持つ相手に対しても安全と信じられている。パラメータ集合はML-KEM-512・768・1024の3つで、番号が大きいほど安全性は高く、性能は下がる［8］。つまり、前の章で見たLWEの考え方が、そのまま標準方式の土台になっている。

限界も整理しておく。「信じられている」は証明ではなく、格子問題を効率よく解く量子アルゴリズムが知られていないという現状の上に立つ［3］。本稿では、2013年に825次元の問題を解いたと発表された記録を紹介した［9］。

ほうがんしと えんぴつを 用意します。まず「右へ 1」「上へ 1」を ものさしに して、点（7、3）に たどりつく 行き方を かいて みます。ものさしは、右や 左、上や 下に すすむ 長さです。（「左へ」「下へ」も、右や上の 回数が マイナスに なったと 考えれば、使えます。）

つぎに「右へ 3、上へ 1」と「右へ 2、上へ 1」を ものさしに します。（7、3）に いくには、どう すれば いいでしょう。やって みると、ものさしを かえると、同じ 点でも 道が ちがうと 分かります。

こんどは 点（11、5）で ためして みましょう。はじめの ものさしと、あとの ものさしで、道は どれだけ ちがうでしょう。

じげんが 100も 1000も あったら、と 考えて みると、あんごうが どうして この ならびを つかうのか、すこし 見えて きます。

方眼紙と鉛筆があれば、物差しの違いを手で確かめられます。まず基底(1,0)と(0,1)で、点(7,3)と点(11,5)にたどりつく係数を書きます。次に(3,1)と(2,1)で、同じ点に至る係数を探します。(3,1)をa回、(2,1)をb回使うとして、xとyの式を2本立てて解きます。

すると(7,3)は(a,b)=(1,2)になります。(11,5)はどうなるでしょうか。aとbは整数になりますか。基底を替えても、点の集まりは同じだったことが確かめられます。

そのうえで、次元が3、4、…と増えたらどうなるかを考えてみてください。前の基底と後の基底の差が、暗号の鍵の難しさと結びつく様子が見えてきます。

手で確かめられる計算がある。基底(3,1),(2,1)で、点(11,5)の係数をa,bとすると3a+2b=11、a+b=5が成り立ち、a=1,b=4を得る。(7,3)ではa=1,b=2だった。基底(1,0),(0,1)では係数はそのまま点の座標である。基底変換の行列式が±1であれば、同じ格子を別の基底で表せる、という性質を使っている。

この小さな例を、次元を増やして考えると、悪い基底でCVPを解く手間が急に増える理由が見えてくる。実際の暗号では、この難しさをLWEのような形に組み込んでいる。

確かめの課題として、基底(3,1),(2,1)の行列式を計算し、±1になることを確認したうえで、点(7,3)と(11,5)以外にも(5,2)や(9,4)の係数a,bを自分で書き出してみるとよい。整数の組になれば、同じ格子の点だと分かる。