量子コンピューターが仮想通貨の安全性を脅かすのはいつなのか？

「量子コンピューターで仮想通貨はどう変わるの？」「仮想通貨の安全性は量子コンピューターに脅かされるの？」という疑問を持っている方は多くいるかと思います。

先日Googleが量子コンピューターの実証実験を成功させたというニュースが注目を集め、仮想通貨の安全性を疑う声も多くなってきたと思います。

そこで本記事では、量子コンピューターがビットコインに与える影響をわかりやすく説明します。

この記事を読んでいただければ、量子コンピューターが与えるビットコインへの影響をゼロから理解することができますよ。

「量子コンピューターでどのようにビットコインが安全でなくなるのか」また、「量子コンピューターが出てきたら仮想通貨産業はどのように変化していくのか」を知りたいという方は、是非最後まで読んでみてください!

量子コンピューター時代に向けて

量子コンピューターの台頭で、現在一般的に使われているRSA暗号や楕円曲線暗号などの現代暗号理論が安全ではなくなる(危殆化していく)ことが問題視されています。

アメリカ標準技術研究所(NIST)は、2030年までに現在普及している暗号方式を一変し、2031年から耐量子暗号技術に移行することを推奨しています。

ビットコインでも秘密鍵から公開鍵を生成する時に楕円曲線暗号が用いられており、ビットコイン界隈の方にとっても決して他人事ではないのです。

そのような現代の暗号技術を脅かす量子コンピューターの仕組みやアルゴリズムについて、世界動向も交えてお伝えします。

量子コンピューターとは？

量子コンピューターとはその名の通り、量子力学の原理により並列性を実現するコンピューターです。

従来のコンピューターは、0と1の2つの状態で情報を表現します。

電圧のオン・オフで、0か1のいずれかの状態に1ビットは定まります。これの膨大な繰り返しで、Youtubeで動画が観られたり美しい写真を保存できたりするのです。

このビットに代わり、量子ビットで情報を処理するのが量子コンピューターです。この量子ビットは従来のビットと異なり、0と1が同時に成立している状態(重ね合わせの原理)も考えることができます。

0の状態と1の状態が決定的ではなく、確率的に決まっているということです。

この原理の画期的な応用により、1度で扱える情報量が増えます。

コンピューターで取り扱う量子ビットの数がn個のとき、1度で処理できる情報量が2のn乗となります。

2量子ビットなら4つのデータが取り扱えるということです。

先日Googleが53量子ビットの運用実験に成功したニュースがありましたが、この量子コンピューターが1度に取り扱えるデータ量は2の53乗という巨大な桁数になります。

10の15乗以上なので、1の後に0が15個並ぶほど巨大な数字ということになります。

演算処理速度が速いスーパーコンピューターでも、構造上はどこまでいってもバイナリーの原理(0か1か)の繰り返しです。量子コンピューターの演算処理が、スーパーコンピューターのそれを上回ることが将来考えられます。

しかも、重ね合わせ状態を利用して量子コンピューターでしか実行できないアルゴリズムなどが考案された結果様々な問題を従来のコンピューターよりも効率的に解くことができます。

量子コンピューター時代に向けた世界動向

各国で様々な研究所やIT企業が、こぞって量子コンピューターの研究・開発に取り掛かっています。大きな企業では、GoogleやIBMなどの取り組みが顕著なようです。

量子コンピューターの研究・開発が徐々に開始されるようになったのは、1970年代末ごろからです。

1985年にドイッチュ(David Deutsch)が、量子コンピューターを用いた計算アルゴリズムを考案しました。1994年にはショアのアルゴリズム(Shor’s algorithm)が考案され、量子コンピューターで素因数分解を高速に行う方法論が発見されました。

理論研究に続いて、ハードウェア開発も1990年後期から2000年代に入り盛んに行われ、核磁気共鳴NRM、超伝導粒子などを用いた10から20量子ビットの量子コンピューターがすでに実現されています。

今後の計画では、Googleが72量子ビット、IBMが50量子ビットまで拡張させるようです。

世界の研究競争に対応して、標準的な暗号システムも変化していかなければいけません。

2016年からアメリカ標準技術研究所(NIST)が耐量子計算暗号へ移行する準備を始めました。日本でも、CRYPTOREC(Cryptography Research and Evaluation Committees)によって、電子政府推奨暗号の安全性評価などが行われています。

暗号方式は、その性質上、慎重に精査・評価をしなければいけません。我々の日常で使用される暗号に”穴”があっては大変なことになります。

