Title Author(s) Citation Issue Date Type インターネット・セキュリティの原理 : 公開鍵暗号系とゼロ知識証明山崎, 秀記一橋論叢, 125(4): 447-461 2001-04-01 Departmental Bulletin Paper Text Version publisher URL http://hdl.handle.net/10086/10415 Right Hitotsubashi University Repository （131）インターネット・セキュリティの原理一公開鍵暗号系とゼロ知識証明山崎秀記 1 序論多くの人が電子メールを利用している．ときには当事者以外には秘密にしたい情報を電子メールでやりとりしたくなることもあるだろう．また，アンケートに答えるときの個人情報や・買い物の苧きのクレジットカード番号など，他人に知られたくない，知られてはまずい情報をインターネット上で入力する必要があることもある．これらの秘密情報をインターネット上で安全にやりとりするためには，送信した相手以外に内容を解読されることを防止する暗号化や，情報が第3者による偽造でないことの確認（認証）が必要である．例えぱ，URLが“https”で始まるインターネット・サイトでは，やりとりする情報を他人が盗み見ることを防ぐ処置が講じられている．これらは，セキュリティで保護された「安全な」サイトと呼ぱれ，最近のブラウザは，安全なサイトで使われているセキュリティ・プロトコル（情報交換のための手順を定めた規則）をサポートしている．実際，インターネット上で，安全なサイトと安全でないサイトの間を移動したり，安全でないサイトにデータを送信しようとしたりするときに，ブラウザに「警告メッセージ」が現れるの経験することも多い．また，最近のメールソフトには，暗号化やデジタル署名などの機能がついており，メッセージを暗号化したり自分（メッセージ）の身元を証明したりできる．ところで，これらの暗号化や認証はどのような仕組みによっているのだろうか．普通我々が思い浮かべる暗号といえぱ，通信する二人が互いに秘密の「鍵」を共 447 （132）一橋論叢第125巻第4号平成13年（2001年〕4月号有し，その鍵を知るものだけが暗号文を作成したり解読したりできるようになっている．だカ）ら，その「鍵」の保持・入手をめぐってスパイが活躍する，というわけだ．ところが，インターネットで暗号通信を行うのはまったく見ず知らずの者どうしである．いったいそんなことが可能なのだろうか．また，身分を証明するときは運転免許書や身分証明書を提示し，書類の正当性を保証するときは実印に印鑑証明書をつけて利用する．それらが有効なのは，公正な第3者機関によって保証されたもので，なおかつその偽造（コピー作成）が困難だからである．しかしインターネット上のデジタル情報は，完全なコピーを作成することがいともたやすい．それなのにどうして，他人に詐称されないような身分証明が可能なのだろうか．その原理には，「計算の複雑さ」に関する計算機科学の理論が深く関わっており，また，素因数分解という我々もよく知っている概念が利用されている．この原理を応用すると，インターネット上での暗号化や認証だけでなく，次のような手晶みたいなことが可能になる． l1〕電話でのコイン投げ離れたところにいる二人が電話でコイン投げをする．互いに相手が見えない状況で，片方がコインを投げもう一方がその裏表を当てることで物事を決める（のと同等の）ことができる． 12〕電話でのポーカー 11〕と同じ状況にいる二人が，公正な第3者の介在なしにポーカー（トランプゲーム）をすることができる．（3）金持ち比べ相手に自分の資産額を知られることなく，どちらが金持ちか，資産額を比較した結果だけを（公正な第3考の介在なしに）知ることができる．（4〕電子投票投票の一覧が公表されて，各自は自分の投票が正しく扱われたことと集計結果の正しさを確認できるにも関わらず，投票の秘密は守られる（一覧表からは自分の投票と集計の正しさしかわからない）． 448 インターネット・セキュリティの原理（133） 15〕ゼロ知識証明ある「情報」を知っていることを，その情報について何も漏らすことなく相手に納得させることができる．ここでは，現在のインターネット社会を支える暗号技術の基礎となる原理の簡単な紹介を試みることで，さまざまな不思議にあふれた計算機科学の一端を紹介してみたい． 2 コイン投げプロトコル最初に，コイン投げを実現するプロトコル（情報交換の手順）を考えてみよう．例えぱ次のような状況を考えてみる．離婚した二人，ヒデキとヨシコが，最愛の一人娘をどちらが引き取るか，コイン投げで決着をつけることにした．もう顔を合わせたくない二人は電話だけですませたい．どうすれぱよいだろうか．もちろん，これほど深刻な例でなくても，恋人同士のヒデキとヨシコが今日のデート場所をディズニーランドにするか府中競馬場にするか電話で決める，というのでもよい．これを解決するいろいろなプロトコルが考えられる．まず，簡単なプロトコルから紹介する．コイン投げプロトコル1：二人が同じ電話帳を持っているとする．ヒデキ：（電話帳で適当に選んだ人の電話番号を見ておく）電話番号がOユ2− 345−6789の人は山田太郎か田中］郎かP ヨシコ：田中一郎．（すぐに答えなけれぱならない！！〕ヒデキ：残念，山田太郎でした．僕の勝だ．ヨシコ：（電話帳で確認する）確かに私の負けね．このプロトコルがうまく働くのは次のような理由による．電話帳を持っていても，ヨシコが電話番号から所有者名を短時問で割り出すのはまず不可能である．頭から順に調べていったのでは，たとえできるにしても，ひどく時問がかかる． 449 （134）一橋論叢第125巻第4号平成13年（2001年）4月号ヨシコがその電話番号の持ち主をたまたま知っているとか，電話帳の目に付いたところにその電話番号があった，などということは，万に一つもないだろう．ヨシコはすぐに答えなけれぱならないので，当てずっぽうで答えるしかない，という点が重要である．もうひとつ重要なのは，ヨシコはヒデキがずるしてないことを容易に確かめられるという点である．ヒデキの答えが正しいが否かの検査は，名前から電話番号を調べることだから，電話帳があれぱ簡単にできる．ヨシコは，電話帳がなくても実際に電話をかけて確かめることもできる．しかし，知らないお宅に「あなたは誰ですか」などという電話をしたら，怒られてしまうだろう．さて，電話帳がない場合，次のプロトコルはどうだろうか．コイン投げプロトコル2：素因数分解を使うヒデキ：（；つの素数233，149を選び，その積34717を計算しておく）34717を素因数分解したとき，一番大きな数の上から2桁目は偶数か奇数か∼ ヨシコ：奇数．（すぐに答えなければならない！！〕ヒデキ：あたり．34717は233掛ける149だから，君の勝だ．ヨシコ：（233，149が素数で，34717＝233×149となることを確認して）やった．確かに私の勝だわ． 34717の素困数分解を直ちに求めることは，普通の人にはまず不可能なので，やはりヨシコはあてずっぼうで答えるしかない．また，ヒデキがずるしたときに，ヨシコがそれを容易に見破れる点もプロトコル1と同様である．これら2つのプロトコルでは，ヒデキはヨシコに，ある種の（二者択一）問題に直ちに答えるよう要求している．その問題は，通常，ただちに答えることが難しいので，ヨシコは当てずっぼうで答えるしかなく，コインの役割を果たせるというわけである．しかし，その問題は（最後にヨシコが確認できるように），示された答えの正しさがすぐに確かめられるような問題でなけれぱならない．整理すると，ヒデキがヨシコに出す問題は， 450 インターネット・セキュリティの原理（135） ①問題を作るのは容易（答えから問題を作っている事に注意！） ②問題を解くのは困難 ③答えを示されたら，それが正しいことを検証するのは容易という性質を持っていなけれぱならない．ここでは，容易というのは直ちに（時間をかけずに）できるという意味で，困難というのはできるのに時問がかかる，というぐらいに解釈しておいて欲しい．上の例に使われた，「電話番号からの名前調ぺ」や「素因数分解」はそのような問題だったというわけである．ところで，上に述ぺた②の性質（他の性質も）は，解答者（ヨシコ）の計算能力に密接に関係することに注意しておこう．5桁の数の素因数分解は，普通の人が紙と鉛筆だけでやるのは難しいだろうが，ヨシコが暗算の天才（因数分解の天才∼）だったらすぐに34717の素因数分解を計算できてしまうかもしれない．そうでなくても，ヨシコのそぱにパソコン（と素因数分解のプログラム）があれぱ， 34717の素因数分解ぐらい一瞬のうちに計算できてしまうだろう．プロトコル1でも，仮にヨシコがNTTの電話番号案内係でしかもその仕事中だったら，電話番号からその所有者を求めるのは，いともたやすいことに違いない．目の前のキーボードを叩けぱ，すぐに所有者名がディスプレーに現れることだろう．では最後に，ヨシコが暗算の天才だろうが，スーパーコンピューターを持っていようが大丈夫なプロトコルを紹介しよう．今度はヒデキもパソコン程度の助けは必要になる．コイン投げプロトコル3：100桁の数の素因数分解を使うヒデキ：（50桁の素数力とσをでたらめに選び，その積Wを計算しておく．力くσで力の4桁目は奇数だとしよう．）〃の最小素因数の上から4桁目は偶数か奇数か？ヨシコ：偶数．ヒデキ：残念でした．〃は力掛けるσだから，答えは奇数だよ．ヨシコ：（ヵ，σが素数で，w＝〃となることを確認して）確かに私の負けね． 451 （136）一橋論叢第125巻第4号平成13年（2001年）4月号プロトコル2との違いは単に桁数が増えただけである．前に述べたように，次のような性質が成り立たなけれぱならない． ①50桁の素数を選ぶことや50桁の整数の掛け算は（パソコンを使えぱ）容易 ②100桁の数の素因数分解は（スーパーコンピューターを使っても）困難 ③与えられた数が素数か否かの検査（とその積の計算）は（パソコンを使えぱ）容易実際，①と③は，ここでは詳しくは述べないが，速いアルゴリズムがすでに知られていて，パソコンでも1分とかからずにできる．②に関してはどうだろうか．プロトコル2では5桁の数の素因数分解が，パソコンを使えぱたちどころに可能だと述べた．ところが，桁数が多くなるとそうはいかないのである．議論を簡単にするために奇数の合成数（素数でない数）だけ考えることにしよう．奇合成数1Vの素因数分解を求める素朴な方法は，3，5，7，…という奇数で順に，割れ切れる限り〃を割る，という方法である．例えぱ次のようなプログラムになる．伽←3；（変数刎に3を代入する〕（閉＜〃）の間は括弧内を繰り返す｛（〃が閉で割り切れる）間は括弧内を繰り返す｛伽を〃の素因数として書き出す： 1V←〃÷刎；（Wを刎で割る〕｝刎←刎十2：（〃を2増やす〕｝この方法で，〃を素因数分解するための計算時間は，最悪，恢までの奇数で〃を割ってみることになるので亙，つまり河に，比例する．鵜プロトコ 2 ル3で使ったWはほぼ最悪の場合になっている．これはWの桁数を〃とすれぱ， 1O姜に比例する時問がかかる．このことはWの桁数が10増えれぱ計算時問は 100000倍になることを意味する．桁数が20増えれぱ，10m＝100億倍，40増えれぱ1020倍になる．いくらスーパーコンピューターを使っても（素朴なアルゴリズ 452 インターネット・セキュリティの原理（137）ムでは）手に負えない理由がお分かりいただけただろうか．では，素因数分解を計算する速いアルゴリズムはないのだろうか．・素数についてはユークリッド以来約二千隼もの間その性質が調べられているが，素因数分解の（素朴なアルゴリズムより本質的に）速いアルゴリズムは，いまだに知られていない．実際，1994年に後で説明するRSA暗号が破られたときには，129桁のある数の素因数分解に，世界中の600人に及ぶ研究者が協力して数百台のスーパーコンピューターを使い，8ヶ月かかったという．残念なことに，素因数分解が本当に難しいということの数学的証明はまだ得られていない．もしこのことが証明できれぱ，ノーベル賞ものである（数学にはノーベル賞はないが，それに匹敵する賞が貰えることは確実）．実際，この問題は「P≠NP問題」という計算機科学の有名な末解決問題の解決につながる問題で，100万ドルの賞金がかかっている（http：／／www．claymath．org／）． 3 一方向関数と公開鍵暗号系インターネット上で使われている公開鍵暗号系の説明に入る前に，少し言葉の定義をしておこう．普通，関数とはある数から別の数への対応関係をいうが，ここでは必ずしも数にこだわらずに，一般にある物からある物への対応関係を関数．と呼び，その対応関係を求めることを関数の計算という．また，考える関数は議論を簡単にするためにすべて1対ユ対応の関数だとする．関数Fがαにろを対応させる，つまりF（α）斗のとき，5にαを対応させる関数をFの逆関数といいF−1で表す．つまり，F（α）＝あならF■1（ろ〕＝o．この切から（F（α）＝あとなる）ろを求めることを逆元（逆関数）の計算という． 2節のコイン投げプロトコルでは，「名前に電話番号を対応させる電話帳関数」や「（素数の）積」のように，それ自身の計算は容易だが，逆元（逆関数）の計算は困難だという関数を利用していた．このような関数を一方向関数という．一方向関数の実際的な応用として，パスワード管理がある．パスワードの照合を行うには，利用者のパスワードをどこかのテーブルに保存しなけれぱならない．しかし，パスワードをそのままテープルに保存したのでは，それを誰かに見られ 453 （138）一橋論叢第125巻第4号平成13年｛2001年）4月号たとき危険である．そこで，パスワードに一方向関数を適用した結果を保存しておき，入力されたパスワードに一方向関数を適用した結果と比較する・ということが行われている．こうすれぱ，照合テーブルを見られても，逆関数の計算は困難なので，もとのパスワードは分からない．一方向関数を暗号に応用することを考えてみよう．もとの文（平文という）を暗号文に対応させる関数を晴号関数，その逆関数，暗号文を平文に戻す関数を復号関数という．受信者送信者暗号文←復号関数→平文（暗号関数の逆関数〕この暗号関数に一方向関数を使うのである．電話帳関数を使う場合なら，電話帳の「あ」で始まる人の電話番号（のどれか）を使って文字「あ」を表す（平文はすべて平仮名だとする）．こうして得られた暗号文（電話番号列）を復号するには逆関数を計算しなけれぱならないので，ぱくだいな時間がかかる．したがって，暗号関数を公開しても暗号が破られることはなく安全である．しかしこれでは，暗号の正規の受信者も解読できないことになってしまう．受信者は，例えぱNTTの番号案内係のように，特別の情報（復号鍵）を持っていて，それを利用すれぱ，簡単に復号できるとい？のでなけれぱならない一（実は，電話帳方式はあくまで説明のためにあげているだけで，暗号としては失格である．復号鍵を多くの人が持っている暗号など役に立たない！）まとめると，暗号に使うには，一方向関数であるという条件に加えて，逆関数の計算は「鍵」を知っていると容易，という条件を付け加える必要がある．このような関数を個人用一方向関数という．個人用一方向関数の条件 ①関数の計算は容易 ②逆関数の計算は「鍵」を知らなけれぱ困難 ③逆関数の計算は「鍵」を知っていれば容易 454 インターネット・セキュリティの原理（139）では，暗号関数に個人用一方向関数を使うと，どんな利点があるのだろうか．それは「鍵」さえ秘密にしておけぱ，暗号関数を公開しても暗号は安全だという点にある．暗号関数に個人用一方向関数を使い，暗号関数を公開する暗号のことを公開暗号という．公開暗号では，暗号文を受け取りたい人は，自分宛の暗号の暗号関数を公開し，復号のための「鍵」は秘密にしておく．Aに暗号を送りたい人は（誰でも，Aの知人でなくても），公開されているAの暗号関数を使って暗号を送れぱよい．「復号鍵」を持っているのはAだけなので，他の人に解読される心配はない．このアイディアがいかに画期的かは，あらかじめ共通の鍵を秘密裏に交換しなければならない通常の暗号方法と比べてみれぱ明らかだろう．ところで，それぞれがまったく違う方式で公開暗号を作成するのでは不便でしかたがないし，ただ，個人用一方向関数を作りなさい，といわれても困ってしまうだろう．やはり，なにか共通の暗号生産方式があって，適当なパラメータを定めれぱ暗号（関数）が定まるというようにしたい．このような暗号の大量生産方式を暗号系といい，暗号系にぞくする暗号（関数）を定めるパラメータを暗号鍵という．整理してみよう．次の条件をみたす暗号生産システムを公開鍵暗号系という． ①暗号鍵を定めると暗号（関数）が容易に定まる ②暗号関数の計算は容易 ③暗号関数（の計算法）を知っていても，復号（関数の計算）は困難 ④復号鍵を知っていれぱ，復号は容易暗号鍵（暗号関数）を公開しても復号鍵を秘密にしておけば暗号が安全なのは前に述べた通りである．公開鍵暗号系のアイディアはアメリカのDiffieとHell− manによって1976年に発表された．彼らの暗号系は不完全だったが，1978年， Rivest，Shamir，Adlemanの3人は，RSA暗号系という，現在一般的にも使われている公開鍵暗号系を発表した．3人は最初，公開鍵暗号系など不可能だと思っていたらしい．公開鍵暗号系が不可能であることの証明をあれこれ考えているうちに，それを実現してしまったというのだからおもしろい．ではRSA暗号系を説明しよう．簡単のために，平文と暗号文はともに（例え 455 （140〕一橋論叢第125巻第4号平成13年（2001年）4月号ぱ100桁以下の）数としよう．平文がローマ字なら，A：01，B：02，…のように，文字を2桁の数で符号化し，50文字（100桁）ずつのブロックに区切って暗号化すれぱよい．以下の説明でmodという演算が現れるが，πmod yはπをyで割った余りを表す．また，素数力，ρは，その積〃＝〃が100桁を越えるように，それぞれ51桁の素数だとする．暗号鍵と復号鍵の選ぴ方 2つの素数ヵ，σを選び，ヵ一1とσ一1の最小公倍数Lと互いに素な数2を選ぶ．（ε，W）が公開する暗号鍵である．このようなLとθに対して，1＝1二c＋θ∂を満たすo，ゴが存在する．この6が復号鍵である．暗号関数，復号関数の定義暗号関数は，RSA哩．。〕（〃）＝〃壇mod〃，復号関数は灰M由〕（C）＝Cd mod〃である．例．簡単のために，2つの素数力＝149，ρ：233を選んだとすると，力一1とρ一1 の最小公倍数はL＝8584．それと互いに素な数ε＝101を選べぱ，一（101．34717）が公開する暗号鍵である．このLと召に対して，1＝一8584＋101・85なので6＝85 が復号鍵である．したがって暗号関数は，R∫λ（〃）＝〃ml mod34717，復号関数はRM■1（C）＝α5mod34717である．このとき，例えぱ文字列ABを符号化した0102に対し，RSλ（0102）：34507，RS片1（34507）＝0102となる．復号関数の正しさを証明しよう1まず〃L mod〃＝1を証明する．数論でよく知られたフェルマーの小定理より力，σが素数のとき，〃ρ一Imod力＝〃q■lmod ρ：1が成り立つ（証明は省略）．したがって〃止一1mod力＝〃」1modσ＝O．ヵ， ρは素数だから〃L−1mod〃＝0である1〃＝〃だから，”mod〃＝1．したがって，灰∫λ壱〃〕（灰Sλ｛ε．州（〃））二〃値dmod〃＝（〃・〃芭d−1）mod〃＝（〃・〃一止‘）mod〃＝（〃・1−c）modW＝〃mod〃＝〃である．つぎにRSA暗号系の安全性はどうだろうか．復号鍵を知らない人が，Wの因数分解をせずに暗号を解読（復号）する方法は知られていない．実際，2節で述 456 インターネット・セキュリティの原理（141）ぺたRSA暗号（のひとつが）破られたときも，Wを因数分解するという正攻法（P）が使われ，wの因数分解にはとてつもないコンピューターパワーと時間を必要とした．誤解しないで欲しいのだが，RSA暗号の暗号鍵のひとつが破、られただけで， RSA暗号系が破られたわけではない．RSA暗号系はいまだに安全である（と信じられている）．まえの例はRSA暗号を破るのに，膨大なお金（コンピュータ資源〕と時間がかかることを例証したものだと見ることもできるのである．ただし，RSA暗号系の安全性の数学的証明がまだえられていないことは前に述べた通りである． 4 さまざまなマジックプロトコルこの節では，公開鍵暗号系（個人用一方向関数）を利用して得られるいくっかのマジックプロトコルを紹介しよう．（1〕デジタル署名，電子印鑑（復号関数の逆利用）暗号関数を公開しているAは，自分が作成した文書（平文〕〃に，署名として，〃こAの復号関数（！）を適用した結果を添付する．受信者は公開されているA の暗号関数を使って，署名を平文に戻して〃と一致することを確認する．Aの復号関数を計算できるのは復号鍵を知るAだけだから，確かにこの文書はAから送られたものだとわかる．そこで通常の印鑑登録と同じように，暗号関数（個人用一方向関数）を役場などの公正な第3者機関に登録しておけぱ，これが実印代わりなる．（2〕金持ち比ペプ1コトコルこれは金持ちの二人A，Bが，相手に自分の資産額を知られずに，しかもその大小だけを比較するとというプロトコルである．もちろん二人は正直（資産額を偽らない）でなけれぱならないので，状況としては少し不自然かもしれない．しかし，互いに手の内は見せずにどちらが有利かだけを判定したいときなどに，応 457 （142）一橋論叢第125巻第4号平成13年（2001年）4月号用できるだろう．以下はAがBとの金持ち比べの結果を知るためのプロトコルである．BがAとの金持ち比べの結果を知りたいときは，AとBを交換して同じ事を繰り返せぱよい．記述を簡単にするために以下，Bが公開している暗号関数をBで・Bだけが計算できるその逆関数をろで表す．第1ステップ：Aの作業．Aの資産をπ億円とする． Aは適当に数プを選び，2＝8（γ）十πをBに伝える．第2ステップ：Bの作業．Bの資産はツ億円で，y＜10とする． ①〃1＝あ（2−1），〃呈＝あ（2−2），…，伽＝5（2−y）を計算し，それと異なると1O−y個の〃甘一、，…，伽、。をランダムに選ぶ． ②〃、＝B（吻十1），…，砂、。＝B（〃m＋1〕をAに伝える．第3ステップ：Aの作業．受け取った〃、，…，〃1。の中にB（γ十1）がなけれぱAがBより金持ち（π〉ツ）で，あれぱBの資産はA以上（π≦ツ）である．このプロトコルの正しさや安全性（A，Bともに相手の資産額がわからないこと）の確認は読者へのパズルとして残しておこう．（3〕ゼロ知識証明ゼロ知識証明というのは，自分が知っている秘密情報について，相手に知識を与えずに，なおかつ相手に自分がその情報を知っていることを証明する（納得させる）方法である．考えてみれぱ，l1〕で解説した認証プロトコルは，自分が公開している暗号の復号鍵を知っているということを，復号鍵についての情報をほとんど漏らさずに相手に納得させるということに他ならない．ここではグラフの3 彩色問題を使ったセロ知識証明を紹介しよう．今考えているグラフは，下図のように，頂点とそれを結ぶ辺から構成される図形である．3彩色問題とは与えられたグラフの各頂点を3色で塗り分ける（辺で結ばれた点が同じ色にならないようにする）問題である．有名な「4色問題」は平面上に書かれたグラフの4彩色が常に可能か，という 458 インターネット・セキュリティの原理（143）グラフとその3彩色 ○ 間題で，これはつねに可能であることが最近証明された．3彩色は与えられたグラフによってできたりできなかったりする．ここで詳しく述べる余裕はないが，グラフの3彩色問題は，解くのは難しく答えの検証は容易な問題（NP問題と呼ぱれる）の中でも，もっとも難しい問題であることが証明されている．したがって，グラフを与えられてその場でそれを3彩色して見せることは大きなグラフではまず不可能である．さて・Aが，あるグラフの3色（赤，青，白）塗りわけを知っていることをB に示すゼロ知識証明プロトコルは次のようになる．まずAは塗り分け前のグラフをBに渡しておく． ①Aはグラフの各頂点に対応して1枚ずつカードを用意し，その裏に対応頂点の色を書く． ②Bは辺でつながった2点を指定し対応するカードを裏返す． ③もし裏返したカードに同じ色が書かれていたり，赤，青，白以外の色が書かれていたりしたら，BはAが正しい答えを知らなかった，と判断する． ①∼③を適当回数繰り返しても，BがAの誤りを発見できなけれぱ，BはAの証明を受け入れる（納得する）．さて・AがBを欺くことのできる確率を計算してみよう．Aが答えを知らなけれぱ，どこかの辺では，端点に赤青白以外の色が塗られていたり，両端点が同じ色で塗られていたりするわけだから，Bがそれを発見できる確率は⊥（刎はグラ刎フの辺の数）である．言い換えれぱ，見逃す確率は（1一⊥）なので，これを〃回繰刎り返しても間違いを見つけられない確率は（1一⊥）＾である．刎 459 （144）一橋論叢第125巻第4号平成13年（2001年）4月号例えぱ閉＝13なら，椛＝60回も繰り返せぱ，その確率は0−0082…となり，1 パーセントにもみたない．欺かれる確率をもっと減らしたけれぱ，回数を増やせぱよいだけである．では，本当にゼロ知識なのだろうか．検証を繰り返しているうちに，Bがこのグラフの3彩色法に関する情報を少しでも得る心配はないのだろうか．これは，①∼③まで繰り返す点が重要である．つまり，繰り返しの度にAは新しいカードを用意し，色（赤，青，白）をランダムに入れ替えて，使う．その結果，Bは単に空けた辺の両端が同じ色で塗られていた，という以外の情報を得ることができない．与えられたグラフの3彩色法を知っていても，それがゼロ知識証明を要するような璽要な情報には思えないかもしれない．しかし実はほとんどの数学的証明が，なんらかのグラフの3彩色法に符号化できることが知られている．．したがって，驚くぺき定理1「素因数分解の早いアルゴリズムが存在する」ことの証明を幸運にもあなたが得たとしよう．あなたは，その証明の内容を漏らすことなく，証明を知っていることを相手に納得させることができる．そうすれぱ，あなたはその情報を某国の秘密情報機関に多額の金で売り渡すことができるだろう． 5 後書き公開鍵暗号系やさまざまなマジック・プロトコルを紹介してきたが，いかがだっただろうか．公開鍵暗号系のアイディアは，暗号鍵と復号鍵を分けるという意外とシンプルなものである．しかも基礎に使われている素因数分解の問題も・古くから研究されてきた．にも関わらず，このアイディアが発見されたのがこうも遅い（1976年）のはなぜだろうか．それは，問題を解くのに必要な計算の複雑さや計算時問を見積もる「計算量理論」が開発された（理論的基盤が整った）のがごく最近のこと（1960年代後半から）だからだろう．計算が「容易」，「困難」という概念も，実は「計算量理論」できちんと定義される． 460 インターネット・セキュリティの原理（145）「計算量理論」では，解くのが容易な（時間のかからない）問題を「P問題」と呼び，解くのは困難だが（速いアルゴリネムが知られていないが）解の検証は容易，という問題を「NP聞題」と呼ぶ．「NP問題」が本当に困難，つまり「P 間題」でないことを数学帥こ証明（あるいは反証）することは，序論でもふれたように，100万ドルの懸賞のかかった，計算量理論の大未解決問題である．読者の中には「NP問題」と「一方向関数」の類似性に気付かれた方も多いだろう．実はその一方向性を数学的に証明された一方向関数はまだ見つかっていない．そのような一方向関数（とその数学的証明）を見つけることは，とりもなおさず未解決な「P≠NP問題」を解決することに他ならない．「計算量の理論」，さらに一般的に「計算機科学」は，現代のインターネット社会を支える基本学問として，多くの若者の参加を待ち受けているぱかりでなく，マジック・プロトコルに見られるような多くの不思議にみちた世界でもある．さらに実世界に応用可能な新しいプロトコルを発見すれぱ億万長者も夢ではない（P〕かもしれない．この拙文が，その不思議の世界へのいざないとして，すこしでも読者の役に立てれぱ幸いである．参考文献「公開鍵暗号系」サローマ著足立訳東京電機大学出版局（1992〕「情報セキュリティの科学」大田，黒澤，渡辺著，講談社プルーバックス（1995〕（一橋大学大学院商学研究科教授） 461