ratio - rational - irrational

キーサインパーティーの実施と効率的な身分証明書確認について考えてみた。

■ キーサインもらった

先日、日本Ruby会議2008の懇親会でPGP公開鍵に卜部さんのキーサインをもらった。キーににサインしてもらうのはこれが初めてで、今まで何のために公開鍵使ってたんだという話はある。「信頼の輪」に入ってなかったわけだからね。

PGPとか信頼の輪とかの話はOpenPGP作法(PDF)を参照。

ちなみに、私の公開鍵はpgp.nic.ad.jpに登録してあって、yugui.jpのメールアドレスで検索すると出てくる。fingerprintは"438F 411C FC0E 9589 A0E3 CC88 397C C7E4 92DB FC05"。新しいバージョンの名刺にはfingerprintを入れたから、比較的最近名刺を交換した人は見てもらうと裏に書いてある筈。

Rubyコミッタの認証には一応PGP公開鍵を使っていて、いざというときのオンラインの本人認証には「信頼の輪」が活躍するわけだ。だから、「コミッタは名刺にfingerpintを入れろ」とCommitterHowtoに書いてある。ま、普段はRubyistはもっとやることがルーズだけど、それでも厳密なセキュリティが必要な場面というのはあるわけだ。

■ キーサインパーティーしたい!

で、Rubyの人たちの間でもっとPGP署名を活用するために、今度の「日本Rubyの忘年会」か日本Ruby会議2009のときにでも、「日本Rubyのキーサインパーティー」をやりたいと思っている。前回の忘年会でも今回のRubyKaigiでも提案しようと思って忘れていたので、次回こそは!

ここで、どうやって効率的に本人確認をするか、という問題がある。公開鍵にキーサインをするというのは、「その公開鍵に対応する秘密鍵の持ち主がその人本人であることを、私が確認したことを保証する」って意味なわけだ。Debianみたいな開発者が世界中に散った開発プロジェクトの成果物をそれなりに信頼できるのは、こうして確認された「信頼の輪」によるものだ。各パッケージの開発者が全員「Debianコアメンバーの顔見知りの誰々の顔見知りである誰々」という風に実在の、トレースできる誰かであることが保証されているからだ。いい加減な確認でサインしてしまうとそこで「信頼の輪」が崩れるとか、自分が「いい加減なサインをする奴」ということで信頼を失うとかしかねない。

というわけで、キーサインするに当たってはその鍵を持っている人を、「国家もしくはそれに準じる組織による身分証明書」によって確認することになっている。私は自動車運転免許証を卜部さんにみせたし、卜部さんはパスポートを持ってきていた。なるほど、国際カンファレンスではパスポートのほうが確認してもらいやすくて良いんだろうな。慣れてるね。

■ 本題

Debianの過去ログを見ると、身分証明書確認のやり方が書いてある。「2列になって」と書いてあるのは、つまり二人ペアになって確認し、確認したら1つずつずれて、端の人は反対の列に移って、これで一周したら全員の身分証明書を確認しした、ということなのだろう。

Sassaman方式というらしい。O(n)だから、全員がごっちゃになってfingerprintを渡して確認してを個別にやる場合のO(n²)よりは効率がよい。

でも、n人のパーティーで確認するにはn回ずれる必要がある。もっと効率よくできないのか。そこでどうすれば良いのか3分くらい考えてみた。

■ 仮定

• Sassaman方式と同様に、事前にfingerprintと名前のリストを構築しておく。
  • したがってあとは、そこに居る人物と身分証明書が一致することを確認すればよい
• 1対1でなくても、mが十分に小さければ1対mの身分証明が可能。
  • 身分証明書片手に名乗ればよい。mが小さければ、証明書をはっきり見られし声も届くのでOK
  • で、m人が順番にそれをやればm×(m-1)パスの確認が終わる

そこで、m人組を作って相互確認し、それから組を攪拌した後にこれを繰り返す、ということを考える。

• 小さな素数pをとる。簡単のため、今パーティー参加者はp²人とする。
• p人組をp個作る。これらを第0組 .. 第(p-1)組とする。また各人には組内で一意な0 .. (p-1)の番号を与える。
• 各組で相互確認を行う
• その後、番号がjで、現在第i組にいる人は第(i+j) mod p組へ移動する
  • 繰り返す

これをp-1回行うと、全員が全員を確認したことになる。pは小さいのだからそれこそ列を作れば組み分けは容易だし、移動回数が少ない分だけ速いんじゃないかと思った。

が、が、実際にはどうだろう。

• 素数の2乗に足りない部分は欠落させておいても大丈夫そう
• だが、p人組内の確認は本当に速いのか?　これをほぽO(1)と見なせば良いんだが、実際にはO(p)だったりしないか?
  • だとすると、結局O(n) = O(p²)じゃないか。
• 操作が複雑な分だけ混乱を起こしそう
  • そこに不正な動きをする余地がある?
  • 互いに最初は信頼していなくても信頼の輪を広げられる、というのが趣旨だから不正を許すようでは意味がない?
• 仮定が成立する「十分小さいp」は精々が7じゃないかな?　だとすると、7×7=49で、オーダーを気にして複雑な操作をする意味があるか?

難しいね。と、3分ぐらい考えたことを書いてみた次第。このアイディア、絶対に既出で「捨てられた」ことがあると思う。公開鍵暗号を扱う人たちが巡回群を考えないわけないもん。

山なし落ちなし意味なし。