賞金１億円のミレニアム懸賞問題とビットコイン

ビットコインなどの暗号通貨に価値がある理由は様々ですが、その内の１つにセキュリティが上げられます。自分の持っているコインがハッキングされてしまったら元も子もないですよね。暗号通貨に限らず、私たちが普段使っているオンラインショッピングであったり、SNSなどのWebサービスにも欠かせないセキュリティですが、これらに共通している技術に「公開鍵暗号」というものがあります。公開鍵暗号はインターネット上で安全にショッピングをしたり動画をみたり、また暗号通貨を送受信したりするために欠かせない技術です。一般的に標準化・普及した公開鍵暗号にはRSA暗号方式というものがあります。このRSA暗号方式の仕組みは以下の1文で表すことができます。それは、

2つの素数p,qを掛けたNから元の素数p,qを見つけるのは難しい

と言うことです。Nは簡単に求めることができますが、Nからpとqを求めることは非常に難しいのです（素因数分解が難しいとも言われます）。簡単に計算できるが逆計算は非常に困難である性質をもつ関数を一方向性関数と言い（詳細はここを参照）、暗号通貨やPKI（公開鍵暗号基盤）の核となっているものです。

しかし、この一方向性関数の存在は証明されておらず（p*q=>Nは一方向性関数の候補にすぎません）、もし存在が証明されると、「P≠NP」であることが示されます。今、突然でてきた「P≠NP」という言葉ですが、これは何を表しているかと言うと、

効率的に解を求める方法は存在しない
（上記の場合、Nからpとqを求める方法）

を数式で表現しているのです。これを「P≠NP予想」と呼び、PKIや暗号通貨の安全性を根拠としているモノです。なぜ語尾に「予想」が付くかと言うと、まだこの数式を証明した人がいないためで、本ブログの題名にもあるように、ミレニアム懸賞問題と題して証明できる人を募集しているみたいです。もしこの予想が間違っており、P=NPであることが証明されると、暗号通貨はもとよりPKIやGPKIなど世の中のインターネット上の安全性は皆無となってしまいます。

ちなみに、ビットコインの署名と検証は楕円曲線暗号（ECDSA）を使っていますが、これも公開鍵暗号方式のうちの1つであり、「離散対数問題」を安全性の根拠としています。離散対数の計算も非常に困難であり（素因数分解が難しいという性質に似ている）、セキュリティの担保も「P≠NP予想」を前提にしています。ミレニアム懸賞問題の1である「P≠NP予想」を解くと1億円の懸賞金が手に入りますが、これを解くことでビットコインの時価総額である数兆円までも手に入れることができるかもしれないですね！ウヒヒ

＜おまけ＞
以前、自分も分けもわからず呟いていたリーマン予想ですが、これは「素数の分布の規則性」に関する予想であり、この予想が証明されたとしても暗号通貨や公開鍵暗号基盤への影響はありません。これは素数がいくつあるかを厳密に表すことが可能になるこであり、いくら素数の数が分かったとしても、Nからpとqを見つけ出すための計算コストには影響がないのです。また、リーマン予想もミレニアム懸賞問題のうちの1つとして上げられています（リーマン予想やミレニアム懸賞問題に関する書籍の紹介はここが面白いです）。