過去・現在・未来

【 図形としてのラティス、数学的対象としてのラティス 】 ラティスとは、「格子」のことです。 ただ、格子というと、僕は、格子戸や障子の桟をイメージしてしまうのですが、ラティスというのは、空間上に規則的に格子状に配置された「点の集合」のことです。点と点を結ぶものは、ラティスには含まれません。 問題は、この図形（と言っても、点の集まりですが）が、とても規則正しく感じられることです。今回、ラティスの例として最初に取り上げたものは、単純なもので、その規則性は、座標を入れれば、x座標もy座標も整数の値だけを取ることによっています。ただ、全てのラティスが整数値の座標を取るわけではありません。 ここでは、二つのベクトルb1とb2の整係数の線型結合で表される点の集まりとして、ラティスを捉える見方を紹介しています。座標が整数になることではなく、二つのベクトルの整数倍の和が、ラティスを構成します。ここでも、ベクトルの係数として、二つの整数が登場します。 こうした、図形上のラティスの点の集合全体を生成できるベクトルを、ラティスの「基底」と呼びます。 図形としてラティスが与えられたとしても、実は、その基底は一種類とは限りません。ただ、基底が与えられれば、そのラティスは一意に決定されます。 図形として簡単に把握できるのは、二次元か三次元までだと思います。時間を入れて四次元までは頑張ればいけるかも。ただ、10次元と11次元の違いは、物理学的に意味があると言われても、直感には響きません。 その上、暗号理論で使われるラティスは、RSA暗号のキーの長さと同じくらいの 512とか1024とかの次元を持ちます。こうした次元では、図形としてラティスを把握するのは不可能です。 そういう時には、数学を使います。ですので、ラティスを図形としてではなく、数学的対象として捉えること、ラティスの数学的特徴づけを理解することは、とても大事です。 ただ、面白いことがわかります。 ラティス暗号の説明に、512次元の図形を使う人はいません。 それは、二次元のラティス、要するに紙の上で書かれる図形としてのラティスが、高次元の数学的対象としてのラティスを理解するのに十分な情報を与えてくれるからです。 図形に対する直観は大事なものです。に次元のラティスはわかりやすいものです。そのうえ、ラティスの数学の基礎は、簡単な線形代数です。

【 Regev が示したこと (2)  -- Regevの証明概要】 ここでは、RegevのLWE問題のラティス問題への還元の証明を見ていこう。 具体的には、LWE問題のSVP問題への還元を見ていく。 基本的なアプローチとしては、ラティスL とそのdual ラティス𝐿^∗の双方を考えることと、DGS – Digital Gaussian Sampling という手法をとることに特徴がある。   --------------------- 動画「Regevの証明概要」を公開しました。ご利用ください。 https://youtu.be/KFrpKu4h448?list=PLQIrJ0f9gMcPtw-6OwIOO2rFKu_A-7OfF この動画のpdf は、こちらからアクセスできます。 https://drive.google.com/file/d/1F7SwORnfZvUbefWli-Q3gxQKnZ-MV4-t/view?usp=sharing セミナーの申し込み受付始めました。申し込みはこちらからお願いします。 https://cipher3.peatix.com/view 「ラティス暗号入門」のまとめページはこちらです。 https://www.marulabo.net/docs/cipher3/ blog:「Regev が示したこと (2) -- Regevの証明概要」 https://maruyama097.blogspot.com/2022/09/regev-2-regev.html 「LWE暗号の対量子耐性」についての連続投稿は、こちらのblogからアクセスできます。　 　●「Shorのアルゴリズムの秘密」 https://maruyama097.blogspot.com/2022/09/shor.html 　●「Shorのアルゴリズムの秘密の秘密」 https://maruyama097.blogspot.com/2022/09/shor_045224329.html 　●「Hidden Subgroup Problem」 https://maruyama097.blogspot.com/2022/09/hidden-subgroup-problem.html 　●「量子陣営の困惑」 https://maruyama097.blogspot.com