そのため標準化には多くの時間と労力がかかります。そこで今は2030年からの移行に向けて世界の各機関が動いている状況です。

量子コンピューターが仮想通貨に与える影響

従来のコンピューターとはそもそもの構造が大きく異なる量子コンピューターですが、仮想通貨の脅威になることが予想されます。

ショアのアルゴリズムとグローバーのアルゴリズムによってビットコインの安全性が脅かされている状況です。

公開鍵から秘密鍵が割り出される？

ビットコインを保有している方ならばご自身の秘密鍵をお持ちでしょう。誰にも公開してはいけない、自分だけが知っているべきランダムな数字とアルファベットの羅列です。

公開鍵はこの秘密鍵から生成されるので、ビットコイン取引の安全性は公開鍵から秘密鍵を割り出されないことを根拠としています。

公開鍵は名前の通り公開して良い鍵です。なぜなら、現在ではその公開鍵からいくら頑張っても秘密鍵を知るすべがないからです。

(Mastering Bitcoin, Andreas M. Antonopoulos 図4-3から引用)

ビットコインプロトコルで秘密鍵から公開鍵を生成する暗号技術が、上記で触れた楕円曲線暗号です。画像にもあるように、秘密鍵から公開鍵を生成できても、公開鍵から秘密鍵を割り出すことはできないようになっています。

しかしこれは従来のコンピューターでの話であり、量子コンピューターと量子アルゴリズムを使えば解けてしまう時代がいずれ来ることが理論上わかっています。

ショアのアルゴリズム(Shor’s Algorithm)

それが、後になってショアのアルゴリズムと命名される量子アルゴリズムです。この計算手法は1994年に米国大学MITの応用数学科ピーター・ウィルソン・ショア教授(Dr.Peter Williston Shor)によって考案されました。

理論上、ショアのアルゴリズムによって、離散対数問題と素因数分解が高速で解けるようになります。現在最も普及しているRSA暗号と楕円曲線暗号は、それぞれ素因数分解と離散対数問題の計算困難性に支えらています。

実際、現在使われている2048ビットの大きさの数を素因数分解するには、スーパーコンピューターで30年ほどかかると言われています。

これほど強固な暗号理論を量子コンピューターは破る可能性があるのです。

また、扱うデータ量が増えてもさほど計算量が変わらないところもショアのアルゴリズムが突出している点です。ですから、扱うデータ量を増やすという対処法が通用しません。

これによりRSA暗号と楕円曲線暗号が危殆化を迎え、耐量子計算暗号へと移行しなければいけなくなります。

これは、ビットコインを保有する上でも重大な事実となります。

楕円曲線暗号が破られるということは、公開鍵から秘密鍵が割り出されてしまうことを意味するからです。

本来なら公開できるはずの公開鍵から誰にも教えてはならない秘密鍵がバレてしまい、保有するビットコインがウォレットから盗まれるなどの被害も考えられます。

グローバーのアルゴリズム(Grover’s algorithm)

もう一つ、総当たり攻撃に特化したアルゴリズムとしてグローバーのアルゴリズムがあります。

グローバーのアルゴリズムは、1996年にベル研究所の研究員であったロブ・グローバー氏(Lov Grover)によって考案された高速検索アルゴリズムです。

ここで「3つの数字の組み合わせのひとつが正解となる」ダイアル錠など、N個のデータの中から1つだけ正解を割り出す作業を考えてみましょう。

<0,0,0>から始めて<9,9,9>まで0から9の10つの数字を1つずつ試します。

この場合だと、10の3乗の1000通りの組み合わせがありますね。

N通りの場合数がある時、従来のやり方ならば最悪N通りをしらみつぶしに探る必要があります。

N-1個まで不運にも外れてN個目でやっと正解に行き着くのが最悪のケースです。平均的に考えてもN/2回の総当たりを仕掛ける必要があります。

しかしこのグローバーのアルゴリズムを使えば平均的にNの平方根程度の回数で正解にたどり着けるそうです。

100個の中から1つ選ぶのに今までなら50回平均して試さなければいけないところを10回程度で正解にたどり着けるのですから驚きです。

この効果はNが大きいほど顕著になります。Nが100万通りある場合、50万回試さなければいけないところを1000回まで抑えることができるからです。

グローバーのアルゴリズムの存在で、安全性が不安視されることも理解できますね。

ハッシュ値が衝突する？

このグローバーのアルゴリズムはハッシュ値の衝突問題に応用することができます。

通常のコンピューターでは、同一のハッシュ値を得る入力値を発見するためにはハッシュ値の取り得る総数の平方根回を試せば良いことが知られています。

