ブラム・ブラム・シャブ....

私は別に専門家じゃないですけど、暗号関連の話って大好きだったりします。このところ「自然とランダム」と「秘奥義メルセンヌ・ツイスター」で、ランダム性と強く結びついた暗号関連話が続いたところで、こんな名前のアルゴリズムがあったりするんですね。

あ、これ開発者の３人の連名で付いているだけです。ブラムさん２人とシャブさんが開発したアルゴリズム....というだけの名前ですが、メルセンヌ・ツイスターがアニメの必殺技だったとすると、こっちはクトゥルフ神話（苦笑）かな。

この Blum Blum Shub アルゴリズムは、暗号論的に安全な一連の乱数を提供します。言い換えると、メルセンヌ・ツイスターが漸化式によるものなので、「前の値から次の値を推測する」ということができてしまう...のに対して、Blum Blum Shub は「前の値から次の値を推測できないことが、数学的に証明されている」（ま、現実には前の値から次の値を推測する困難性が、素因数分解の困難性と同じであるようにしているわけです）アルゴリズムです。強力なアルゴリズムですが、これ数論としてはそんなに難しい知識を使っているわけじゃないようです。ですからメルセンヌ・ツイスターを種にして Blum Blum Shub で希釈すれば安全だ、という感覚のようです。メルセンヌ・ツイスターは「充分にランダムに散らばった種」を提供しますからね。

そういう具合に結構ここらへんの数学寄りの応用アルゴリズムって、目立たないけども重要な進歩が1990年代後半にかなりあるようですね。この理由は勿論インターネット環境の普及があって、セキュリティに関する議論が盛んになったことから、こういう暗号技法が着目された（RSAとかもそうですね...）わけです。

勿論こういう暗号技法の「意外な利用」の最大なものは「電子署名」ですけども、一時私も面白がって調べたことのあるいわゆる「マジック・プロトコル」がいろいろあります。たとえば通信環境で「コイン投げ」を公平に行うためのプロトコルとか、電子投票で「投票者の投票内容が秘密」なのに、投票全体が公正であるか（たとえば二重投票した人がいないとか）を検査できるプロトコルとか、面白い応用例がいろいろとあるわけです。ここらへん数学的には「ゼロ知識証明」と呼ばれる新しいジャンルです。興味のある方はこういうキーワードで調べてみると刺激的ですよ！