Enigma詳細解説 part3 -Secret Sharingを実際にやってみた
こんにちは。カナゴールドです。
最近Enigmaの活動が盛んみたいだけどmoonしねえな?とイライラしている諸君、こういう時はやることないのでのんびりでお勉強しましょう。
今日は、enigmaで用いられるSecret Sharingについて解説したいと思います。実際にEnigmaで用いられる際はもっと洗練された手法になりますが、エッセンスを感じてもらうのを目的として書きました。
//////
ここに3人のビットコイナーがいます。彼らが会って話すことと言ったら、暗号通貨の話か、どうしてモテないかの話しかありません。しかしながら、彼らは異常にプライドが高く、自分の彼女いない歴については頑なに口を割りません。あまりにも生産性が低いので、それを見ていたカナゴールドが次のような提案をしました。
「お互いに自分の彼女いない歴を明かさずに、全員の彼女いない歴の平均値を算出するのはどうか。シークレットシェアリングを用いれば、それが可能である。」
プライドが高いビットコイナーたちは、シークレットシェアリングについて知りませんでしたが、もちろん、知ったかぶりをして合意しました。
「各自、関数f(x)=s+px+qx^2を用意してほしい。ここで、sは自分自身の彼女いない歴、pとqはランダムに選んだ数字とする。」
数字が好きなビットコイナーたちは、各々自分の好きな数字と自分の彼女いない歴を使って、関数を作りました。
ビットコイナー1:f1(x)=24+3x+6x^2
ビットコイナー2:f2(x)=30+4x+7x^2
ビットコイナー3:f3(x)=18+5x+8x^2
カナゴールド含め、彼らは他の人の彼女いない歴を知りませんが、上の式を見ている読者としては、ビットコイナー1~3の彼女いない歴がそれぞれ、24、30、18年となっていることがわかりますね。
「みんな準備できただろうか。それでは、他のビットコイナーにこっそり、xにそのビットコイナーの番号を代入した結果を教えてあげてほしい。例えば、ビットコイナー2はビットコイナー3に、f2(3)の値を教えてあげてほしい。その数字は他の人には教えてはならないよ。」
ビットコイナー1は、f1(1)=33、f2(1)=41、f3(1)=31の値を(f1(x)は自分で作ったから全て知っているが)、ビットコイナー2は、f1(2)=54、f2(2)=66、f3(2)=60の値を(f2(x)は自分で作ったから全て知っているが)、ビットコイナー3は、f1(3)=87、f2(3)=105、f3(3)=105の値を(f3(x)は自分で作ったから全て知っているが)を知ることとなりました。
「それでは、いま計算した値の合計値だけを全員に公表してほしい。」
ビットコイナー1は105、ビットコイナー2は180、ビットコイナー3は297と公表しました。
カナゴールドは言いました。
「君たちの彼女いない歴の平均値は24歳である。しかし、それぞれの彼女いない歴はわからない。」
//////
賢明な読書であれば、105、180、297という数字だけで、全員の平均彼女いない歴を計算することができて、それぞれの彼女いない歴は判明しないことを理解できるであろう。
3人の関数の形をそれぞれ、
f1(x)=s1+p1x+p2x^2
f2(x)=s2+q1x+q2x^2
f3(x)=s3+r1+r2x^2
とすると、
f1(1)+f2(1)+f3(1)=(s1+s2+s3)+(p1+q1+r1)+(p2+q2+r2)=105
f1(2)+f2(2)+f3(2)=(s1+s2+s3)+2(p1+q1+r1)+4(p2+q2+r2)=180
f1(3)+f2(3)+f3(3)=(s1+s2+s3)+3(p1+q1+r1)+9(p2+q2+r2)=297
と書くことができる。
いずれの式にも、(s1+s2+s3)、(p1+q1+r1)、(p2+q2+r2)が出てきていることから、S=(s1+s2+s3)、P=(p1+q1+r1)、Q=(p2+q2+r2)と置けば、
S+P+Q=105
S+2P+4Q=180
S+3P+9Q=297
となるので、この三元一次連立方程式を解けば、
(S,P,Q)=(72,12,21)が得られる。
よって、平均彼女いない歴を求めるには、S/3=24で良いことがわかる。
この時、仮にこのゲームの参加者であれば、例えばビットコイナー1は追加でs1とp1とq1の値と、f2(1)とf3(1)も知っていることになるが、未知数が9個から6個に減るものの、式は5本しかないので、他の人の値は求めることができないことがわかる。
//////
ビットコイナーのうち一人は、ふと、面白い事実に気づきました。全員の年齢の平均値が24歳であることを元々知っていることと、恒等的に彼女いない歴は年齢以下であることから、全員の彼女いない歴は判明してしまうのではないか、と。
しかしこれはプロトコル外のお話であり、カナゴールドは関知するところではないので、ビットコイナーたちの歓談をよそに、そそくさと立ち去りましたとさ。
おしまい。