プライバシーはパズルで守る？！
公開鍵暗号方式の数学的脆さ

　理想郷から現実世界へ

　　新しい技術の社会への導入といえば, 今日のインターネットの広がりが, この典型例であることは論をまたない。というより, 今世紀末最大の技術革新になる可能性さえあるのだ。だが, これほどの技術革新にもかかわらず, なぜか「負の面」についての議論は少ない。
「革新的な技術の負の面を強調したがるのはエセ人道主義者の常道だ。インターネットには公害のような『負の面』はない」という人もいるかもしれない。実際, インターネットには不思議と「人間性の抑圧」というイメージが少ない。工場にオートメーションが導入されたときは映画『モダン・タイムス』に描かれたような工場労働者への抑圧があったし, それほどでなくても, 新しい技術が導入されるたびに, 古い技術に頼って生計を立ててきた人々が失業の憂き目に遭う, という悲劇は避けられなかった。
　しかるに, インターネットの成立で損をしそうなのは, どうも個々人ではなくて, マスコミ, 出版業界, 通信業者, あるいはマイクロソフトなどの独占・寡占により利益を得てきた巨大組織, と想像されがちである。だからこそ, インターネットは個人を解放し, 権力者を叩く「強きをくじき, 弱きを助ける」ものであり, 巨大企業の影で市民が苦しむ「公害」のような構造の「負の面」の出現は想像が難しいわけだ。だが, これはある意味では, インターネットの世界が今まで“ユートピア”だったからだともいえる。
　インターネットの世界はあくまで現実世界の添えものとして扱われてきた。電話網や道路網のように社会のインフラとして組み込まれていたわけではなく, あれば非常に便利だが, ないからといって人命や国家経済に甚大な影響が及ぶほどのインフラではなかったのだ。
　インターネットがその程度の存在であるうちは“ユートピア”として存在し続けることができた。しかし, 社会の基本的なインフラとして組み込まれようとしている現在, さまざまな問題が吹き出しつつある。アメリカでの通信暗号システムの国家による独占のもくろみ, 著作物の権益化, あるいは, 猥褻物の取り締まりなどである。
　これらはあくまで, 「“秩序ある無政府状態”であるべきインターネットへの既存の権力の進出」という文脈で語られることが多い。しかし, 国家や大企業が現実世界で社会の秩序を形成・維持していたのを考え合わせると, これらの「秩序維持者」あるいはその代替物なしにインターネットのシステムは円滑に機能することができるのだろうか。
　この問題に対して, 答えの一端となりうるのがインターネットにおける「暗号技術」である。たとえば現実世界では, 国家が造幣し, 銀行が管理する。郵便物の機密性は郵便局が保証し, 郵便局員が封筒を開けて中身を読む, などという行動に出た場合には, 郵便局が責任をもってその局員を処罰する。インターネットではこのようなシステムを導入する代わりに, 暗号技術を導入して乗り切ろうとしているわけだ。
　機密性を保証する公的機関がなくても「公開鍵暗号方式」を用いれば, 機密性を維持できる。デジタル・キャッシュを導入すれば「所有者だけが支払いを許可できる電子貨幣」というものが, 銀行や国家の介入なしに実現可能だ。暗号技術さえ破られなければ, 国家も銀行も郵便局も必要ない。つまり, 中央の権力に依存することなく, 各自が分散した形で安全を確保できる。権力を分散することにより, 権力者を排除することができ, かくして“ユートピア”が生まれるというわけだ。
　だが, はたして暗号技術自体はどのくらい安全なのかという議論はきわめて少ない。「電子貨幣や公開鍵暗号はどのような仕組みなのか」あるいは「それらが実現したとき社会に受け入れられるか」とか「その結果社会がどうなっていくか」という議論だけが先行している。
　はたしてインターネットのセキュリティは、公開鍵暗号方式を用いることにより万全となるのだろうか ?
　日本におけるこの分野の基礎理論の権威である東京工業大学情報理工学研究科計算工学専攻 助教授、渡辺治にこの疑問をぶつけてみた。「計算の複雑性」の研究で日本IBM科学賞を受賞し、『情報セキュリティの科学』（講談社ブルーバックス）の著者の一人でもある彼の答えは意外にも「決して万全とはいえない」というものだった。なぜこのような答えが彼の口から出たのか。これについては、もう少し説明が必要だろう。

