量子コンピュータ/耐量子暗号/量子暗号あたりの関係を整理しておく

Last updated at 2019-11-30Posted at 2019-11-30

このへん、結構誤解が多いので、整理しておきます。

#量子コンピュータで解ける暗号/解けない暗号

現状、アルゴリズムを実行できるハードウェアがない、という問題は後で話します。本節は、「理想的なハードウェアがあったとして」の話です。

RSAと楕円曲線暗号は破られる (Shorのアルゴリズム)

現状は量子コンピュータですべての暗号が(ビット数に対し多項式時間で)解けるわけではありません。
解けるか解けないかは、解くための量子アルゴリズムが見つかっているかどうかで決まります。

巷でよく聞く「量子コンピュータで暗号が解かれる」は、ほぼすべて「Shorのアルゴリズム」を指しています。また、Shorのアルゴリズムで解ける暗号は、有名なものでは、RSAと楕円曲線暗号だけと考えて特に差し支えありません。

たまに、「素因数分解しかできないから楕円曲線暗号は安全」と誤解されている方もいますが、離散対数問題も解けるため、楕円曲線暗号も解けます。¹,²

効果は限定的だが、より広汎的なGroverのアルゴリズム

なお、多項式時間にはなりませんが、Groverのアルゴリズムで計算量のオーダーが古典での総当りのルートになることは知られています。このアルゴリズムは、Shorのアルゴリズムと比べて、より広い用途に使えます。

Microsoft ResearchがAESをGroverのアルゴリズムで解いたときの計算量の予想をしていて³、それによると、回路の深さ(ざっくり、計算時間に相当します)は、以下のとおりです。

ビット数	回路深さ
AES-128	$1.16 \cdot 2^{81}$
AES-192	$1.33 \cdot 2^{113}$
AES-256	$1.57 \cdot 2^{145}$

ざっくり、Nビットに対し$O(2^{N/2})$と考えることができます。
この程度なら、ビット数を上げれば十分安全かと思いますが、ビット数の少ないものは危険になりうると考えられます。

ただし、以下に述べるように、暗号利用モードなどによっては危険になりうるので注意が必要です。

Simonのアルゴリズムなど、その他、暗号解読の危険性があるもの

AESであっても、一部の暗号利用モードでは、Simonのアルゴリズムにより解かれるという報告もあります。⁴,⁵

量子コンピュータだからって何でも解けるわけではありませんが、新たな攻撃方法として量子コンピュータによる攻撃が増えたと考えるべきです。

量子コンピュータのハードウェアの話

今あるハードウェアにはたくさんの課題があり、Googleの量子超越性を示した量子コンピュータをもってしても、暗号解読には全く使い物にならない状況です。

主にあるのは、エラーやノイズの問題です。

今の量子コンピュータは短時間(100マイクロ秒もないくらい)しか量子状態を保つことができません
量子状態を保っていられる間に計算が終わる必要があります。さすがにそこまでは速くなりません
また、ゲートをかけたとき(つまり計算したとき)のエラーレートも高いため、たくさんのゲートをかけた計算は、まず合いません

また、そもそも量子ビット数も足りません。(アルゴリズムによりますが、RSAならビット数の数倍、AESは³にありますが、AES-128で2,953量子ビットが必要)

これからの数年で、もしかしたら、

量子ビット数が数百ビット
量子誤り訂正で、1量子ビットないし2量子ビットを長時間保つ

などは、開発が進む可能性がありますが、量子誤り訂正ありで数百〜数千量子ビットを保つのは、到底数年では無理と言えるでしょう。(20年以内とか50年はかかるとか、いろんな予想がありますが、どれも、大した根拠はありません)

耐量子暗号

「耐量子暗号」あるいは「ポスト量子暗号」とは、RSAや楕円曲線暗号の代わりとなる、量子コンピュータでも解けない(と信じられている)暗号です。

**耐量子暗号は、通常のコンピュータ等でも使うことができる暗号化方式です。**量子コンピュータがなくても利用できます。

何種類か提案されていますが、格子暗号⁶などが有力です。2016年には、Chromeブラウザの開発者版(Canary)で、httpsで耐量子暗号を使えるようになっています。⁷

##耐量子暗号への移行の話
「暗号解読ができる量子コンピュータが当面は出来ないのなら、まだ耐量子暗号のことは考えなくていいのでは?」と思われた方もいるかもしれません。
ですが、RSAや楕円曲線暗号は既に多くの場面で広く利用されており、それらを置き換えるには長い年月がかかります。
そのため、米国NISTや日本国内でもCRYPTRECなど、各国の政府機関等は、既に移行に向けて動き始めています⁴,⁸

量子暗号

より正確な用語では「量子鍵配送」といいます。ざっくりというと、量子が複製不可能である、という性質を利用して、量子を送受信することで、送信者と受信者がランダムなビットを共有して、それをワンタイムパッド(一度しか使わない、使い捨ての暗号鍵)に使うのが量子暗号です。

理論上は盗聴不可能なことが示されている夢の暗号なのですが、送信者、受信者は、何らかの量子を送信あるいは受信する設備を持っている必要があります。
また、量子を通信するための経路も大変で、増幅器を噛ませない光ファイバーを用意するとか、人工衛星を経由して量子を送受信するとか、いずれにせよ、通常の通信よりも高コスト低スループットになります。

当面は、軍事などの特殊な用途に限られるのではないかと思われます。

まとめ

今の量子コンピュータ
- しょぼい。暗号解くの無理
しょぼくない量子コンピュータ
- いつ出るか分からないが、出たらヤバい
RSAと楕円曲線暗号
- しょぼくない量子コンピュータが出たら終わる
その他の暗号方式
- Groverで計算オーダーは減るので、鍵を伸ばすと良き
- 攻撃方法が増えることには注意が必要。暗号利用モードとか、そういうのにも注意
耐量子暗号
- 普通のコンピュータで使える、量子コンピュータに強い暗号
- 近い将来、RSAや楕円曲線暗号は耐量子暗号に移行する予定
量子暗号
- 大掛かりな設備が必要だけど、解読不可能な暗号

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up