増田の誤解 - Crypt Alarm Basic (仮称) 方式について
追記: 2008/04/15 0:03
“解読不能”の新暗号の記事について、いつくかのお詫び − ＠IT
続報出た. 大方の予想通り, ストリーム暗号の疑似乱数生成部をブロック暗号が担っているタイプのようだ.
煽りっぽいのは大矢教授/入矢助教への不満だと思ってください. あと@ITの記者 (西村賢氏) はもっと纏まった記事を書いてください.
ref:「解読不能は数学的に証明済み」、RSAを超える新暗号方式とは − ＠IT
ref:新暗号方式はたぶん胡散臭くないよ
いやーそれはどうかなー.
「理論的」な胡散臭さ
大矢氏がハッタリをかます動機がない
まず、大矢氏はその道では有力な研究者で、名前も売れてます。俺のような門外漢でも知ってるぐらいだから。だから、胡散臭いものに手を出すという動機がまずないんですよ。
いや, ハッタリをかます動機は無いにせよ, 誤解する可能性はありますよね? 暗号家見習いが考えるに, 単に暗号学の基礎を知らない, または, これまでの暗号学を無視しているかのどちらかなんだと思うんですよ. 前者であれば誤解ですし, 後者であれば良く言って誤解を招く表現, 悪く言ってハッタリです*1. あと会社作ってるんでハッタリをかます動機はあると思いました. (他の増田さんもhttp://anond.hatelabo.jp/20080412114633で書いてますけど.)
以下, どうして俺にとって彼らの発言が胡散臭いのかというのを説明してみます.
例の記事だと計算量的に難しいのが「解読が困難」であるという定義になっています. 「CAB方式は数学的に解読が不可能」との発言があるので, 大矢氏は計算量的な困難性を超えた困難性の話をしているわけです.
一方, 暗号学の枠組みでは, 情報理論的に安全な公開鍵暗号方式というのは存在しません. まず, 公開鍵と秘密鍵には関連があります. ということは現実的には無理かもしれないけれど, 理論的には公開鍵から秘密鍵が求められるので, 暗号文の情報理論的な安全性は損なわれています.
また仮に計算量的な困難性を証明していたとすると, 一方向性関数が作れているので, P!=NPが証明出来ています. 凄いね!
ということで暗号学の枠組みから見ると彼らの発言は意味が分からないのです. なので胡散臭いなぁと思いました. よりつっこんだことを言えば, そういう発言は良心的なセキュリティ関係者にとっては害悪だと思います.
あ, CAB方式は公開鍵暗号方式で良い筈ですよ.
「ほかの公開鍵暗号方式は、表現方法や公開鍵の数を変えることでCAB方式に含まれることが数学的に証明されています。ほかの公開鍵暗号方式はCAB方式の特殊な場合なのです」（大矢教授）。
ってあるんで.
鍵空間の話
「確率0」というのは「絶対に解けない」ということではない
次に、大矢氏の発言「鍵空間は無限大ですから、鍵を推定できる確率はゼロ」という発言は数学的に普通かつ真っ当なものであって、レトリックでないことを指摘しておく。
数学では、確率は長さとか面積とか体積とともに「測度」という概念に包含されるんだけれど、「確率0」というのは「『点』は『無』ではない」という話と本質的には同じものだ。例えば、中学校の時「点には大きさがない、長さも幅もない」「直線には幅がない」「平面には厚みがない」と習ったはずだけれど、つまりこれは「点の長さは0」「直線の面積は0」「平面の体積は0」って話なんだよね。点とか直線とか平面というのは「無」ではなくちゃんと存在するものなのに長さとか面積とか体積が0（こういうのは「零集合」なんて名前もついてる重要なものだ）という話、当初違和感をもたなかった？多分、今になってみれば感覚的に「そんなもの」だと理解できているはずだけど。つまり、「長さや面積や体積が0ということと、存在しないということは別物だ」ということ。
確率が0というのもこれと同じなんだ。例えば、0<x<1を満たすxを全くのランダム（あるxが別の数より選ばれやすいということはないものとしよう）に選んでくることを考えよう。これはまさに「数直線0<x<1上、x=0.5という一点の長さはいくつ？」と聞いているのと同じことで、答えは0になる。別に変なことではないでしょ？
測度を持ち出す必要は無いと思います. 鍵空間が無限大だったとしましょう. どうやって鍵を表すんですかね? 任意長のビット列? それは無理筋でしょう.
よくよく記事を読むと, CAB方式はブロック暗号
ってあるんですよね *2. ということは適切なパラメータの下で, 暗号化関数の定義域 (平文空間と乱数空間の直積) と値域 (暗号文空間) はそれぞれ有限集合になっている筈なんです. 有限集合から有限集合への関数の数は有限です. よって, そもそも鍵空間は無限大じゃないと思うんですよ. そこのところ, いかがでしょうか, 増田さん.
追記1: ごめんなさい. 上の話は下と繋がっているのね.
追記2: 上の話はその段落単体で読むと妥当. ただ全体を通して暗号の話として見ると変だと思う. そもそもTMのモデルを使っているときには有限サイズの空間しか考えられないんだから, 下に書いてあるようにパラメータ化して理論に折り込んだ方がいいんじゃないでしょうか?
追記3: そうそう最後の項についての話を忘れていた.
アルゴリズムの実用化の難しさ
もっとも確かに、「現実のコンピュータ上で、鍵の候補が無限大なんて関数が作れるのか」という疑問があると思う。俺の理解が間違ってなければこれは確かに無理だ。でも、そういう言い方をするのは無理なことではないんだ。
そりゃそうですよね. ただ, その後の話は暗号屋から見るとおかしいです.
暗号ではパラメトライズされた議論が行われています. n=1024のときにはRSAの鍵長は2048ビットで, 敵が秘密鍵をT時間で求められるなら, ある定数cで大体T+n^5くらいの計算時間で素因数分解できるとかそういう話をします. なので, 暗号理論の方でも元々有限長で考えています. ということで, 暗号の文脈から言えば, 鍵の候補が無限大の暗号方式ってのは意味が分かりません.
そもそもアルゴリズムの枠組みでも同様な議論をすることが多いんじゃないでしょうか? 増田さんが例に挙げている括弧対応問題も, 「入力長がnビットの文字列であるとして, 括弧が対応しているかどうか判定せよ」という話にすれば, 理想と現実の差は埋まると思います.
