本ドキュメントはSoftwareDesign2002年11月号の原稿を元にHTMLドキュメント化 したものです。

国際暗号学会 CRYPTO2002カンファレンスレポート

すずきひろのぶ
hironobu @ h2np . net

2002年8月19〜22日米国カリフォルニア州サンタバーバラ市にあるUCSB(カリ フォルニア州立大学サンタバーバラ校)にて開催されたCRYPTO2002カンファレ ンス(国際暗号学会IACR主催)の様子をレポートします。

UCSB

以前は UCSB といってもほとんどの人はピンと来ませんでしたが、 今は「青色ダイオードの中村氏が日本を捨てて移った大学だ」といえば、 「ああ、なるほど」と気がつく読者も多いかと思います。

カリフォルニア州サンタバーバラ市はロサンゼルスから1号線を約80マイルほ ど北上したところにあります。ちょっと'80sのノリが入ってしまいますが、カ リフォルニアのイメージというとイーグルスの"ホテルカリフォルニア"の ジャケット写真 のように太陽とビーチとパームツリーのイメージがあります。サンタバーバラ は、あのジャケットのイメージそのままの場所です。

カリフォルニアといえば太陽が燦々と輝きいつでも薄着十分という気がします が、寒流が沖に流れる海辺の街なので日が射さないと、とても半袖ではいられ ないくらい気温が下がります。特に夜は、厚手の上着がないと外に30分といら れません。 今年は例年になく 天候が不順で、日中でもトレーナーが必要なほどでした。 長袖は機内で着る分しか持っていかなかったので、あわてて大学生協で トレーナーを購入したほどです。「いやー、思ったより寒い所ところですね」とレジ のおにいさんに話し掛けたところ「いつもは違うけど、ここのところの天気は ちょっと寒いんだ」とのことでした。 猛暑の東京で既に体力が落ちていたところに、急に寒いところへ来たもので体 調を崩し、カンファレンスの期間、大変辛い思いをしました。

CRYPTOカンファレンス

