量子コンピュータとモナコイン (1)

はじめに

みなさんこんにちは。

VIPPOOL でエンジニアをやっています、星月です。

前回、楕円曲線暗号の強さについてお話ししたところ、
Twitter で以下のコメントを見かけました。
「量子コンピューターに対抗できそうなmonacoin」

ところが、残念ながら、モナコインは量子コンピュータに対しては、
完全に太刀打ちできません。残念ながら対策もありません。
今回はそういうお話をしようかと思います。

量子コンピュータの仕組み

まずは量子コンピュータがどういうものか。
というところから説明いたしましょう。

いわゆる普通のコンピュータは、FF (フリップフロップ) や、
キャパシタ（コンデンサ）の充電・放電を使って、0 と 1 のどちらかの状態を記憶しています。
これを 1 bit という単位で扱います。

FF をたくさん集めたものは SRAM と呼ばれ、CPU のレジスタやキャッシュに使われています。
コンデンサをたくさん集めたものは DRAM と呼ばれ、
PC のメインメモリや GPU のメモリに使われています。DDR4-SDRAM とか言われるものの後ろ４文字です。

一方、量子コンピュータは、「1 である確率が x%（つまり 0 である確率が 100-x%）」
という素子を使って計算します。これを 1 qubit という単位で扱います。

例えば普通のコンピュータでいうビット反転。1 qubit の計算で 1-a を計算してみると、
その出力結果は「1 である確率が 100-x%（つまり 0 である確率が x%）」となり、
その qubit を観測すると、100-x% の確率で 1 を観測でき、x% の確率で 0 を観測できます。

なんじゃそりゃ。と思われるかも知れませんが、こういうシステムを構築すると、
色々な計算がすごく効率的に計算できてしまうのです。不思議ですね。

まずはその例を見てみましょう。

量子コンピュータで素因数分解をしてみる

RSA 暗号では、2 つの大きな素数 p, q を用意して、その合成数 N = pq を公開鍵とします。
p, q が十分に大きければ、N の素因数分解は現行のコンピュータでは非常に難しいので、
公開してしまっても問題ない、ということです。

ところが、これは量子コンピュータを使うと効率的に解けてしまいます。

十分な数の qubit を並べて、p', q' と名付けましょう。量子ゲートと呼ばれる素子で計算を行います。
p'×q' を計算して、その結果が N と一致したときに p' と q' を観測しましょうか。
……この方法ではダメです。これではまだ従来のコンピュータの考えから抜け出せていません。

なぜなら、p' も q' も p'×q' の計算結果も、観測する時点で、各 qubit それぞれが、
それ自身の持つ確率で 0 か 1 かに収束するので、p' の観測結果と q' の観測結果を掛け算しても、
p'×q' の観測結果と一致する確率は qubit 数が増えるほど、0 に近くなります。
これでは話になりません。

じゃぁどうするのか。
ここで出てくるのが、有限巡回群の位数を求めるアルゴリズムです。
詳しい説明は量子力学の知識が必要になるため割愛しますが、
量子コンピュータは、有限巡回群の位数を求めるのが得意です。
なので、素因数分解の問題を、有限巡回群の位数を求める問題に帰着させます。

まず、N より小さな正の数 a をランダムに決めます。
十分な数の qubit を並べて、 ${ a^x \bmod N }$ という有限巡回群を作ります。
そうすると、この有限巡回群の位数φは、量子コンピュータなら簡単に計算できます。
オイラーの公式により、 $a^{(p-1)(q-1)} \bmod N=1$ が成り立つため、
$\phi = (p-1)(q-1)$ となります。p, q は大きな素数なので、2 は使いません。なので、
p も q も奇数ですので、p-1 も q-1 も偶数となります。というわけで、 $b=a^{\frac{\phi}{2}} \bmod N$ とします。
すると、 $b^2 \bmod N=1$ となるので、 $b^2-1 \bmod N=0$ です。
左辺を因数分解すると $(b+1)(b-1) \bmod N=0$ ですので、b+1 も b-1 も N と共通の約数を含みます。
なので、b+1 と N、b-1 と N の最大公約数を求めると（これは従来のコンピュータで効率的に計算できます）、
N の約数である p, q が計算できる。……という流れです。

これを、Shor のアルゴリズムと呼びます。

楕円曲線暗号を量子コンピュータで解いてみる

楕円曲線暗号は、楕円曲線上のベースポイントとなる点 G は公開されていて、
秘密の値 x 倍した P=xG を公開鍵として使います。

以前、このブログでも紹介した通り、楕円曲線上の点のなす群は有限巡回群となっています。
参考：https://blog.vippool.net/entry/2019/04/08/125519

量子コンピュータは、有限巡回群で aG-bP=O となる a, b の組み合わせを求めるのも得意です。
ちなみに、ここで、P=O とすると、aG=O となり、G が生成する有限巡回群の位数を求める問題に
帰着することに注目してください。そう、素因数分解で使ったやつです。

さて、この式を aG-bP=aG-bxG=(a-bx)G と式変形すると、(a-bx)G=O となります。
一般的に使われている楕円曲線は、ベースポイントとその位数が公開されているので、
位数を n とすると、 $a-bx \bmod n=0$ となります。
これを x について解くと、 $x=ab^{-1} \bmod n$ と解けます。
ここで、-1 乗は n を法とする逆元の意味です。