デジタル社会の「機密」と「認証」

　　インターネットが社会的なインフラとして機能するために欠く部分に「認証性」と「機密性」の確立がある。認証性とはいわば, 実世界で「印鑑」とか「身分証明書」のような役目をする部分である。物品の売買など, 契約関係を結ぶときには「この契約に同意した」ということを第三者に対して証明するために印鑑（欧米であればサイン）が使用される。そこで仮定されているのは「唯一性」という概念である。印鑑にせよサインにせよ, それを使用できるものはひとつしか存在しない, ということが暗黙のうちに仮定されている。それは, 印鑑であれば, その印鑑という物理的実体であり, サインであれば, サインする人物ということになる。
　ところが, この認証をインターネット上で行おうとすると「デジタル・データは複製自由である」という点がネガティブに働くことになる。インターネット上のデータはすべてデジタルであるから, 複製のできない印影というものは存在しない。ということは, ある人の認証が入った書類を一度受け取れば, 印影の部分だけをカット・アンド・ ペーストすることにより, いくらでも「ニセ」の認証を発行できることになってしまう。これでは認証の意味がない。
　一方, 機密性も同じような問題をはらんでいる。現実の郵便では, 「封筒」という物理的実体によって、ある程度の機密性は最初から与えられているし, 「書留」という, より機密性の高い封筒と管理方法を導入することも可能だ。ところが, インターネット上の通信, たとえば電子メールなどでは無防備の裸のパケットが, 不特定多数の人が管理する回線上を動き回る。よって, その気になれば経路上の第三者がその内容を見ることができる。それどころか, 現状のインターネットの仕組みでは不特定多数のマシンが「受け手」を装うことを完全には防止できない。もちろん, 任意の場所で, というわけにはいかないが, その気になればA氏からB氏への電子メールを横取りすることは簡単である。B氏の受け手となっているマシンのIPアドレスを名乗ればいいからだ（もちろん, そんなことをしたら, システム自体がめちゃくちゃになるかもしれないが）。
　つまり現状のインターネットの仕組みでは「機密性」など望むべくもない。というより, 「権力をもった管理者」を否定するインターネットの基本的なプロトコルがあるかぎり、インターネット上は, 認証性や機密性が保証されようのない無法地帯なのだ。（でもケヴィン・ミトニックは逮捕されたではないか, というかもしれないが, 逮捕, という行為自体, インターネットの外部に存在する権力の行使である。インターネット内の組織や機構の範囲内で,　ミトニックを罰したり排除したりできたわけではないのだ）。「管理・保全はインターネット外の権力に依存するが, その権力自体はインターネットに入ってきてほしくない」などという虫のいい話しは成立し得ない。
　こういう状況の中で一躍脚光を浴びはじめたのが「公開鍵暗号方式」と呼ばれる暗号技術である。これを使うとある特定の個人しか解読できない暗号を誰もが作ることができる, というのだ。つまり, 解読法を知らなくても暗号文が作れる。このシステムが「完璧」に動作すれば認証性や機密性は容易に保てるはずだ。
　たとえば, 機密性について考えてみよう。A氏に機密電子メールを送りたくなったら, A氏からA氏専用の「暗号作成方法（公開鍵）」を聞き、その方法で文章を暗号化してから送る。メールを受け取ったA氏は、自分しか知らない「解読方法」でこの文章を読むというわけだ。このシステムの優れた点は、暗号作成方法を知っているだけでは解読はできないので, A氏が暗号作成方法を電子メールを送っても（たとえそれが第三者の手に渡っても）機密性にはまったく問題がない、という点だ。
　認証性も同じようにして実現できる。たとえば, 印鑑（電子署名）を考えてみよう。印鑑を捺したい文章があれば, それを自分だけが知っている「解読方法」で符号化する。自分だけが知っている解読方法は本来, 暗号化された文章を元の文に戻すために使うのだが, 普通の文章にその解読方法を用いると、わけの分からない文章ができる。文章の受け手が、今度は公知されている「暗号作成方法」でこの文章を暗号化すると, もとの普通の文章が再現される。これにより、その人がその文章を書いたことが確実になる。暗号化をすると普通の文章になるような妙な文章を作ることができるのは, 暗号解読法を知っているその個人だけだからだ。
　このシステムは, 既存の権力が握っていた認証性や機密性の保証を「数学」という科学の“神様”に肩代わりさせようというものだ。だが, その“神様”は人間の頭脳から生まれたものにすぎない。本当にそんなものにそれほどの絶対的な力があるのだろうか。

