はじめまして、田中芳治といいます。

これまで大学・研究機関で情報技術に関わる研究をしてきました。

今回から技術コラムを書かせていただきます。

なるべく易しい解説を心がけますので、よろしくお願いいたします。

唐突ですが、皆さんは量子コンピューターというものをご存じでしょうか。

最近各国や大企業が開発を目指している次世代方式のコンピューターです。

1980年代から量子力学の原理を利用した新しい計算方式が理論的に提案され、1990年代には有効な量子計算アルゴリズムがいくつか考案されました。

1994年にアメリカの数学者ピーター・ショアが考案した量子計算のアルゴリズムは、公開鍵暗号方式に対して脅威を与えることが理論的に指摘されています。

公開鍵暗号方式は今日のセキュアな通信を支えるインフラとして利用され、民生用技術だけでなく安全保障上もとても重要であることはいうまでもありません。

いい意味でも悪い意味でも「破壊的イノベーション」ということですね。

公開鍵暗号を利用したデジタル署名は、ブロックチェーンのブロック生成プロセスにも採用されています。もし、量子コンピューターが開発されれば、暗号資産にも影響を与えることになるといわれています。

とはいえ、現時点ではまだ実現されていないので、実際に量子コンピューターが現在の暗号方式を破ったという報告はありません。

しかし、いまは安心してよいのでしょうが、これから先はどういう展開になるかは気になるところです。

時々、量子コンピューターに関係する研究がメディアで紹介されることがありますが、実際のところどうなのかという疑問はあるでしょう。

色々な情報があるとどれが正しい事実なのかがわからなくなってしまいます。

そんな先行きが不透明なときに役立つのが＜理論＞です。

幸いなことに、暗号技術の背景には＜理論＞があります。

田中のコラムでは、複数回にわけて、量子計算機が既存の暗号技術に対してどのような脅威を与えるのかを、理論面から解説します。

その上で、量子計算を行う装置を開発するのは非常に困難であるようだな、ということを直感的に理解して頂くことがねらいです。

まず、前提となる知識として「楕円曲線上の離散対数問題（ECDLP）」を簡単に解説します。

ざっくりというと、図に

R=xP

みたいな式がありますよね。これがxについての方程式だと思ってください。

R、Pに対して具体的な数値で与えられていて、式を満たすxを求める問題、これがECDLPです。

以下で、もうちょっと記号を説明します。

楕円曲線というのは、２次元平面上のある曲線で

ｙの2乗　＝　xの3次式

の形で与えられるものです。

ビットコインやイーサリアムの署名では、secp256k1という規格があり、利用する楕円曲線の式が定められています。

さらに、その楕円曲線上の点に対して、加法・減法が定義されます。

つまり、楕円曲線上の点P,Qのx座標・y座標の値から、ある関数（計算手続き）にしたがって、また別の点R=P+Qの座標を計算することができるということです。

さらに、自分自身の足し算を整数倍として考えれば、自然と点Pの整数x倍

xP

も定義されます。

ECDLPの問題は、点RとPが与えられているとき、Pを何倍したらRになりますか？という問題です。

具体的に楕円曲線の簡単な例を考え、図に示しました。

P=(0,1)という点が与えられると、その整数倍を全て一覧にしています。

この場合は、Pを28倍すると、また元のPに戻るようですね。

27個の点列に規則性があるように見えるでしょうか？

ないようにみえますよね。

実際、複雑なようなんです。

だから、R=(12,19)という点が与えられても、すぐにR=xPを解くことができるような公式みたいなものは無いようだと考えられます。

しかもこの例では素数23を法としていますが、secp256k1で利用される楕円曲線は、もっと大きな素数を法としています。

こうなると、xP=Pに戻ってくるまでのxは大きくなってしまい、探索すべき解の範囲も大きくなってしまいます。

ざっくりいうと、secp256k1では256ビットの数の中で、一つだけ解xがあると思ってください。

ECDLPでは、＜解の公式＞のようにダイレクトにxを求める手法がなく、現在のコンピューターでは大量の時間がかかってしまう方法しかありません。

現実的な時間では解けない、という意味でECDLPは「解けない」とか、「計算量的に困難である」などと言われています。

もし、このECDLPが解けてしまったら、ビットコイン・イーサリアムに限らず多くのブロックチェーン技術に深刻な影響を与えてしまいます。

公開鍵暗号では、このRが公開鍵でxが秘密鍵として使用されます。

また、Pは公知の情報として運用されるので、R,Pは誰でも入手できる前提になります。

この状況設定で秘密鍵を求められないようにするためには、ECDLPが解けないということが重要です。

もし、xが流出してしまうと、別人がなりすまして署名することが可能になってしまうなど、深刻な障害が発生します。

一方、ショアのアルゴリズムでは、ECDLPを現実的な時間で求めることができるとされています。

次回はショアのアルゴリズムを解説し、どういうところがポイントなのかを説明します。