解読不能な公開鍵暗号Crypto Alarm Basic? - トビハネインディアン

解読不能な公開鍵暗号Crypto Alarm Basicな暗号方式Crypto Alarm Basicに関する発表があったようです(東京理科大学大矢雅則教授)。

「解読不能は数学的に証明済み」、RSAを超える新暗号方式とは − ＠IT

考案者によると

「われわれの開発した暗号方式は、数学的に解読が不可能であると証明されています」

まっじでーー？？と思い、いろいろ論文探したんだけど、ほんとに見つからないんだよ。

「数学的に解読不可能」というのがどういう意味なのかはさておき、「情報理論的に」解読不可能な暗号としてワンタイムパッドがずいぶん昔(1940年代)にかの有名なシャノンに考案されている。やりかたは極めてシンプルで、たとえば送信したいメッセージをM=HELLOWORLDとすると

1. Mと同じ長さの秘密の乱数R(例えばR=DKLKHGRHEP)を生成し、送信者と受信者で共有する
2. 送信者：C[i] ← M[i]+R[i] mod 26 としてCを受信者に送信。ただし M[i],R[i],C[i]はそれぞれメッセージ、乱数、暗号文のi文字目とする。
3. 受信者：M[i] ←C[i] - R[i] mod 26

ここでは26文字のアルファベットを使ったのでmod 26としたけれど、ふつうはbitにエンコードして排他的論理和を取ればよいわけです。

情報論的に安全というのは神様(=無限大の計算能力を持つ解析者)ですら暗号文CからメッセージMを解読できない、という意味です。ようするにワンタイムパッド＝最強の暗号です。ただ乱数Rが一回しか使えないうえに、メッセージ長=鍵長なので、まるで実用的ではないわけです。

シャノンが示したのはこの情報理論的に安全な暗号はワンタイムパッド以外にはない、ということです。これ重要です。この暗号がワンタイムパッドでないならば、この暗号は情報理論的に安全な暗号ではなく、計算量的に安全な暗号なんです。計算量的に安全というのは、ぶっちゃけていえば、神様ほどではないけれど、ものすごく頭のいい人(あるいはコンピュータが)ものすごい時間をかけても、100年200年じゃ解くことはできない、というような概念です。

普通に考えれば新しく考案されたこのCrypto Alarm Basicも計算量的に安全なものなのだろうと思うわけですが(量子コンピュータや分子コンピュータで実装されているわけではないので)、@ITの記事には

コンピュータの計算能力が爆発的に上がっても、あるいは量子コンピュータが実現されても、それでも「解読不能」と言い切れるのがCAB方式の強みだ。

とある。ひょっとして情報理論的に安全で、かつワンタイムパッドより優れた方式を発見したということでしょうか？？

入山博士はデモンストレーションで一般的なノートPC2台を使って映像ストリーミングを実演。数MbpsのビットレートのMPEG映像を8ギガビットと非常に長い鍵を使って暗号化し、サーバ・クライアントで送受信してみせた。

ともあります。ここにも8ギガビットと非常に長い鍵を使って暗号化し、とワンタイムパッド的な方式を想像させる記述がありますが、こんな長い鍵を使える理由がよくわからない。ほんとにワンタイムパッド的なのなのだとしたら、10MBのデータをAさんに送るためには、10MBの鍵をあらかじめオフラインでAさんに送っておく必要があるのです。なぜRSA等をつかわずにオフラインで送るかといえば、そこでRSAを使った時点ですでに情報論的安全性が保障されないからです。いったいどんな方式なんだろう。。。

また、

例えば、xのm乗というのも1つの関数ですし、2xも関数です。実際には逆関数の計算が極めて難しい関数の集合を利用していますが、こうした関数からなる無限集合から鍵となる関数をピックアップします。盗聴者の探索しなければならない鍵空間は無限大ですから、鍵を推定できる確率はゼロです」（大矢教授）。

鍵を推定できる確率はゼロ、と気になることが書いてあります。関数を鍵として使うってのはどういうことかこの文面からはよくわからないけれど、まあそれはいいとして、無限集合から一様ランダムに鍵をとってきて使うんだとしたら、鍵長も無限大になりうるんだよね。このとき無限大の公開鍵を転送するコストは無限大だから、意味がないんだよね。無限大のサイズの鍵を使えば確かに情報理論的に安全な暗号もできるだろうけど、それって別にワンタイムパッドよりいいってことにはならないんだよね。これもよくわからない。

そしてもう一つの謎は、

CAB方式の将来性に着目し、実験実装を行ったのが2006年。それから約2年間、学会発表やメディアへの公表、特許申請などは一切行わず、さまざまな用途に合わせたプロトコルの開発を進めてきたという。東京大学理学部を卒業後、米ロチェスター大学大学院へ進んだほか、ローマ大学、ハイデルベルグ大学など欧米の大学から招待を受けてきた大矢教授だが、その行動も欧米流だ。
　「学会で発表をして名誉だけを受けるという選択肢もありましたが、われわれは会社にしました」（大矢教授）。

これのどのへんが欧米流なのかはよくわからないけれど(ココ、皮肉ね)、第二次大戦中ならいざ知らず、これは現代暗号の提案としては全く普通じゃない。暗号はどうやって解読するか、を秘密にすることで安全性を確保してはいけないからだ。もしこれを認めるとすると、解読法が公になった時点でその安全性が怪しくなるし、守るべきものが秘密鍵と暗号化方式の二か所になってしまう。弱点は一つでいい。

暗号は、解読方式を明らかにした上で、暗号学者や数学者が徹底的にその暗号を破ろうとして、それでもなお脆弱性がみつならなくて（あるいは脆弱性が許容範囲内であって）初めて標準化される。名誉がどうこう、というような筋のものではない。会社を作って、特許をとって公開し、その後安全性について公に議論する、というプロセスを踏んだとしたって、利益の独占は十分可能なはずだ。いまいち当事者の意図が読めない。

@ITの中の人も暗号には詳しくないようで記述には矛盾が多いし、せめて論文か特許公開広報を公表してくれないと、なんともいいようがないです。