公開鍵は誰でも解ける ?!

　公開鍵暗号方式とは要するに「クイズ」だと思えばよい。誰もが一度はやったことのあるクロスワードパズルを考えてみよう。クロスワードパズルには, 非常に難しく、半日かかってしまうものもある。雑誌や新聞についている懸賞のクロスワードパズルによくあるのは文字を埋めるべき空欄のいくつかが太枠で囲まれていて, その太枠内の文字でできる言葉を答えなさい, というものである。
　しかし, どんなに難しいクロスワードパズルでも, 実は時間が無限にあればきわめて簡単なクイズとなってしまう。ます目がいくつあっても, 結局そこに入るのは「ア」から「ン」までの50文字足らずにすぎないからだ。そして、その組み合わせの数は、たとえば空欄が100マスであれば「たったの」50×100通りである。「たったの」と書いたが実際にこの組み合わせを全部試すとなると膨大な時間がかかる。毎秒, 1つの文字パターンを試すというスピードで検査ができたとしても, 宇宙の年齢である150億年より長い時間がかかってしまうのだ。「総当たり」でクロスワードパズルを解くのは事実上不可能なのである。
　つまり, こういうことだ。クロスワードパズルは無限の時間があれば誰にでも解くことができるが, 実際にはそれだけの時間がないがゆえに頭を使って解かなくてはならない。だから, クロスワードパズルというのは, いい暗号になる。伝えたいことがあったら, それをクロスワードパズルの中に組み込む。懸賞クイズのときのように太枠の文字を設けておき, それが伝えたい言葉になるようにする。これなら, クロスワードパズルが完全に解けない限り, この「暗号」は解けない。
　しかし, このやりかたには大きな問題がある。ひとつは、伝えたいことがあるたびに, 難解なクロスワードパズルを作るのは大変だということ、もうひとつは、 受け手以外の人にクロスワードパズルが解けないとは限らないという点だ。
　公開鍵暗号は前者の問題点はクリアした。つまり、誰でも, 頭をまったく使うことなく, クロスワードパズルに相当する難しいクイズを作ることができるのだ。また, その方法で作られたクイズの解き方は1通りしかなく, その解き方を知っていればたちどころにクイズの答えが分かる＝暗号文の解読が行える。つまり、ある一定の方法で解けることが分かっている難しい問題を、解き方が分からなくても無限個, 自動的に作れる, ということなのだ。これなら, 伝えたいことがあるたびにクロスワードパズルを作るという大変さはない。解き方を公開せずに, 問題の作り方だけ公開しておけば, 前に述べたやり方で, 認証性や機密性を実現できる。
　では, もうひとつの問題, 「受け手以外の人は答えを得られない」というのはどうだろうか。

NP問題の応用

