Q.
A,B,Cが自然数のパスワードSa, Sb, Scをそれぞれ持っている。互いのパスワードを知ること無く、全員がSa+Sb+Scの値Sを得たい時にどうするか。
greeの千田さんの日記で提示されてた問題。
基礎中の基礎らしい。
僕の解答はcontinue readingで→
A.
整理すると、
AがSb,Scそれぞれの値を知らないままにSa+Sb+Scを知りたい場合、Sb+Scの値を得られればよい。
まずAとBが乱数xを、AとCが乱数yを、BとCが乱数zを共有する。
BとCは互いに独立にSb+z、Sc-zをAに教える。この数値を互いに足せばSb+Scとなる。
つまりSa, Sb+z, Sc-zの値をL1, M1, N1とすると
L1 + M1 + N1 = Sa + Sb+z + Sc-z = Sa+Sb+Sc = S
よってAはAの観測可能範囲内でSを得られる。
この時点でAが知り得ている値はSa,x,y,Sb+z,Sc-zであり、Sb,Sc,zをそれぞれ導出は出来ない。
以下略
コメント (3)
それ間違いだと思うよ。
共有できる乱数が存在するということは二人以上が同時にアクセス可能な乱数発生機があるということ。
それは第三者の存在と同値だよ。
足し算プログラム作るとかと一緒じゃない？
俺の回答は、AがSaに乱数Raを足して、Bに渡す。
BはそれにSbを足してCに渡す。
CはそれにScを足してAに渡す。
Aは返ってきた数からRaを引くと答えが得られる。
ってのを繰り返せばいいよね。
第三情報の共有なし。
さすがでしょ？
投稿者: NZM | 2006年10月23日 04:12
よく考えたらそんなことないか。
Aが発生させた乱数xをBに渡せばいいんだもんな。
でも面倒くさいなあ。
投稿者: NZM | 2006年10月23日 10:24
なるほど〜
そっちの方がかっこいいかも :D
投稿者: negipo | 2006年10月23日 11:24