Enigma Japanのブログ

仮想通貨Enigma(エニグマ)についてガチ解説していくEnigmaJapan.infoのブログです!

Secret Sharingを実際にやってみた

《転載元:カナゴールドの仮想通貨ブログ

f:id:udoncryptocurrency:20180226165315p:plain

こんにちは。カナゴールドです。

最近Enigmaの活動が盛んみたいだけどmoonしねえな?とイライラしている諸君、こういう時はやることないのでのんびりでお勉強しましょう。

今日は、enigmaで用いられるSecret Sharingについて解説したいと思います。実際にEnigmaで用いられる際はもっと洗練された手法になりますが、エッセンスを感じてもらうのを目的として書きました。

//////

ここに3人のビットコイナーがいます。彼らが会って話すことと言ったら、暗号通貨の話か、どうしてモテないかの話しかありません。しかしながら、彼らは異常にプライドが高く、自分の彼女いない歴については頑なに口を割りません。あまりにも生産性が低いので、それを見ていたカナゴールドが次のような提案をしました。

「お互いに自分の彼女いない歴を明かさずに、全員の彼女いない歴の平均値を算出するのはどうか。シークレットシェアリングを用いれば、それが可能である。」

プライドが高いビットコイナーたちは、シークレットシェアリングについて知りませんでしたが、もちろん、知ったかぶりをして合意しました。

「各自、関数f(x)=s+px+qx2を用意してほしい。ここで、sは自分自身の彼女いない歴、pとqはランダムに選んだ数字とする。」

数字が好きなビットコイナーたちは、各々自分の好きな数字と自分の彼女いない歴を使って、関数を作りました。

ビットコイナー1:f1(x)=24+3x+6x2

ビットコイナー2:f2(x)=30+4x+7x2

ビットコイナー3:f3(x)=18+5x+8x2

カナゴールド含め、彼らは他の人の彼女いない歴を知りませんが、上の式を見ている読者としては、ビットコイナー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+p2x2

f2(x)=s2+q1x+q2x2

f3(x)=s3+r1+r2x2

とすると、

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歳であることを元々知っていることと、恒等的に彼女いない歴は年齢以下であることから、全員の彼女いない歴は判明してしまうのではないか、と。

しかしこれはプロトコル外のお話であり、カナゴールドは関知するところではないので、ビットコイナーたちの歓談をよそに、そそくさと立ち去りましたとさ。

おしまい。

この記事は、著者であるカナゴールド氏の許可を得てブログポストから転載されました。オリジナルの記事を参照する場合、こちらのリンクから確認することができます。