IACR (International Association for Cryptographic Research)はその名の通り暗 号研究をする者たちの国際的な連帯組織、短く言えば国際暗号学会のことです。

  • URL http://www.iacr.org

    年に4回ほど大きなカンファレンスを行いますが、そのなかで最も大きいカン ファレンスがコンピュータ産業の中心地カリフォルニア州で行なわれるCRYPTO カンファレンスです。開催期間中、参加者は大学キャンパスに缶詰になります。 多くの参加者は大学内の質素な寄宿舎に泊まるので、まるで合宿のような雰囲 気です。主催者発表によれば参加者は445名とのことです。カンファレンスの 内容はアカデミックな研究のみで、今年は39本の論文発表と2つの講演があり ました。ちなみに投稿された論文総数は175本です。論文も、暗号研究のほと んどの分野を広くカバーしており、CYRPTOに来ると最先端の暗号研究がどこま で進んでいるかよくわかります。さらに暗号というより数論の論文といった方 が良いようなものも何本かありました。たとえばある論文の著者すべてが数学 科の研究者のみというのがあります。

    全体のセッションスケジュールは次のようなものです。1つのセッションには 2,3本程度の発表が含まれています。

  • 1日目: Block Cipher, Multi-user Oriented Cryptosystem, Invited Talk, Foundation and Methodology, Security of Practical Protocols, Secure Multiparty Computation. (夜レセプションディナー)

  • 2日目: Public-Key Encryption, Information Theory and Secret, IACR Distinguished Lecture, (午後はなし), Rump Session

  • 3日目: Cipher Design and Analysis, Elliptic Curves and Abelian, Password-based Authentication, Distributed Cryptosystems, Pseudorandomness and Applications, Variations on Signature and Authentication, IACR Member Meeting, (夜バーベキューパーティー・Crypto Cafe)

  • 4日目: Stream Ciphers and Boolean, Commitment Schemes, Signature Schemes
  • 講演

    量子情報処理からみた量子暗号技術

    Invited Talkは最先端の暗号技術などに関する招待講演です。本年度は情報理 論の大家であるプリンストン大学のAndrew Chi-Chih Yaoが"New Directions in Quantum Cryptographic Protocols"というタイトルで講演を行いました。 内容はQuantum Information Processing (量子情報処理) からみたQuantum Cryptography(量子暗号技術)についてです。Yaoは情報理論の大家なので、暗 号研究の分野では彼の論文が大量に引用されていますが、彼自身は暗号研究を しているわけではないので、まったく CRYPTOなどには顔を出しません。今回、 生A.Yaoを見ることができてとてもラッキーでした。

    Quantum Cryptographの歴史は意外と古く、1970年に既にCash(電子キャッシュ) のアイデアとして使われています。これはもちろん概念でインプリメントはさ れていません。1984年にKey Distribution(鍵配送)のアイデアが出ています。 ちなみに世間で「量子暗号」という訳語が使われる時、多くは、この鍵配送の ことを指しています。

    1995年にBit commitmentのアイデアが出ています。古いにはふるいのですが、 約25年 間に主要なアイデアは3つしかありませんでした。ところが、1998年か ら2002年の今日 にいたるたった4年間で因数分解のアイデア、電子署名法、秘 密情報共有、Quantum Interactive Proof(QIP)などなどの新しいQuantum Cryptographyのアイデアが次々に 現われています。ここのところ、ちょっと したラッシュでした。A. Yaoは講演の最後をこうまとめています。

  • 量子暗号技術は量子情報処理研究をさらに拡張した世界の一角を成すもので ある。

  • 量子暗号技術はどの程度実用的なものになるかはすさだかではない。(もっ とも使 えそうなのは量子鍵交換である)

  • 量子法則は暗号技術に新しいエキサイティングな領域を与えるものである。 数々の 公開問題への挑戦が解決されていない。

    つまりまったく新しい概念を使う未開拓な分野で、この分野では手がつけられ ていな い問題がたくさん残っているというわけなので、今、研究者を目指し ている人たちは どうですか?あらたな金鉱を掘りにいきませんか?もしかする と、あなたの業績が未 来永劫この分野で残るかも知れませんよ!!

    未開拓なのは研究だけではなく、報道するメディア側もいいかげんで、 Quantum Cryptography(量子暗号技術)もKey Distribution (量子暗号)も Quantum Computing(量子コンピュータ)もよくわかっていなくて、Quantumとキー ワードがつけば同じようなもんだと思っているレベルのひどいものです。

    プライバシ保護と電子投票

    もう1つの講演であるIACR Distinguished LectureはDavid Chaumによる"A Survey of Security Without Identification"です。Chaumはプライバシーを 考慮した認証技術の創始者ともいえる人で、電子投票などは彼が引っ張ってき た分野です。そのモチベーションは、べつに電子投票の特許をとって金をもう けようという卑しいものではなく、「プライバシーをきちんと保護した上で、 正しい権利を主張できる方法」という人権と民主主義を守るため暗号技術はど う使うことができるかといった崇高な理念が根源となっています。

    住民基本台帳法の問題が日本で話題になっていますが、これらの技術をきちん と使えば、自分のプライバシーを保護しつつ、本人である証明ができます。ま あ住民基本台帳システムは国民を管理するために全国民にデータベースのマス ターインデックスをつけるというのが目的ですから、たとえこのようなプライ バシー保護技術があっても関係ないでしょうけれども。

    個人的に興味を持った発表

    本年度は、あまり興味を引かれる発表はありませんでした。Antoine Jouxらに よる"Blockwise-Adaptive Attackers Revisiting the (In)Secure of Some Provably Secure Encryption Modes: CBC, GEM, IACBC"の発表は、いくつかの 暗号モードの安全性に関しての分析で、広くつかわれているCBCモードの攻撃 法を示してい ます。AES選出が終わった後の NIST 暗号モードのワークショップ を開催していて、今後、暗号モードの見直しや安 全性基準が改定されるだろう という流れの中で、このような論文が現われる ということは、かなりインパクトのあることではないかと思われます。

    Sean Murphyらによる"Essential Algebraic Structure within the AES"とい う研究 は、暗号技術の歴史に足跡を残す日本人研究者(名前を載せて良いか聞 くのを 忘れただけで、こう書いておきます)が教えてくれたことには、この研 究の先にAESへの有効な攻撃が見つかるかもしれないとのことです。この論文 はAESの代数的構造を深く掘っている内容ですが、この時点では筆者はまった く発表の意図がわかりませんでした。まだ攻撃法を明確に示せる段階ではない が、かなり突っ込んだ所まで研究は進んでいるのではないか、という印象をもっ たそうです。AESの128bit版は以外と寿命が短いかも知れない、という可能性 も否定できないとのことです。

    ランプセッション

    CRYPTOのランプセッションは、2日目の夜に開催される"非公式"な発表の場で す。発 表したい人は前日の午後までに申し込めば、運がよければ発表できる という場で、夜の7時30分スタートで11時過ぎまで一人4分程度の持ち時間でど んどん発表していきます。いつも後ろに時間がずれて、最後は何時が終了にな るかわかりません。筆者は最後まで付き合っていられないので、いつも10時ぐ らいに部屋に戻って寝るので最後がどうなっているかは一度も見たことがあり ません。最後は発表待ちだった人すらも既に帰っているというウワサもちらほ ら聞きます。面白い話は10時前に割り振っているので、10時ぐらいまでいれば 大体、今年の面白いネタは聞けるということになっています。

    どんな発表があるかというと

  • 各種カンファレンスやシンポジューム、ワークショップの案内
  • 論文に入らなかったが面白いネタ
  • 論文が通らなかったけど発表したいネタ
  • 今、研究中のネタ
  • わざわざ論文にするほどでもないけど、聞けば面白ネタ
  • まったくのエンターテイメント

    というようなことが一般的です。

    Palladium / マイクロソフト

    今年は、さらにマイクロソフトからPalladiumという 新しいTrusted Computing Frameworkの紹介にJohn Manfedelli責任者がやってきて7分もの時 間枠を押えて説明していました。最後にいくつか会場から質問が飛んだのです が、どれもちょっと刺のある質問ばかりで、マイクロソフトってオープンソー スな人たちだけじゃなく、あちらこちらで嫌われているんだなぁ、とあらため て感じました。

    ふとランプセッションのスケジュール表をみるとマイクロソフトの発表者の欄 に名前に見覚えが。92、3年ごろMITでPGP Keyserverに関連していた人の名前 があったのです。動かしたり、同期を取ったり、デバックしたりして、何度も 何度もメールを送りあった相手ですが、一度も顔をあわせたことがありません。

    その人を見つけたので声をかけました。「すずきひろのぶだけど、もしかして 93年ごろにMITにいた方ですか?僕の名前を覚えています?」声をかけるとき最 初はちょっと不安でしたが、相手も筆者のことを覚えてくれていて「いや10年 経って始めて顔を合わせるなんてね」なんていう話をしていました。少し話を したところで、名刺交換。彼はマイクロソフトのPalladiumの研究開発スタッ フとなっています。筆者は本業の名刺のほかに、最近、活動を始めた Free Software Initiative of Japan の名刺を出しました。 むかしはお互い「暗号技術は政府の支配を離れ人々に 開放されなければならない」などと青臭いことを言い合っていたわけですが、 それから10年経ち、一方はマイクロソフトに、もう一方はフリーソフトウェア という、この業界でもっとも敵対する立場同士になっていて...ちょっとため 息がでます。

    話を元に戻しましょう。Palladiumの全体構造をざっとみると、ハードウェア レベルからのプロテクションが可能になります。かなり強力な計算資源に対す る排他アクセス、耐タンパー機能といった通常のオペレーティングシステムだ けでは実現できないセキュリティが構築できます。しかし、これには別の見方 ができて、たとえばハードウェアベンダーがその機能をブラックボックス化し、 そのAPIを特定のベンダーのみに提供するような状況になれば、それ以外のフ リーなオペレーティングシステムがまともに載せられなくなります。Wintel陣 営という皮肉がありましたが、それ以上のソフトウェア・ハードウェア同士の 結びつきが可能となり、その結びつき以外のオペレーティングシステムの排除 に繋がる危険性があります。動向に注意する必要があるでしょう。

    素数判定

    今年は珍しくInvited Talkがありました。"Polynomial-Time Deterministic Primarily Test"のネタでDan Bernstein が説明しました。これは多項式時間 で決定性の素数判定を効率的に行うアルゴリズムでつい最近、インドの数学者 グループが発表したものです。一般には、大きな数の素数判定は確率的な方法 を用います。計算は速いのですが、わずかな確率で素数と判定されたにも関わ らず、素数ではない可能性があります。このような偽判定になってしまう数を カーマイケル数といいます。しかしながら2^1024といった大きな数の素数判定 で偽判定がでる確率はあまりにも小さく実質的には無視できるレベルなので、 この決定性の素数判定は現実的には今後も使われることはないでしょう。しか しながら、今回発見した決定性の素数判定は、驚くほどエレガントなもので、 この業績はすばらしいものです。あちこちで報道されたので筆者もWebサイト からそのアルゴリズムの論文をダウンロードしたのですが、21世紀に入っても まだこのようなエレガントな方法が見つかるということに驚きを感じました。 別の表現を使えば我々人類は素数1つ取っても、我々の到達した知識というの は僅かなものなのだということです。

    役に立たない暗号あれこれ

    カリフォルニア州立大学バークレー校のDavid Wagnerは、2つの面白いネタを 提供してくれました。1つはt-bit OFBやCBFモードで0になれば、あとは出力が 0になるという(つまり、暗号として役に立たない)ごく当たり前のことを指摘 したのですが、考えてみれば誰もこれを過去に指摘した人もなく、また、この 実装をしているソフトウェアは存在しそうで、なるほどな、と思わされました。 もう1つはAPONというATMベースのネットワークで使っている暗号のことを紹介 したのですが、これが暗号技術を知らない素人が作ったような2回のパッドを 当てるだけのインチキな方式で、たった256回鍵を試行しただけで解読できて しまうというお笑いなシステムなのです。Wagnerが「実は暗号はこうなってい て」とOHPを出した瞬間から、あと終わるまで爆笑につぐ爆笑でした。

    エンターテイメント系発表

    今回のランプセッションだけではなく、筆者がかつて見たエンターテイメント の中で最高傑作ともいえるネタが今回Jean-Jacques Quisquater(短くJJQ)が行っ た"In search of snake oil: A rump CHESsion"です。JJQはヨーロッパの重鎮 です(筆者は影で「死神博士」と呼んでいます。だって仮面ライダーの死神博 士に似ているんだもん)。

    CRYPTOに来ているなら誰でも知っているような有名人を密かにデジカメで取り、 そこに強烈な一言吹きだしをいれます。ちなみにSnake Oilとはインチキ暗号 のことです。Applied Cryptographyで有名なCounterpaneのBruce Schneierが 誰かと会話している写真に"今度Applied Snake Oilを書こうかと思うんだ"、" そいつは売れるぜ"といった皮肉を書いています。「こりゃ重鎮JJQじゃなきゃ 殴られるよな」というようなネタのオンパレードでした。 Philip Zimmermannの吹きだしは"NSAはPGPにSnake Oilを入れろといってきた"。 NISTの人は"Snake Oilは、おっと失礼AESでしたが、"。ノートパソコンを使っ ている人の写真には"Snake Oilのビジネスモデルの企画を云々、あ、でもまず はsnakeoil.comを取らなきゃ"、などともうやりたい放題って感じで、会場は 大爆笑につぐ大爆笑です。

    いつも質問がキツイのを見て、JJQには厳格で真面目なイメージしかなかった のですが、今回のモンティパイソンも真っ青な毒舌なエンターテイメントをみ て「実はJJQって、そんなオチャメな人だったんだ」と認識を改めた次第です。

    4DES

    あと面白かったのはCounterpaneに在籍している日系の Tadayoshi Kohnoの発表した4DESです。2つの鍵を使った3DESは強力である。そ こで2の鍵を使った4DESはさらに強力であるというものです。ランダム性をチェッ クするために、大きなランダムブロックxを用意し4DESで処理したところ、そ の出力はランダムテストをパスすることが証明できています(よく考えてくだ さいね。これはエンターテイメントですからね)。

  • 3DES の構造 Ek1(Dk2(Ek1(x)))
  • 4DESの構造 Dk1(Dk2(Ek2(Ek1(x))))

    おわりに

    CRYPTOは発表を聞くだけではなく、そこに集まる人たちの情報交換の場です。 2002年8月19日夜のレセプション会場で、筆者はPhilip ZimmermannやPGP関係者に対 し筆者の開発しているPGP鍵サーバOpenPKSD(openpksd.org)の話をしていました。 部屋にもどって、メールを読むと PGP Corpという新会社がNAIからPGPの権利を 買い取り、開発を続けるという内容。 しかも、その会社の経営陣にはさっき話していた Jon Callas が最高技術責任者として入っているではないですか!

    PGP CorpのWebサイトをみると8月19日づけのプレスリリースのみがあるだけで すから、たぶん19日づけで立ち上がったのでしょう。後日そのメールのことを Callasに言うと「CRYPTOの期間、そればっかり言われているよ」と笑っていま した。

    おしまい