量子コンピュータとブロックチェーン

ビットコインをはじめとしたブロックチェーンを基盤にした技術は、量子コンピュータの実用化によりどういった影響を受けるのかについて考察します。

量子コンピュータ

1980年代に、量子力学を応用した提唱された新しいコンピュータの概念です。

当初は夢のコンピュータとか言われていた記憶がわずかにありますが、実際のところは「お題によっては、従来コンピュータ(いまのコンピュータ)と比較して、とてつもない速さで解を出すことができる」という特徴をもつ(期待されているといってもよいかも)コンピュータです。

bit, qubit

従来コンピュータでは、情報をbitという単位で扱い、このbitにを対象に記録、演算することで情報を処理します。bitとは、binary digit (2つの数字)からなる造語で、0 または 1 の値をとります。古典コンピュータのbitをCbit (classical bit) と呼ぶこともあります。

対して、量子コンピュータでは情報の単位として、bitではなくqubit (quantum bit) を使います。qubitは0と1だけでなく、量子力学的な重ね合わせ状態もとることができます。

量子重ね合わせ状態

これが量子力学を知る上で、まず躓くところだと思います。

  • 状態そのものの重ね合わせ
  • ある振幅を持った2つの確率波として表される状態

という言い回しがされますが、少々わかりづらい。

量子重ね合わせは、光に関する実験を行ってゆくうちに、こういう概念を当てはめないと説明できない事象がおきてしまったことから生まれた、なんとも不思議な状態です。

私の力量不足によりここでのわかりやすい説明は諦めますが、ともかく、qubitは0と1の状態を同時に持つことができるというのがポイントです。

並列計算

量子コンピュータと従来型のコンピュータの違いは、情報量を増やすことで、よりはっきりしてきます。

いま、100 Cbitのメモリを考えます。これは0から2^100-1の範囲を表現できますが、ある時点でとり得る値は1つです。

対して、100 qubitのメモリを考えます。1qubitは2つの量子重ね合わせを表現できます。2qubitの重ね合わせは2^2=4。100 qubitでは2^100の重ね合わせをとることができます。量子コンピュータではこの重ね合わせ状態をそのまま計算に利用することができます。2^100 qubit同士の掛け算は、一度の処理で0×0, 0×1, …2^100×2^100 ができてしまうイメージです。この辺りが、量子コンピュータは超並列演算を可能にすると言われる所以です。

因数分解

量子コンピュータが注目されたきっかけの一つに、Peter Shorの示した因数分解のアルゴリズムがあります。

因数分解(例:15を5×3という因数の積に分解する)は、従来コンピュータでは計算に時間がかかる問題の一つです。数桁くらいでしたら大したことありませんが、桁数の増大とともに、計算のオーダーが指数関数的に増えます。Shorは、量子コンピュータを用いることで、因数分解をせいぜい桁数のに比例する程度のオーダーで解けるアルゴリズムを提唱しました。

RSA暗号

因数分解の困難さを拠り所にしていた暗号は、Shorのアルゴリズムに強い衝撃を受けます。その代表がRSA暗号です。RSA暗号は身近なところですと、SSL(https)に使われています。よって量子コンピュータが実用化すると、暗号化通信が無力化してしまうじゃないかと大騒ぎになったわけです。

実用化に向けて

しかしながら、実際に現在のRSA暗号をすぐに突破できるかというと、そういうわけではありません。量子コンピュータは理論が先行していて、「動くもの」は、急激な進化の手前にある状態です。

2016年IBMは世界で初めて量子コンピュータをクラウドで公開しました。当時は5qubitと16qubitの量子コンピュータにアクセスできました。その後改良を重ね、2017年11月には、20qubitの提供を開始しています。

現時点でRSA暗号の鍵長は2048bitです。これをShorのアルゴリズムをもって量子コンピュータで解こうとしたら、誤り訂正などを考慮しないとしても、2048qubitが必要になります。つまり2桁足りません。しかし中国では一兆円規模の研究施設を建設を計画したり、Google, IBM, 大学などの研究機関等、多くのプレーヤによる開発競争が加熱しています。よって、爆発的な進化がいつ起こってもおかしくない状況であると考えます。

ビットコイン

少々前振りが長くなりましたが、ここからは量子コンピュータの出現と実用化により、ブロックチェーン技術の安全性は脅かされるのか、について考察します。

ただ、単にブロックチェーン技術というと抽象的すぎるため、具体的なアルゴリズムによる考察になりません。そこで、本稿では、ビットコインに絞って考察を進めます。(記事の冒頭に「ブロックチェーンを基盤にした技術」と書いたのはこのような理由によります)

ビットコインは以下の2つのアルゴリズムを、システムの安全を担保するための基盤としています。

  1. 楕円暗号
  2. ハッシュ

楕円曲線暗号

ビットコインにおいて楕円曲線暗号は「自分のウォレット(財布)が、他人から不正にアクセスされないこと」を実現するために用いられます。楕円曲線暗号の解説とそれがどのようにビットコインで用いられているかについては、名著Mastering bitcoinをご参照ください。なんと日本語翻訳版が無償で公開されています。

楕円曲線暗号はRSAのように因数分解を用いていないため、量子コンピュータによりShorのアルゴリズムを用いることで、公開鍵から秘密鍵を現実的な時間で求められる恐れがないと思いきや、どうやら、楕円曲線暗号も量子コンピュータにより突破されることが指摘されています。こりゃ困った。

ハッシュ

ハッシュもビットコインにおける基盤技術の一つです。過去のブロックがの改ざん防止や、ビットコインアドレスの生成に用いられています。また、マイニング(PoW)を成立させるための技術という側面もあります。つまりハッシュの一方向性が量子コンピュータにより破られると、過去ブロックの改ざんが容易になり、ビットコインアドレスから公開鍵(ひいては秘密鍵)の推測が容易になり、マイニングの難易度調整が困難になったり、量子コンピュータを持つ者が圧倒的なマイニングパワーを獲得したりすることが懸念されます。

が、今の所量子コンピュータによってハッシュ関数を攻撃する有効なアルゴリズムは発見されていません。例えばSHA256で特定のハッシュ値をとるデータを発見するには、従来型のコンピュータで2^256の演算が必要ですが、量子コンピュータでは2^128(これでも非現実的な演算量)で済むといった程度です。

じゃあどうするの

何年先かはわかりませんが、量子コンピュータが実用化すると、楕円曲線暗号のような公開鍵暗号方式が無効になり、それらを用いているビットコインのようなシステムのセキュリティ基盤が崩れることがわかりました。ではどうするか。

量子コンピュータ耐性

アルゴリズムを変更するしかないのですが、調べると、「量子コンピュータ耐性」あるいは「量子耐性」というキーワードが登場します。量子コンピュータからの攻撃にも耐性をもつという意味です。

ビットコインのコミュニティでは、量子コンピュータ耐性を持つアルゴリズムとして、Lamport署名が注目されているようです。Lamport署名はハッシュ関数の安全性に依拠しています。また、次世代の国際標準公開鍵暗号方式としては、格子暗号が注目を浴びています。いずれにせよ、暗号は長年の検証に耐えた「枯れた技術」を採用すべきであるため、早めの準備が求められます。

ちなみにビットコインでアルゴリズムの変更をする場合、ソフトフォークし、利用者は新たにビットコインアドレスを生成し、資金を引っ越すことになります。この辺りの合意形成コストと、移行にかかる時間が気になるところです。

量子耐性通貨

なお、将来を見据えて、初めから量子耐性を持った仮想通貨というのも登場しています。

参考