【 Regev が示したこと (1) 】 2005年の論文で、Regevが示したのは、LWE( Learning with Errors )問題を解くことの難しさを、Lattice問題を解くことの難しさに「還元」できるということだった。　 LWE問題を解くのは難しい。同様に、Lattice問題（例えば SVP「最短ベクトル」問題や、CVP「最近ベクトル」問題）も解くのは難しい。ただ、二つの難しい問題があるからといって、その二つの「難しさ」に関係があるとは限らない。 Regevは、次のように考える。 「LWE問題とCVP問題が解けたとしよう。そう仮定すると、二つを結びつけるものが見えてこないか？」 「ちょっと待って。解けてもいない問題を解けたことにして、いいの？」 ま、でもこれは大したことではない。実際には解けていない問題Pに、それを瞬時に解くアルゴリズムを想定することを、Pの「オラクル」を考えるという。文字通り「神託」を仮定するのだ。それは、お互いの関係がよくわかっていない複雑性の関係を考えるための、複雑性理論の常套手段だ。 gitalもちろん、LWE問題とCVP問題の「オラクル」を仮定しても、それだけでは両者の関係が見えてくるわけではない。 Regevがとったアプローチには、二つ特徴がある。 一つは、ラティスLの中だけで考えるのではなく、その双対ラティスL* も一緒に考えることだ。ラティスLでの議論は双対ラティスL* 上の議論に翻訳される。逆に、双対ラティスL*上の議論は、ラティスL上の議論に翻訳される。 こうして彼の推論は、ラティスLと双対ラティスL* の間を行ったり来たりする。といっても、それは行き当たりばったりではなく、L -> L* -> L -> L* -> ... -> L というふうに、最後には、Lの議論に戻る。 もうひとつの特徴は、ラティスL上の「正規分布」から、何度もデータをサンプリングしてそれを利用することだ。これを、Digital Gaussian Sampling -- DGS という。"Gaussian"というのは「ガウスの正規分布」という意味だ。 LWE( Learning with Errors )問題というのは、公開キーのデータAを既知として、B = A^Ts + e という形のデー

【 浅海ゼミ 第15回の講演ビデオと講演資料公開しました 】 浅海ゼミ「クラウドアプリケーションのためのオブジェクト指向分析設計講座」第15回の講演ビデオと、講演資料を公開しました。 https://www.marulabo.net/docs/asami15/ 今回のテーマは 「分析」です。要求モデルから、分析モデルを作成する作業分野である分析について説明します。今回はユースケースからシステムの概観を抽出するシナリオ分析を取り上げます。　 次回にコンポーネントとシステム・アーキテクチャとして具体化したモデルを作成するコンポーネント分析を取り上げる予定です。　 講演ビデオ  https://youtu.be/GZQQCcDO4zg は、次のような構成になっています。 　00:00:00 開始 　00:01:10 分析の位置づけ 　00:10:26 分析と設計 　00:17:37 シナリオ分析 　00:30:59 シナリオ分析の実践 　00:36:52 まとめ 資料は、次からアクセスできます。 MaruLabo:   https://www.marulabo.net/docs/asami15/ SlideShare: https://www.slideshare.net/asami224/15-253173625 浅海ゼミの講座の全体構成はこちらを参照ください。 https://www.marulabo.net/docs/asami/

【 量子陣営の困惑 】 2008年に発表された Vaziraniらの、次の論文は、興味深いものだ。　 C.Moore, A.Russel, U.Vazirani . A classical one-way function to confound quantum adversaries, 2008  https://arxiv.org/pdf/quant-ph/0701115.pdf タイトルは、「量子論の敵手を困惑させる古典論的一方向関数」というもの。　 この間、暗号の話をしてきたのだが、基本的には、古典的な暗号理論に、量子コンピューターの脅威が攻撃を仕掛けているといった構図のものが多かったのだが、ここでも量子コンピュータの陣営は、古典論に対する「敵・対抗相手」として捉えられている。この「敵手」はVaziraniたち自身のことである。ただ、この「敵手」は、「困惑」しているという。 Vaziriani は、量子コンピューターが多項式時間で計算可能な量子複雑性のクラスを発見し、それを初めて「BQP」として定義した人だ。 「量子計算とさらには計算複雑性理論に基づく暗号の大きな可能性は、現在の技術でも実装可能でかつ量子コンピューターの攻撃にも安全な、暗号システムの研究を当面の課題として動機づけた。」 では、何に「困惑」しているのか？ 彼が扱っているのは、以前、Ajitaiの一方向関数として取り上げたものだ。彼は古典的に行列から代数的に定義されたこのAjitaiの一方向関数が、量子コンピュータによる攻撃に対して安全であることを示そうとする。 攻守、ところを変えているのである。 以前なら、古典的な一方向関数に対する量子攻撃は、離散対数問題なら、Shorのアルゴリズムで可能であった。ただ、Ajitai関数の場合、Hidden Subgroup 問題は、非可換群のHidden Group 問題になる。有限アーベル群のようにはうまくいかない。 Vazirianiはいう。「これらの結果は、離散対数に対する Shor のアルゴリズム とは異なり、Hidden Subgroup問題に基づく量子攻撃が機能する可能性は低いことを示唆している。」 すでに、2003年の論文 "Quantum Computation and Lattice Problems" https://

