ブロックチェーンで使われている暗号の解読困難性の根拠となる離散対数問題をざっくり理解する

はじめに

こんにちは．株式会社AcompanyのCTOを務めている近藤(Takeharu.K)です．今回は，ブロックチェーンを支える技術の一つである暗号について簡単に書きます．

現代における暗号は，計算機が現実時間で解くことができないような数学的な困難性をもち，かつ，ある秘密を知るものだけは簡単に解くことができる問題を作り出すことで実現されています．

このような性質を作り出すことができる関数のことを一方向性関数(One Way Function)と言います．この一方向性関数には素因数分解問題を提供するものや，離散対数問題を提供するものがあります．

実は，普段何気なくウォレットで暗号通貨の送金や，スマートコントラクトの実行をしていますが，それらはこの離散対数問題の困難性によって実現されています．

そこで，今回はこの離散対数問題とは何者なのかということを噛み砕いていきます．

離散対数問題は怖くない

まず，離散対数問題は名前ほど怖くないということを示します．

実は一言でこの問題を述べると以下のようになります．(注意:数学的に正確でありません)

「g を何乗したら y になるか？」

つまり

の s を求めよということです．そんなに難しくないですよね．

一般的にこういう問題は対数の log を使って計算することができます．つまり，「対数問題」を解くことで解決します．

次に，これに「離散」をつけてみます．

急に難しく見えますが，y と g が素数 q を法とした整数の集合であることが条件として示したものになります．

Z mod q は整数 Z の集合を q で割った余りの集合を表します．つまり，q で割った余りでしか表現できない空間での計算であるということを示しています．

この条件をつけることで一般的な対数問題のように解くことができないことが知られています．これが離散対数問題です．再度記述しなおすと以下のようになります．

「g を何乗したら y になるか？(素数 q を法とする)」

mod q がついた対数問題と考えれば分かりやすいです．これで離散対数問題はもう怖くないと思います．

指数を求めるのは難しい

次になぜ離散対数問題を解くことが難しいかを見ていきます．

具体的に問題を解いてみることでその困難性を確かめてみます．

問題「2を何乗したら1になるか？(11を法とする)」

以上の計算によると 2 を 10 乗すると1 になることが分かりました．今回の例であれば素数 q＝11 や g=2 と小さいので順番に計算をすることで求めることができましたが，現在，効率的に解を求める方法が発見されていません．

つまり実質的に指数 s を探索することは q の大きさを持った空間を全探索することと同義なのです．例えば q が100桁の整数の場合，最低でも100桁の整数の中からたった一つの正解を引き当てる必要があるのです．効率的なアルゴリズムもいくつか提案されていますが，いずれも多項式時間で解くものではありません．

これは現在の最も高速に計算できる計算機を並列に途方もない数を並べて計算しても，人間が生存している間に解くことはできないような全探索になってしまいます．

指数計算は簡単

一方で，累乗の計算を高速に行うことができる「バイナリ法」というアルゴリズムが提案されており，これを用いることで，指数 s が分かっていれば簡単に g から y を求めることができます．

具体的に示すと以下のようになります．

計算問題「2 の 257乗を求めよ」

このように累乗の形に変形することで 8 回の計算を行うだけで 257 乗が計算できます．つまり，単純に計算する場合であれば 257 回の計算が必要ですが，たったの 8 回の計算で求めることができます．

まとめ

離散対数問題は「g を何乗したら y になるか？(q を法とする)」です．

ただし，この問題を簡単に解く方法が見つかっていないため，実質的に解くことができない性質を持ちます．

一方で，指数計算の問題「g を s 乗したらいくつになるか？(q を法とする)」はバイナリ法を用いることで簡単に求めることが出来ます．

このように，一方向への計算は非常に難しいが，逆方向の計算は非常に簡単である性質をもつ関数を一方向性関数といいます．

この性質を用いて実現された暗号の一種がブロックチェーンに用いられています．

今後も，Acompanyからブロックチェーンに関する記事を投稿していきますので，ぜひfollowしていただけると嬉しいです．

Happy Hacking 😎!