일본에서 일하면서 회사 테크블로그에 글을 게시하고 있습니다.
부족한 일본어지만, 이전에 제 블로그에 투고한 글들을 정리하고
관련테마로 새롭게 조사한 내용도 있기에 번역기로 살펴보시면 좋을것 같습니다.
「目次」
- QKD (量子キー分配)
- PQC (量子耐性暗号)
- GGHで見る格子暗号化
量子コンピュータの活用でRSA暗号化が攻撃できることを知った時は
2010年の大学図書館からでした。
実際にRSA暗号化がネットワーク世界で持つ影響力を知った時は
その4年後、大学3年生のコンピュータ保安講義からでした。
そしてまた2年後の2016年からNIST(National Institute of Standards and
Technology / 米国国立標準技術研究所)が
IBM、Amazon、Google、MSなどのIT企業と一緒に
RSA暗号化体系の崩壊に備えて量子耐性暗号化の標準化を進んでいました。
最初に提案された82個のアルゴリズムから分析と評価を重ねて
最近の3ラウンドまで残ったアルゴリズムは7個、
そしてその中で格子暗号化に基盤したものが5つでした。
3ラウンドで複数の候補が選択され、
2024年まで最終選択されるアルゴリズムとして以後の標準化が進行されます。
量子耐性技術には
ハードウェア基盤の量子キー分配(Quantum Key Distribution、QKD)と
ソフトウェア基盤の量子耐性暗号(Post Quantum Cryptography、PQC)
がありました。
QKDとPQCの概念図
1. QKD (量子キー分配)
QKDは既存の通信チャネル以外に量子キー分配装置と量子チャンネルを築いて
光子などの量子の状態がワンタイムキーになります。
量子力学によって量子の状態をコピーすることは量子間の絡み状態を崩して
中間にそんな盗聴がある場合にすぐ盗聴者がいることが見つかります。
ここで量子の絡みとは量子重畳と共に量子の代表的な性質です。
一つの量子を割って2つの量子を作ると
2つの量子は絡んでいてどんなに遠い距離でも（干渉がない場合）
繋がっています。一つの量子を観測すると
1000km、10000km距離の双子の状態も
量子重畳からあの一つの状態まで同時に決定されるので
これで通信ができます。
ちなみに、特殊相対性理論によって宇宙のどんなものも
(物質だけではなく情報も含めて)
実量が0で最大速度(秒速30万キロメートル)が可能な光より
速いものはありえないです。
量子絡みでは3000万キロメートルに離れていても
すぐ通信できそうな仕組みに見えて
最初は特集相対性理論を違反することができたかと思われました。
「QKDで伝える情報は光より速いのか」という論難がありました。
しかし量子状態の決定は光より速いですが、
それで伝えられるものは情報ではなく、ただ量子生成に使われる難数で、
実際のデータも既存の通信ネットワークで電送されます。
そのため情報が光より速いことではありません。
QKD関連情報でよく見える国家は中国でした。
中国は私が高校生だった2000年代後半から
200kmほどの都市間量子キー分配に成功して
科学書でそれを使って暗号キーを作る記事もよく見ました。
エドワード・スノーデンさんの事件、アメリカの中国通信企業制裁を見ても
国家間の通信保安は大事なことなので量子暗号化技術を
その広い地域を守る盾だと判断したようでう。
もちろん矛も量子技術の量子コンピュータになりますね。
有線(光ケーブル)では32個の連絡点を活用して
2000kmの量子キー分配に成功しました。
連絡点間の平均距離は80kmほどで、速度は20～30kbpsでした。
ほとんど真空状態である宇宙空間を活用すると光ケーブルより安定的に
無線通信(レーザー)が可能です。
人工衛星量子通信でも中国が世界最初の量子通信衛星
「墨子号、Micius」を活用しました。
中国のペキンからオーストリアのウィーンまで7,600kmの距離で
QKDが成功しました。
地上連絡点たちが送ったレーザー信号を墨子号が反射させて
他の連絡点に送る原理です。
80kbitの量子暗号キーでペキンはウィーンまで5.34kBの墨子号の写真を、
ウィーンからは4.9kBのシュレーディンガー
(量子力学に寄与したオーストリアの物理学者)
の写真が伝えられました。
晴れた日と、正確な光軸整列が必要で
速度は1000kmで3kbps、600kmでは9kbpsでした。
ちなみに、日本は2018年から2027年まで量子技術を活用した
社会/経済的な目標達成のため「Q-LEAP」R&Dプログラムを運営しています。
2019年基準で量子コンピュータ特許件数はアメリカ(500件)のあとで2位(200件),
量子暗号特許件数は中国(450件)、アメリカ(250件)のあとで3位(200件)でした。
Toshibaは世界で一番速いQKD装置を作ったそうです。
やはり日本は科学的にベースになる技術は逃さないですね。
ここまでQKDの話でした。ご覧の通りQKDはハードウェア的に
大きいスーケルなので国家または大企業中心に進行されていました。
ところで格子暗号化などが含められている
PQCはソフトウェア的なアルゴリズムだけで量子コンピュータに対応できます。
２．PQC
量子耐性暗号(PQC)は
量子ハードウェア、量子ソフトウェアの発達と組合で
量子コンピュータの情報処理効用がディジタルコンピュータを超える時が来ても
(量子優位、[Quantum supremacy])
ネットワークに使える暗号化です。
RSAが量子コンピュータのため危機になった理由は
量子コンピュータに適応可能なショアアルゴリズムが1994年に
発明されたためで、カウンターパンチを食らわなかった
AES対称鍵暗号は既存AES－128、AES-192の代わりに
もっと大きい暗号キー基盤のAES－384を使うことだけで
一応量子コンピュータの性能脅威から安全です。
AESの状況に付け加えると、
1996年に発明されたLov GroverのGroverアルゴリズムが対称鍵暗号である
AESの敵になります。
Groverアルゴリズムは整列されなかったN個のデータの中で
特定のデータを探す量子アルゴリズムです。
ディジタルコンピュータでは非整列探索すると最大O(N)の検索回数が必要ですが
量子コンピュータでGroverアルゴリズムならO(√N)になります。
量的な問題なのでAESは一応暗号キーを増えることで
量子コンピュータから逃げました。
素因数分解の難しさに基盤するRSA、ブロックチェーン暗号化は
アルゴリズム的にショアのアルゴリズムが動作する量子コンピュータから
解体されます。
専門家たちは現在一番強力なブロックチェーン暗号化も
10～15年以内に量子コンピュータのため解体されると言っています。
(不思議にユーチューブで見た格子暗号化講義動画の大学教授、
企業の保安担当者もRSAの限界を2030年だと見ていました。)
量子コンピュータのため社会の保安ネットワークが崩れる日は
Q-dayという名称で言われました。
そして暗号化だけではなく量子コンピュータそのものが地震などの
自然災害の予測、材料工学などの発展にも使い道があるので
製造業基盤でITネットワーク依存度が高い日本、韓国のような国家なら
もっと重要な技術だと考えました。
私は10年前からこのような背景知識のため
素因数分解基盤のビットコインなどに目を閉じていましたが
何でしょうか、その上げ潮は。しばしば悲しいです..
３．GGHで見る格子暗号化
GGHはRSAのように開発者たちのイニシャルから付けられた格子暗号で
1995年に提案されました。(Goldreich–Goldwasser–Halevi)
現実的に使えられる最初の公開鍵基盤の格子暗号です。
今日には保安的に完全に崩れましたが
比較的にシンプルな仕組みを持っていて
格子がどのように暗号化に使えられるのかを見やすいです。
２次元と３次元の座標系
我々は幼い時から数学で座標系をよく見てきました。
2次元と３次元の座標系がよく見えて
４次元からは人間の頭としては想像ができなくて数学的にだけ表現できます。
ここで格子(Lattice)はその座標系にある点が規則的に反復されて
あの格子縞として配置される集合を言います。
そして格子を構成するその点を格子点(Lattice Point)だと言います。
２次元では2つの基底ベクトル(basis vector)で構成される格子空間
そのような格子ができると、格子点たちの間にある特定なパターンも
無限に反復されます。
そのパターンはベクトルとして基底ベクトル(Basis Vector)になります。
逆に言えば格子点はその基底ベクトルとして決定されます。
そういうことは結局この格子が基底ベクトルとして決定されますね。
基底ベクトルにはその格子空間を決定する情報があるので
格子暗号化でPrivateBasisVector、つまり秘密鍵になります。
(以下Privateベクトル)
N次元の格子座標系はN個の基底ベクトルで表現されます。
そして格子の基底になるベクトルは多様に構成できますので
２次元で作られる基底ベクトルも無数にあります。
この格子と連関された格子問題として
SVP(Shortest vector problem)
CVP(Closest vector problem)
などがあります。格子暗号化はこの格子問題を活用します。
GGHはCVP基盤で、Privateベクトルで作った
PublicBasisVector(以下Publicベクトル)と、NoiseVectorが公開鍵になります。
格子空間で一番短いベクトルを探すSVP問題(左側)
格子空間にはない任意のベクトルが与えられた時、
そのベクトルと一番近い格子空間のベクトルをさがすCVP問題(右側)
それでは格子を感じながらGGHを試して見ましょう。
ここでは２次元のGGHなので２個の基底ベクトルがあります。
ユーチューブでJeff Suzuki様の動画とWikipediaを参照しました。
＿Jeff Suzuki様のユーチューブGGH講義
＿WikipediaのGGH暗号化ページ
Aliceさんは秘密鍵として直交する基底ベクトルである
Privateベクトルとしてv1、v2を持っています。
v1 = (1, 45)
v2 = (45, -1)
「ベクトルの直交条件：v1・v2 = 0」
そしてこのPrivateベクトルを組み合って
Publicベクトルとしてw1、w2を作ります。
そのw1、w2はほぼ平行しています。
w1 = (226, 40) [ v1 * 1 + v2 * 5 ]
w2 = (1853, 319) [ v1 * 8 + v2 * 41 ]
「ベクトルの平行条件：w1・w2 = ±|w1||w2|、
ここでは431538 ≒ 430520」
Publicベクトルと共に公開鍵としてNoiseベクトルがあります。
Noiseベクトルはここでは[-10 <= (rx, ry) <= 10]の範囲で選びます。
ここでは-9と2を選びました。
r = (-9, 2)
Noiseベクトルの範囲の基準はBabai's rounding techniqueに従うそうです。
後に見ますが、暗号文を復号化する時に四捨五入が使われます。
その時Noiseベクトルが充分に小さくと平文だけを残して
Noiseベクトルの部分は無視できます。
その四捨五入のためPrivateベクトルは直交する必要がありました。
その基準を決めることがBabai's rounding techniqueですが、
ここでは格子暗号の流れだけを見るつもりです。
＿Babai's rounding technique関連PDF
さ、とうとうBobさんがAliceさんにメッセージを送ります。
送る平文は(35, 27)です。RSAのようにGGHの暗号化は
平文を公開鍵として暗号化します。
m = (35, 27)
「暗号化」
_1
平文とPublicベクトルの線形結合
35 * w1 + 27 * w2 = (57941, 10013)
_2
そこでNoiseベクトルを足します。
(57941, 10013) + (-9, 2) = (57932, 10015)
r
暗号化完了です。
BobさんはネットワークでAliceさんに
(57932, 10015)を送ります。
それではAliceさんは
「復号化」
_1
自分だけ知っているPrivateベクトルとして(a1, a2)を求めます。
a1 * (1, 45) + a2 * (45, -1) = (57932, 10015)
v1 v2
_2
a1は≈251.04、a2は≈1281.799なので
小数点を四捨五入したら(a1, a2)は(251, 1282)になります。
_3
Noiseベクトルの効果は四捨五入として消されました。
Privateベクトルとしてこの格子空間が元々どのような空間かを
知っているAliceさんは、(a1, a2)として
この格子空間にありえる、元々のClosest vectorを求められます。
251 * (1, 45) + 1282 * (45, -1) = (57941, 10013)
v1 v2
_4
NoiseベクトルがあったためBobさんが送った(57932, 10015)は
Aliceさんが持っている基底ベクトル(Privateベクトル)で作れない
この格子空間にありえないベクトルでした。
それが四捨五入のためこの格子空間にある
元々のBobさんのベクトル、
一番近くのベクトル(Closest vector)を探したことです。
それではこのベクトルで求める平文は、
m1 * (226, 40) + m2 * (1853, 319) = (57941, 10013)
w1 w2
(m1, m2) = (35, 27)、平文が求められました。
悪いこころのTrudyさんが
Bobさんが送った暗号化データである(57932, 10015)を覗き見たくて
Noiseベクトルの除去なしで四捨五入して復号化すると
ちょっと別の平文が出ます。
m1 * (226, 40) + m2 * (1853, 319) = (57932, 10015)
w1 w2
(m1, m2) = (38, 27)
今は原理を見るため２次元格子空間でGGHが進行されましたが
実使用には300次元までも使います。人間の頭では想像できなくても
数学的にはそのような格子空間でClosest vector problem問題で
暗号化することができます。
Noiseベクトルはここで400個の別のベクトルを作りました。
(-10～10範囲で2個の数にNoiseを与えました。[20*20=400])
(57941, 10013)
すなわち、TrudyさんがNoise問題を無くすためには
400回の試しが必要です。
ところでこれは2次元チュートリアルで、300次元でNoiseがあると
20^300 = 10^390個の候補ベクトルが生成されます。
そしてこのように深い次元の格子暗号化に対して
素因数分解、離散対数の既存の公開鍵暗号を解体させられる量子コンピュータも
まだ解体させる適当なソリューションがありません。
GGHは提案された近くで暗号攻撃が提案されました。
そこで350次元までは暗号攻撃で平文が復号化されました。
GGHが安全するためには400次元以上のパラメータが必要でした。
GGHの短所は持っている格子空間ほどの長い公開キーが必要なことです。
そこでGGHの提案者たちはGGHが完全に崩れたことを認めました。
そして1996年に提案されたNTRU格子暗号はGGHの特殊な形態で、
NTRUも近くで暗号攻撃が進行されて100次元まで平文が見つかりました。
その後に暗号攻撃の性能も、NTRU側の対応も多年間進行されて
格子暗号攻撃に対して安全なパラメータが研究されました。
その結果、NTRUは格子空間の次元が200次元以上で
格子のパターンがあの条件を満足すると現実的な攻撃が不可能だと
入れられました。
そしてNTRUはGGHとは違って、公開キーも一つのベクトルです。
今NISTで進行されているPQC標準化の最終候補7個で5つが格子暗号基盤で
その一つが25年間崩れなかったNTRUです。