【 Hidden Subgroup Problem 】 Shorのアルゴリズムから、Hidden Subgroup Problem を説明してみよう。　 素因数分解のアルゴリズムとしてShorのアルゴリズムは、素数 n, a について a^(n-1) ≡ 1 (mod n) というフェルマーの小定理を素数判定に繰り返し利用している。フェルマーの小定理がなりたつことは、次のような例で確かめてみればいい。 2^3=8=3x2+2 ≡ 2 (mod 3) 2^5=32=5x6+2 ≡ 2 (mod 5) 2^7=128=7x18+2 ≡ 2 (mod 7) 2^11=2048 =11x186+2 ≡ 2 (mod 11) a^r ≡ 1 (mod n) なるrが存在する時、この最小のrを（nについての）aの周期（あるいは位数）という。 例えば、n = 15, a = 7 とすると、周期は4である。         7^0 = 1 (mod 15) 7^1 = 7 (mod 15) 7^2 = 4 (mod 15) 7^3 = 13 (mod 15)    7^4 = 1 (mod 15) 7^5 = 7 (mod 15) 7^6 = 4 (mod 15) 7^7 = 13 (mod 15) 7^8 = 1 (mod 15) 7^9 = 7 (mod 15) Shorのアルゴリズムでは、aの周期を求める時、量子コンピューターが呼び出されている。逆に言えば、Shorのアルゴリズムで量子コンピュータが使われているのは、その部分だけである。 足し算が定義されている整数の全体をGとする。Gは、足し算について群になる。今度は、Gの部分群（Gの部分集合で足し算について群になるもの）Kを考える。 このKについて、Gから有限集合Xの関数fを、次のように定義する。 Gの二つの要素g1,g2について、f(g1)=f(g2)となるのは、g1K=g2K となるものに限るものとする。Kは足し算についての部分群なので、g1K=g2K という条件は、g1+k1=g2+k2 というKの要素 k1, k2があるという条件に等しい。 Shorのアルゴリズムの量子コンピューター担当パートでの、「aの周期を求めよ」という問題なら、a^j ≡ 1

【 Shorのアルゴリズムの秘密の秘密 】 Shorのアルゴリズムは幸運だった。それは、量子アルゴリズムの古典アルゴリズムに対するに対する勝利の金字塔となった。　 不幸だったのは暗号陣営である。実際には、できてもいない技術に、強烈な逆風にさらされることになる。 それでは、このphaseの変化から2^n個の情報を取り出すというShorのアルゴリズムの方法は、どんな問題に対しても有効なのだろうか？ もしもそうだとしたら、量子コンピューターは普通のコンピューターに対して、どんな問題に対しても2^n倍の高速化を可能にすることになる。 残念ながら、そうはうまくいかないのだ。 量子アルゴリズムの専門家たちは、量子コンピュータによる高速化が可能になる問題には、あるパターンがあることに気づく。 その意味は、おいおい説明していくので、当面は意味不明と思うが、彼らが見つけ出した、パターンは、次のようなものだった。 　「有限アーベル群のHidden Subgroup Problemは 　　量子コンピューターで高速化可能である。」 先の投稿で、Shorのアルゴリズムの高速性という秘密について触れたのだが、Shorのアルゴリズムには、その裏にさらに秘密があったのだ。 すなわち、Shorのアルゴリズムが、高速なのは、それがこのパターンに当てはまるからであるという秘密が。 別の言い方をすると、Shorのアルゴリズムは、このパターンに属する問題に対する特殊なアルゴリズムで、量子コンピューターの一般的な能力を代表するものではないということになる。 次の投稿で、Hidden Subgroup Problemとはどんな問題なのかを、簡単に説明しようと思う。 ------------- セミナーの申し込み受付始めました。申し込みはこちらからお願いします。https://cipher3.peatix.com/view 「ラティス暗号入門」のまとめページはこちらです。この間の投稿は、こちらからもまとめて読めます。https://www.marulabo.net/docs/cipher3/