例えば、任意の入力に対して3桁の数字を返すハッシュ値があったとします(実際はもっともっと大きな桁数です)。

これは1000通りの3桁数字が存在することになりますが、通常のコンピューターだと1000の平方根である31通りを調べれば同じハッシュ値のペアーを発見できます。

一方でグローバーのアルゴリズムを応用した量子アルゴリズムを用いることでさらに少ない試行回数で同一のハッシュ値を見つけることができます。

具体的には、ハッシュ値の取り得る組み合わせの3乗根、つまり「1000の3乗根 = 10通り」を調べれば衝突が見つかるということになります。

ただ、グローバーの応用アルゴリズムへの対策として、ハッシュ長を1.5倍にすれば現在の安全性を保つことができます。

実際、3桁を1.5倍にした4.5桁に桁数を増やしてやってみましょう。

全ての組み合わせは10の4.5乗で31622通りです。これにグローバーのアルゴリズムを適応すると3乗根を調べればいいので、31622通りの3乗根である31回を調べればいいことになります。これは従来のコンピューターでの安全性と同程度ということになり耐量子性が保たれます。

グローバーのアルゴリズムで起こり得るハッシュ値の衝突問題は、ショアのアルゴリズムと異なりハッシュ値の桁数を増やせば十分であるということがわかりますね。

よってポスト量子コンピューター時代に入った際は、現在推奨されているSHA-256からSHA-384に移行する必要があるようです。

今後の展望

ブロックチェーンのシステム上、ビットコインのプロトコルや規格に対して変更を加えることは難しいです。

その場合、楕円曲線暗号ではなく(格子暗号や多変数多項式暗号などの)耐量子計算機暗号をプロトコルとして備え、かつSHA-384と今よりも桁数が長いハッシュ関数を採用しているシステムがビットコインからハードフォークするか、全く新しいコインが作られるかの2通りが考えられます。

既存のコインの中には、Cardano、IOTA、NEOなど耐量子性を持ったものが存在します。

ただし、これからより一層量子コンピューターの理論・実証双方からの研究が盛んに行われることも予想されます。

これからの研究により、新たに効率的なアルゴリズムが開発されたり、量子コンピューターでしかなせない計算手法が編み出されたりすれば、今存在する耐量子仮想通貨の安全性が脅かされる可能性も十分にあるでしょう。

まとめ

以上、量子コンピューターが仮想通貨にどう影響するのかをお伝えしました。

しかし、いきなり明日からショアのアルゴリズムが用いられビットコインが盗まれるという被害は考えられません。

量子コンピューターで正しい値を算出することがそもそも現時点では困難だからです。

ですから、例えばショアのアルゴリズムを使って現在使用されている2の2048乗の桁数を解読するとなると、4050以上の量子ビットを扱えなければいけません。しかしグーグルが開発中の量子コンピューターの現目標は比べてたったの72量子ビットです。

その上、多くの量子ビットで実装し計算すれば大きな誤差が出るため、実用に向けてはエラー修正への研究も進めなければいけません。さらに、量子ビットを多く使用すると重ね合わせ状態が消えてしまう現象(デコヒーレンス)が起こってしまう問題もあります。

(国立研究開発法人　科学技術振興機構　研究開発戦略センター 科学技術未来戦略ワークショップ報告書から引用)

したがって、現状の暗号化標準が脅かされるまでにはまだ時間がかかり、早くて2030年手前と予想されています。

今後量子コンピューター技術の飛躍に関するニュースが出てきた場合は、それが達成した量子ビット数などをチェックできれば、「現状の暗号通貨にも危険性が出てきたのか」を過剰反応することなく正確に知ることができるでしょう。

参考文献

[1] Newsweeks (2019.10.25) “グーグルは本当に量子コンピューターの開発は成功したのか？”
https://www.newsweekjapan.jp/stories/world/2019/10/post-13265.php

[2] Andreas M. Antonopoulos「Mastering Bitcoin unlocking Digital Cryptocurrencies」, NTT出版 (2017).

[3] 国立研究開発法人、科学技術振興機構、研究開発戦略センター (2018.8.17) “ 科学技術未来戦略ワークショップ報告書、みんなの量子コンピューター　〜情報・数理・物理で拓く新しい量子アプリ”
https://www.jst.go.jp/crds/pdf/2018/WR/CRDS-FY2018-WR-09.pdf

[4] 高木剛「暗号と量子コンピューター耐量子計算機暗号入門ー」, オーム社 (2019).