いぬおさんのおもしろ数学実験室

おいしい紅茶でも飲みながら数学、物理、工学、プログラミング、そして読書を楽しみましょう

3彩色問題で本人の確認をする

 太郎くんが目の前にいれば「あ、この人は太郎くんだ」とか分かります。しかし特にネット越しにメールかなんかのやりとりをしているだけでは「太郎くんだと思っていたら違うヤツだった!」なんてことが起こりかねません。「確かに太郎くんである」という保証が欲しい、そんなときに使える巧妙な方法があります
 下のような図を「グラフ」と言います。

f:id:Inuosann:20190926232139p:plain

2次関数のグラフやなんかとは違いますが、こんなのもグラフと呼ばれます。○を3色で塗りますが、線でつながっている○同士は同じ色にしてはいけません。このルールを守って色をつけることを「塗り分ける」と表現することにしましょう。「グラフを3色で塗り分けよ」という問題を考えます。これは3彩色問題と言われます。このグラフは簡単に塗り分けができます。しかし、簡単なのは○の数が少ないから。やってみると分かりますが、○が100個にでもなればもう事実上塗り分けは不可能なのです。そこで、この事実を利用した本人の確認ができます。
 今、太郎君に塗り分けられる、○の数が500個くらいの大きなグラフGがあるとしましょう。「Gを3色で塗り分けられるのは太郎くんだけですよ」とグラフGとともに世間に公表しておきます。Gは○の数が多いので、公表しても誰にも塗り分けができません。だから太郎くん以外の誰かがGを塗り分けて見せて「私が太郎くんだ」と名乗ることはできないはずです。太郎くんが「自分は確かに太郎くんだ」と証明したいときにはGを塗り分けて見せればよいのです。しかしまずいことがあります。1回塗り分けて見せてしまえば、塗り方を憶えた人が以後その塗り方をマネして「私は太郎くんだ」と名乗れることになるからです。つまり、塗り分け方を見せずに「塗り分け方を知っている」という事実のみを示す方法が必要なわけです。こんなのをゼロ知識証明と言います。「相手に与える知識はゼロだが、本人であることの証明ができる」という意味です。やり方を説明しましょう。
 赤、青、黄色でもいいですが、分かりやすくするため3色をA,B,Cとします。太郎くんは○にA,B,Cを入れる方法を知っています。太郎君は丸いカードを500枚用意してグラフに乗せ、すべてのカードにA,B,Cを塗って裏返しておきます(塗り分けた!)。花子さんは自分が本当に太郎くんとメールをやりとりしているのか、怪しんでいるとしましょう。花子さんに500枚のうちの線でつながっている2枚を選んでもらい、それを表にします。本当に太郎くんなら同じ色はついていないはずです。同じ色でないことが確認できたらその2枚を元通り、裏にします。次に太郎くんがグラフGのA,B,Cをそれぞれ例えばB,C,Aに塗り替えます。花子さんには塗り替えている様子は見せません。塗り替えが終わったら再び花子さんに線でつながっている2枚(さっきと同じ2枚でも別の2枚でもよい)を選んでもらい、表にして色が違うか調べます。違っているなら太郎くんである確率が高まりました。太郎くんはまた塗り替えます。……と、これを繰り返します。20回も繰り返せば、太郎くんでない人間はまあ必ずボロを出すでしょう。つまりどこかで「あ、同じ色だ!」ということになるでしょう。ボロを出さないのは太郎くんだけなのです。いい方法だ! いや、しかしなんで誰にも塗り分けられないGの塗り分け方を太郎くんが知っているのか? これは簡単。塗り分けられていない大きなグラフを塗り分けるのは無理ですが、グラフを作りながら塗っていくのは易しいのです。太郎くんは○を1個描いては線でつなぎ、色をつけていったというわけです。
 (だいぶ前の情報ですが)例えば○が500個のグラフを塗り分ける方法を見つけるのには事実上全ての塗り分け方を試すしかありません。つまり、3の500乗通りの塗り方を試してみて、きちんと塗り分けられているかいちいち確認することを繰り返す方法しか見つかっていないのです。これを実行するには気が遠くなるような時間が必要です。だからGを世間に公表しても誰かに塗り分けられてしまう心配がないのです。なお、実際には塗り替えや2枚を選んで色が違うことを確認するなど、人間がいちいちやっていてはどうにもなりませんから、もちろんコンピュータで実行します。
 この話は『情報セキュリティの科学―マジック・プロトコルへの招待』(太田和夫、渡辺治、黒沢 馨1995講談社ブルーバックス)にありました。こういった話が満載です。古本ならアマゾンで手に入るようです。