本記事はあくまで個人の見解であり、所属する会社・組織とは関係ありません

先日このようなePrintが投稿されました

Y. Chen: ``Quantum Algorithms for Lattice Problems'', ePrint Archive 2024/555, 2024.

その結果、「LWE問題が量子計算機によって解かれた！」という認識が一部で広まっている感覚があります

しかし、そのような事実は現時点ではなく、誤解が広まってほしくないなと思い、本記事を書いています

ですので、本記事に誤りがあった場合、執筆した意味がありませんので、誤字・脱字レベルでもご指摘ください
また，予告なしに内容の加筆や構成の変更を行うことがありますが，読みやすくするためのものですので，ご容赦ください

念のためですが、筆者は、ePrintの著者とは無関係です

ということでサマリーから↓

サマリー

そもそもこのePrintは本記事執筆時点では査読されていないため、主張内容の真偽のほどは現時点では不明（ePrintって？）
正確な主張内容は「ある制約を満たすLWE問題に対する多項式時間量子アルゴリズムを提案する」なので、一般の（全ての）LWE問題が解かれたわけではない（ePrintの主張概要）
実際、代表的な格子暗号方式である CRYSTALS-Kyber のインスタンスを用いたLWE問題は解かれていない（ePrintの主張詳細）
だけれども、このePrintの主張が正しい場合、他の格子暗号方式の安全性がどのようになるかは分からない（今後の展望）
準同型暗号の観点から、仮に、一般のLWE問題が簡単に解かれてしまったとしても、他にも耐量子性を持つ準同型暗号方式は既に提案されている（今後の展望）

ePrintって？

ePrintとは、ガチガチに査読された論文のことではありません

ePrint のトップページでは

The Cryptology ePrint Archive provides rapid access to recent research in cryptology.
Papers have been placed here by the authors and did not undergo any refereeing process other than verifying that the work seems to be within the scope of cryptology and meets some minimal acceptance criteria and publishing conditions.

と記載されており、要するに、掲載された論文の査読はほとんどしてないよ、ということです
（中には査読付きの国際学会にアクセプトされてから、ePrintとする場合もありますが、少なくとも今回はそうではありません）

実際、今回の ePrintのページを見ると，Publication info の項目が Preprint となっており、査読前であることが明示されています

まあ、中身を見るとめちゃくちゃ数式が書かれているし、なんか凄そう・・・のような感情もわかります

だからこそ1つのミスがあれば、誤った結論を導いている可能性もあるため、査読結果を待つほかありません

本記事の執筆中に O. Shmueli, ``A Note on Quantum Algorithms for Lattice Problems'', ePrint Archive 2024/583, 2024. という新しい ePrint が投稿されており、こちらは、今回の ePrint 中の誤りを指摘した内容となります
今後の動向にも期待ですね

格子暗号周辺の事前知識

キーワード（ご存知の方は飛ばしてください）

LWE 問題（Learning With Error）
格子暗号
耐量子性
準同型暗号

LWE問題・格子暗号

タイトルにもなっている「Lattice Problems」のうち、有名な問題として、LWE 問題というものがあります（他にもSVPと呼ばれる問題があり、後で出てきます）

これは、格子暗号という耐量子性を持つ暗号方式の安全性の根拠となっている問題のことです

本記事では便宜上、LWE問題を安全性の根拠としている暗号方式を格子暗号方式、と書くことにします

耐量子性

耐量子性とは、量子コンピュータ（以降、量子計算機で統一）を用いても、解読することのできない（と思われる）、という暗号方式の性質を表します

現在の情報社会のインフラで用いられる暗号技術において、例えば、RSA暗号と呼ばれる暗号方式がよく採用されているのですが、こちらの暗号方式は耐量子性を持ちません

一方で、近年、量子計算機の開発が進んでおり、大規模な量子計算機が実現すると、RSA暗号は危殆化してしまいます

そのようなスケールを持つ量子計算機が完成されるのはそんなにすぐではないと考えられているものの、
量子計算機が実現する前に、耐量子性を持つ暗号方式（耐量子計算機暗号・PQC）へと移行することが検討されています

また、どのような耐量子計算機暗号方式を用いるか、というのが最近のホットな話題で、アメリカ標準技術研究所（NIST）がその標準化活動を進めています

そして、格子暗号の CRYSTALS-Kyber という耐量子計算機暗号方式の標準化が既に決まっています

詳しいことは、CRYPTREC という日本の暗号技術に関するプロジェクトのうち、そちらの昨年のシンポジウムの資料や研究動向調査報告書を参照してください
（筆者は、こちらの組織とも無関係ですが、非常にわかりやすくまとまっていますので、ぜひ）

