■新暗号方式はたぶん胡散臭くないよ

この記事にはブクマを見る限りだいぶ懐疑論が集まってるみたいだね。残念ながらWebで資料を探しても見つけることができなかったので、憶測でしか語れないけれども、たぶん大丈夫だと思う。もっとも、「理論的には」の話であって「実用的に」どうかは知らないけどね。

大矢氏がハッタリをかます動機がない

まず、大矢氏はその道では有力な研究者で、名前も売れてます。俺のような門外漢でも知ってるぐらいだから。だから、胡散臭いものに手を出すという動機がまずないんですよ。

ただし学者というのは自分の仕事を宣伝してナンボという商売でもあるから、まだ残っている欠点を敢えて黙っているということはあるかもしれない。でも、少なくとも「CABは完璧な暗号である」とは言っていないはず。そういう意味で、嘘はついていないことは信用していいと思います。

「確率0」というのは「絶対に解けない」ということではない

次に、大矢氏の発言「鍵空間は無限大ですから、鍵を推定できる確率はゼロ」という発言は数学的に普通かつ真っ当なものであって、レトリックでないことを指摘しておく。

数学では、確率は長さとか面積とか体積とともに「測度」という概念に包含されるんだけれど、「確率0」というのは「『点』は『無』ではない」という話と本質的には同じものだ。例えば、中学校の時「点には大きさがない、長さも幅もない」「直線には幅がない」「平面には厚みがない」と習ったはずだけれど、つまりこれは「点の長さは0」「直線の面積は0」「平面の体積は0」って話なんだよね。点とか直線とか平面というのは「無」ではなくちゃんと存在するものなのに長さとか面積とか体積が0（こういうのは「零集合」なんて名前もついてる重要なものだ）という話、当初違和感をもたなかった？多分、今になってみれば感覚的に「そんなもの」だと理解できているはずだけど。つまり、「長さや面積や体積が0ということと、存在しないということは別物だ」ということ。

確率が0というのもこれと同じなんだ。例えば、0<x<1を満たすxを全くのランダム（あるxが別の数より選ばれやすいということはないものとしよう）に選んでくることを考えよう。これはまさに「数直線0<x<1上、x=0.5という一点の長さはいくつ？」と聞いているのと同じことで、答えは0になる。別に変なことではないでしょ？

アルゴリズムの実用化の難しさ

もっとも確かに、「現実のコンピュータ上で、鍵の候補が無限大なんて関数が作れるのか」という疑問があると思う。俺の理解が間違ってなければこれは確かに無理だ。でも、そういう言い方をするのは無理なことではないんだ。

というのは、アルゴリズムの理論を作るときは、暗黙に「コンピュータには無限にメモリがある」と仮定してしまうことがある。もちろん現実にはそんなことはない。でも、必要なだけメモリを増設すればいくらでもその状態に近づけることはできるので、実用はともかく理論としてはそれで十分と考えることがあるんだ。

もう少し詳しくいうと、チューリングマシンっていう数学モデルがあるんだけれども、これはメモリが無限にあるコンピュータと等価な能力を持っている。そして、情報工学の問題はチューリングマシンに対して考えられることが多い。しかし、現実のコンピュータはメモリが有限しかないから、これは本当は「有限オートマトン」（基本情報処理の試験にも出るから知っているはず）とよばれる非常に単純なモデルで表せてしまうものだ。これの能力は余りにも限られているので、たとえばカッコ対応問題（たとえばCやJavaで"{"と"}"の数が釣り合っているかを確かめる問題）すらも一般的には解けない。実際、メモリ内で表現できる最大の数以上のカッコを与えてやればいい。もちろん、そんな沢山のカッコを与えるなんて現実には無理だけどね。

そういう風に、アルゴリズムについて理想と現実の壁は大きく、常に実用化の壁というものがつきまとう。そういう意味で大矢氏の新暗号が本当に画期的なものになるのかどうか、これはやってみないとわからないと思う。今後の展開に期待だね。

追記

生半可な知識で下手なこと書くもんじゃないですね。専門家からのご批判を頂きました。

http://d.hatena.ne.jp/smoking186/20080412/1208008068

というわけで、この記事は反面教師として下さいませ。この記事単独では、間違ったことは書いてないつもりですが、前提を理解していませんでした。

Permalink | 記事への反応(2) | 11:46

ツイートシェア