「そこが問題です。そもそも, 受け手以外は誰も答えを得られないという問題はありえません。ただ, 非常に難しいというだけのことです」と渡辺は言う。では, どういう問題が「非常に難しく」て, どういう問題がそうでないのか。彼が専門にする「計算の複雑さ」とはこういうことを議論する学問である。
　クロスワードパズルのように「いったん答えが分かれば誰でもすぐそれが答えだと分かる」ような問題はNP問題（NP＝Nondetermistic Polynominal：「べき乗【＊2】（2乗, 3乗）程度の時間では計算できない」の意）と呼ばれている。そのNP問題の中には単純な総当たりで解く以外に良い方法がない, と予想されているものが多くある。そして, この中のいくつかが公開鍵暗号にもうまく利用できるのである。つまり, 公開鍵暗号に利用するためのいいクイズ, を考えるためには, NP問題全般に関する知識が欠かせない。
　では, NP問題についての基礎研究はどれくらい進んでいるのだろうか ? 「最も肝心な点については, まだ何も分かっていません」と渡辺は言う。NP問題に関する研究が進まないうち, それを応用した公開鍵暗号の技術が開発されるということがあり得るのだろうか ?
「それがあり得るのです。実際, NP問題という言葉が提案されて研究が始まったのはごく最近で1972年のこと。それ以前は難しいNP問題は, バラバラに研究されていて, それらがすべて似た問題（共通の性質をもつ問題）だということが分かりませんでした。ところが, 公開鍵暗号の可能性が指摘されたのはそれからたった4年後の76年。つまり, 基礎がちゃんとできる前に応用が始まってしまったのです」
　実際, 現在の公開鍵暗号システムの根幹をなす「難しい問題」である「素因数分解【＊1】」はNP問題であると思われているが, NP問題の研究自体が未解決な問題である以上, 何か画期的なアイディアによって非常に簡単に解けるやり方がない、という保証はどこにもないのだ。つまり、もし, そういう解法が見つかったら公開鍵暗号方式は一夜にして崩壊するということだ。
　NP問題の研究開始と公開鍵暗号方式への応用がほぼ同時に始まった以上, 応用が先行するのは仕方がないことだ。しかし, そのような大切な問題がいまだに放置されているのはなぜだろうか。
「第1に, そういう基礎的な問題は解決が難しくて論文が書きにくい。3年間それにかかりっきりで何も成果が出ないなんて普通のことだ。それに対して, NP問題は難しくて解けない, ということを仮定して応用の論文を書くのは比較的楽だ。僕もいま, デジタル・キャッシュへのNP問題の新しい応用について論文を書いているとことろなんですが」
　渡辺は, 書きかけの論文を示しながらこうもつけ加えた。
「第2に, “何が難しくて解けないか”という研究は, アルゴリズム研究の中ではとっても異端です。だいたい, アルゴリズムの研究というものは, 問題を効率的に解くやり方を求めてなんぼ, という世界ですから。だから, 研究者の数もそう多くないですね」　渡辺は, 基礎理論がないまま応用が先行している現状に非常に危機感を抱いている。公開鍵暗号のシステムがインターネット上に普及してから, 実はNP問題は簡単に解けます, という数学的な証明が発見されたら, すべての暗号が一度に無価値になってしまうからだ。
「現状はもっとお粗末です。未知の問題はおろか, 新しく提案された公開鍵暗号が既存の知識の範囲内で安全化どうかをチェックする機関さえ存在しないません, 少なくとも日本には。なにせお金にならない作業ですから……」

　　自動車や原子力発電など, 安全性や社会への影響がはっきりしない技術を, 人類は次々と導入してきた。それらは, さまざま問題があっても, 徐々に改良する余裕があった。原子炉に欠陥があっても, すべての原子炉が同時に駄目になるわけではないし, テストも可能だからだ。だが, 公開鍵暗号によって保たれるインターネットのセキュリティはそうはいかない。1人の天才の書いた1枚の論文が世界中の公開鍵暗号を一夜にして駄目にする可能性だってあるのだ。
「権力を招き入れたくないが保証は欲しい」というインターネットのもっとも基本的な欲求に, 非常によく合致しているかのように見える公開鍵暗号システム。だが, これは羊の皮をかぶった狼かもしれず, ある日突然, 人々に牙をむくかもしれないことを忘れるべきではない。結局, ただで手に入る自由なんてどこにもありはしないのだから

【＊2】べき乗
「問題の長さ」（クロスワードパズルでは空欄の数）がNであるとしよう。単純な総当たりでクロスワードパズルを解こうとすると本文でも触れたように５０のN乗程度の時間がかかる。これに対し、同じ埋めるべき空欄の数がNである問題でも、例えば、N桁の掛け算ならもっと簡単に計算できる。例えば、３桁の掛け算の穴埋め２３４×□□□＝１２７７６４ならば、１２７７６4を２３４で割る計算をすればいいので、桁数の２乗とか３乗程度の回数の計算をすれば答えが求まってしまう。クロスワードパズルも掛け算の穴埋め問題もクイズには違いないが、掛け算の穴埋めは簡単すぎて暗号には向かない。この様に「問題の長さ」の２乗、３乗、４乗.....などの程度で解ける問題がべき乗程度の時間で計算できる問題、と呼ばれ、それ以外の難しいクロスワードパズルの様な問題がNP問題と呼ばれている。