準同型暗号

（こちらのワードは直接ePrintとは関係しませんので、飛ばしていただいても）
他にも、格子暗号には準同型性、という性質があり、簡単にいうと、暗号文でも足し算や掛け算などの演算ができる、という性質があります

こちらについては調べたら色々出てきますので、記事を１つ貼り付ける程度で
(完全)準同型暗号の最前線1（入門編）

ePrintの主張概要

まず Abstract の1行目には

We show a polynomial time quantum algorithm for solving the learning with errors problem (LWE) with certain polynomial modulus-noise ratios.

と書かれており、

ある条件（with certain polynomial modulus-noise ratios の部分）のLWE問題を解くような多項式時間量子アルゴリズムを示す

と読めます

多項式時間アルゴリズムって何、と思うかもしれませんが、要するに、

ある条件（with certain polynomial modulus-noise ratios の部分）のLWE問題を量子的に簡単に解けることを示す

と読み替えてください

ある条件、の部分は次で詳しく触れることにして、論文の構成を見ると、

１章：イントロ
２章：前提知識
３章：主定理

となっており、特に３章に関して査読が必要だと思われます（ので、本記事では触れません）

ePrint 2024/583 でも３章について触れられていました

もう少し中身を見ると、１章の前説でLWE問題について触れており、1.1 が Main results ですので、そこでは、

Theorem 1.6(3.1) の概要

ある条件（1文目のやつ）を満たす、いくつかの変数を用いた LWE 問題を解くような多項式時間アルゴリズムが存在する

と書かれています

この Theorem 3.1 を証明するために、3章の議論が全て費やされているため、
3章のどこかが間違っていたら、この主定理は間違っているし、正しそうであれば、特定の条件を満たす LWE 問題は量子的に簡単に解けてしまう
という解釈ができます

つまり、イントロを見ても、主定理を見ても、全ての LWE 問題が量子的に解けた、とは書かれていないことが分かります

ePrintの主張詳細

とすると、

その特定の条件ってどのぐらいきついの？
既存の格子暗号方式は大丈夫そうなの？

と考えるのは自然で、実は、1.1 の Corollary 1.7 の後に続きが書かれてあります

現状の格子暗号方式に対して

まだCRYSTALS-Kyber を破ることはできていない、と書かれています

それがどのようなロジックに基づいているかというと（5ページの Let us の段落の上から3-5行目、若干翻訳入れています），

例えば、CRYSTALS-Kyber では、エラーの項が小さい定数範囲から選ばれており、modulus は $q = 3329$，次元は $n \in$ {$256 \cdot 3, 256 \cdot 4, 256 \cdot 5$} であり，$q$ は $n$ にほぼ比例するとみなせる
我々のアルゴリズムでは，$\alpha q$ を定数とすると、$q$ は少なくとも $n^2$ に比例するときに適用するので、まだCRYSTALS-Kyber を破ることはできていない

もう少し詳しく、$n$ の値を十分大きくしたとき、$q$ は $n^2 \log(n^2)$ に比例する、もしくは、それ以上で抑えられる、と読めます
$O(\cdot)$ と $\tilde{O}(\cdot)$ は異なるのですが、本記事では同一視します
（詳しくは、Landau の記号、で参照してください）

大雑把には、
CRYSTALS-Kyber では、moudlus $q$ という変数が $n$ という変数に比例するようなインスタンス選択をしているが、
今回のアルゴリズムの条件では $q$ が少なくとも $n^2$ で比例する場合になるため、アルゴリズムを適用する仮定を満たしていない
と解釈できます

なんか色々といきなり見慣れない変数が出てきましたので、ここで特定の条件、とやらを見ていきます

特定の条件（moduls-noise ratio）を詳しく見る

まずは LWE 問題がどのように定式化されるのかを確認します

Definition 1.4(LWE 問題)

$n, m, q$ を正整数とする．$s = (s_1, \ldots, s_n) \in (\mathbb{Z} / q \mathbb{Z})^n$ とし，各 $s_i$ はある分布 $DistS$ からサンプルされたものとする．
$n, m, q, DistS$ と $\mathbb{Z} / q \mathbb{Z}$ 上のある分布 $DistE$ による探索 LWE 問題とは，$1 \leq i \leq m$ に対して，$a_i$ を $(\mathbb{Z} / q \mathbb{Z})^n$ からランダムに取り，$e_i$ を $DistE$ からサンプルした際に，$(a_i, \langle s, a_i \rangle + e_i \ (\mathrm{mod} \ q))$ から $s$ を求める問題のこと．

$\mathbb{Z} / q \mathbb{Z}$ は0以上$q - 1$以下の整数全体の集合と思ってください
$a_i = (a_{i, 1}, \ldots, a_{i, n}) \in (\mathbb{Z} / q \mathbb{Z})^n$ とすると，$\langle a_i, s \rangle = \sum_{j = 1}^n s_j a_{i, j}$ のことです

定義では、分布 $DistS, DistE$ と書かれていますが、
$DistS$ : $(\mathbb{Z} / q \mathbb{Z})^n$ 上の一様分布
$DistE$ : $\alpha \in (0, 1)$ なる実数を用いて，平均0，標準偏差 $\alpha q / \sqrt{2 \pi}$ による $\mathbb{Z}$ 上の正規分布
がよく用いられます

これらの分布を用いるとき、LWE問題の難しさを決定する変数は、$n, m, q, \alpha$ の4つであり、
これらのインスタンスをどのように決定するか、がメインで考えることになります

先ほどの CRYSTALS-Kyber への主張に戻ると、$e_i$ が小さい定数範囲から選ばれる、つまり、標準偏差 $\alpha q / \sqrt{2 \pi}$ が小さい、ということを主張しています
また、$\sqrt{2 \pi}$ は定数なので、$\alpha q$ は定数になる、と分かります

このことは、$q$ の値が大きければ、それに対応して $\alpha$ の値も同じぐらいの割合で小さくなる、ことを表します
実際、5ページの Theorem 1.6 の後に書かれている、LWE問題の最悪ケースとして、$q$ は $n^4$ に比例するため、$\alpha$ は $n^{- 3.5}$ に比例する場合を考えています

まとめると、特定の条件である modulus-noise ratio とは $\alpha q$ のことであり、$q$ や $\alpha$ は $n^k$ （$k$は何らかの実数）に関する多項式で表せる、ということになります

この $k$ という値がどのように決まるかは、アルゴリズムの性能に関わりますし、それは３章を読まないと分からない話かなと思っています

今後の展望

ここまで色々書いてきましたが、そんなにすぐに悲観する話でもなければ、楽観しすぎるような話でもありません

じゃあこのePrintの主張内容が正しければ、今後はどうなるの？という展望の一例を紹介します

以下は全てifの話です

まず、耐量子計算機暗号に関する観点ですが、本アルゴリズムを適用しても安全であるようなパラメタ選択がさまざまな暗号方式の開発者で再検討されるかと思います
Kyber 以外の既存の格子暗号方式（準同型ならCKKSとかTFHEとか）が、どこまで安全なのかも現時点ではよく分かりませんし・・・個人的には大丈夫そうという感覚はありますが・・・

そして、このアルゴリズムを改善する流れ及びLWE問題を多項式時間で解こうとする研究は一層活発になるかと思われます
ひょっとすると、もしかしたら、LWE問題を多項式時間で解くアルゴリズムが提案される可能性もあります

（実際、RSA 暗号の安全性の根拠になっている素因数分解の困難性（本当はその変種）も、1978年に提案されてから、1994年にShorのアルゴリズムという、多項式時間量子アルゴリズムが提案されましたし、
LWE 問題が2009年に提案されて、そこから現在15年経ったと思うと、同じような流れが来てるのかなと思えばそんな気もしたりしなかったりといった感想です）

符号ベース暗号・多変数多項式暗号・同種写像暗号、といった、格子暗号以外の耐量子計算機暗号の研究も進められておりますので、
LWE問題が解かれた場合でも、それらで代用されることになると考えられます

続いて、準同型暗号の観点から、耐量子性を満たす準同型暗号はもうないのか、と思われるかもしれませんが、実は符号ベース暗号でそのような完全準同型暗号方式が提案されています

R. Challa, V. Gunta: ``Towards the Construction of Reed-Muller Code Based Symmetric Key FHE'', Ingénierie des Systèmes d'Information, Vol.26, No.6, 2021.

実は過去に符号ベース準同型暗号に関する記事を書いているので、もしよろしければそちらも
符号ベース暗号を用いた準同型暗号の構成（前半）

こちらへ移行するかもしれませんし、もしかしたら、まだ考えもつかないような、新しい準同型暗号方式がこれから提案される可能性もあります

今後がどうなるかは楽しみ？ですね

まとめ

今回は ePrint 2024/555 について触れました

中身は確認できていないので、深いところまでは書けませんでしたが、概要は追えたかなと思います

~~最近は全然QiitaとかZennを書けなかったけど、これを機に復帰したいなぁ・・・（n回目）~~