しかし、最後に「本当の平均値」に戻す方はどうするんだ? 巡回群上の1つの値に対して、整数が n 個対応するからこそ、実際の値を隠せるわけだろう? 隠しきれるような値なら元に戻せないし、元に戻せるなら個々の数字ももとに戻せてしまうではないか(巡回群上をぐるぐる回っているのは乱数の部分だけであって、賃金の部分は実は一意決定だって事になるから、後で乱数の影響を取り除くために引き算をするときに、個々の賃金も露呈してしまう)。
An + Xn mod C = Rn から、あるBnがあって Xn = C * Bn + Rn - An だが、P0はCがわからないのでBnとXnがわからない。 PnはCとAnがわかるが、RnがわからないのでXnとBnがわからない。
Sum_n(Rn) + X0 - Sum_n(An) mod C
= Sum_n(An + Xn - C * Bn - An) + X0 mod C
= Sum_n(Xn) + X0 mod C
= Sum_n(Xn) + X0 Avg = (Xp + Sum(Xn)) / 人数 Pn全員がわかったので答えをP0に教えて終わり。
mod Cを省略して、An+Xn=Rnとすると、P0にはAnとRnからXnがわかってしまいます。 最初の案のように、Rnをうまくシャッフルできればmod cなしでもいいのですが、ただ乱数を使っていると一番近いAnを使う、などといったトリックが使えるのであまり効果がありません。 #小さい部屋=紙片を使わず口頭で申告すると全員に聞こえてしまう、という制約がAnとRnだけではXnがわからない手段を必要としています。
巡回群でOK? (スコア:1)
教授は信用できないとは書いてないので、数学的には全員で十分大きな数を決めておき、乱数＋賃金を割った余りを常に用いることにすれば（巡回群で計算）完全正答な気がします。
周りが信用できなければ、準同型暗号使って電子投票することに・・・
#数学教授ならきっと暗算で復号してくれる！
Re: (スコア:1)
？？？
確かに「巡回群上での」平均値は求まるだろう。
しかし、最後に「本当の平均値」に戻す方はどうするんだ? 巡回群上の1つの値に対して、整数が n 個対応するからこそ、実際の値を隠せるわけだろう? 隠しきれるような値なら元に戻せないし、元に戻せるなら個々の数字ももとに戻せてしまうではないか(巡回群上をぐるぐる回っているのは乱数の部分だけであって、賃金の部分は実は一意決定だって事になるから、後で乱数の影響を取り除くために引き算をするときに、個々の賃金も露呈してしまう)。
おぉ。後は鉛筆と紙だけでどうやって 電子投票 するのかという問題をとけば…ってダメやんっっ!!暗号化・復号化処理を暗算でできるかどうか以前の問題やん。
数学教授に機械が組み立てられると思っているのか?!
(あれ？？それもなんか違う問題のような…)
fjの教祖様
Re:巡回群でOK? (スコア:1)
！？
巡回群で計算した合計＝元の数での合計、じゃだめでしょうか？ 有限桁の加減算で桁あふれ無視しても結果が表現範囲内ならOKというのと同じだと思うのですが。
乱数サイズは賃金の合計に比べて大きく取る必要があり、そのままでは最大の乱数を出した人が簡単に特定されてしまうので、巡回群にして乱数の一様性を保証する必要があると思います。
あと全く失念していましたが、乱数と加算後の値が近いことを利用して紙片の持ち主を特定という抜け道を潰すため、あらかじめ２グループ以上に分け紙片の集計は別グループに任せる、といった手順を踏む必要があると思われます。
#これだと4人以上になっちゃう？
すべった元の言い訳すると、「準同型暗号使った電子投票と同じ秘密計算」。
#眠気の中で書くもんじゃなかった・・・
Re:巡回群でOK? (スコア:1)
そのためには、「各教授の給料の最大値」が判らないと駄目では? そういう情報を取得できてはいけない、という拘束条件があるんですが。
Boldで強調した条件のせいで、巡回群の大きさを決められない、という拘束条件が出てしまうのですが…。
# つまり、こいつらの中には何兆ドルも稼いでいる奴がいるかもしれないってことで…
fjの教祖様
Re:巡回群でOK? (スコア:1)
「(集まった)各教授の給料」はともかく、「一般の給料」ならたとえば[0,ドルの発行残高)と言う風に決めてしまって構わないと思うのですが・・・
こういった解釈がだめだとすると、給料は（-∞,∞）である必要があり、紙に書こうが背中に指で書こうが声で伝えようが伝達時間から有限桁であることが分かってしまうので、そもそも情報のやり取りが一切禁止されるはずです。
Re:巡回群でOK? (スコア:1)
うーむ。その巡回群は結局「何を判らないように」しているのでしょう?
例えば巡回群を[0から10京)のように決めたとしましょう。
で、私の年俸と乱数を足したら 30万ドルで、乱数として(10京-20万)ドル足したとしましょう。
…年俸は巡回群を「巡回できない」ぐらい十分小さく、乱数は「巡回できる」ぐらい大きな値をとりうるんですよね? この条件だと…何を隠しているの?? 給料?? それとも乱数??
fjの教祖様
Re:巡回群でOK? (スコア:1)
あ、勘違いで混乱しつつ説明があほすぎて本当に申し訳ないです。
長いですが・・・
N+1人を一人P0と残りPn（n=1..N）に分かれる
・P0は白紙で紙をP1に渡す
・P1は適当な数C>>Max(Xn:Pnの給料)をもらった紙に書き、P0に見せないようにP2...PNに回す
・Pnは乱数An + 給料Xn mod C = Rnを書いてP0に渡す。An>>Cで、Anは口頭で開示する
・P0はX0+Sum_n(Rn)を口頭で報告する (Sumは1...n)
P0: X0, R1...RN, A1...AN
Pn: C, Xn, Rn, A1...AN, (sum_n(Rn) + X0)
An + Xn mod C = Rn
から、あるBnがあって
Xn = C * Bn + Rn - An
だが、P0はCがわからないのでBnとXnがわからない。
PnはCとAnがわかるが、RnがわからないのでXnとBnがわからない。
Sum_n(Rn) + X0 - Sum_n(An) mod C
= Sum_n(An + Xn - C * Bn - An) + X0 mod C
= Sum_n(Xn) + X0 mod C
= Sum_n(Xn) + X0
Avg = (Xp + Sum(Xn)) / 人数
Pn全員がわかったので答えをP0に教えて終わり。
mod Cを省略して、An+Xn=Rnとすると、P0にはAnとRnからXnがわかってしまいます。
最初の案のように、Rnをうまくシャッフルできればmod cなしでもいいのですが、ただ乱数を使っていると一番近いAnを使う、などといったトリックが使えるのであまり効果がありません。
#小さい部屋=紙片を使わず口頭で申告すると全員に聞こえてしまう、という制約がAnとRnだけではXnがわからない手段を必要としています。
たぶんこれで会ってるはずですが・・・まだ間違ってたらごめんなさい。
Re:巡回群でOK? (スコア:1)
C ≫ Xi が成り立つなら、「Pnは乱数An + 給料Xn mod C = An + Xn = Rn」になるじゃないですか。そしてそれを「全員が知っている」状態になります。
An と Rn から Xn が判らないようにするには「 C ≫ Xi が成り立たない」必要があるはずです。
fjの教祖様
Re:巡回群でOK? (スコア:1)
すみません「Piは乱数Ai>>Cと給料Xiから、Ri := (Ai + Xi) mod Cを計算し～」と読み替え願います。
Ai + Xi >> Cなので、ある自然数Biがあって、Ri := (Ai + Xi) mod C == (C * Bi + Ri) mod C != Ai + Xi
Riの計算や平均の計算をするのはmod Cで、Aiの通知は一般の数で行います。（Ai mod Cではなく）
会話は除数C（秘密鍵）で暗号化されているので、Cを知らないP0（Riの集計係）はAiが聞こえていてAiとRiが全て分かっているのに、Xi（とBi）は分かりません。
# mod が左側全体にかかるのって整数論あたりの方言なんでしょうか
# あとRとA逆にするべき鍵はKで添字はiだろとか。重ね重ね書き方悪くて申し訳ないです。
Re:巡回群でOK? (スコア:1)
「乱数 Ai に対して Ai ≫ C」というのは、すべからく「乱数 Vi を定義して C ＞ Vi ≡ Ai mod C」であるのと同じですよね？
なら、Ai の代わりに「C-Xi ＞ Vi ＞ -Xi であるような乱数 Vi だけを使う」としているのと変わらないじゃないですか。
一見巡回群のように見えるこの系は、CがXiに比べてあまりにも大きいと、実は「巡回群じゃない」と仮定して計算できてしまう、と言う事です。
fjの教祖様
Re:巡回群でOK? (スコア:1)
「乱数 Ai に対して Ai ≫ C」というのは、すべからく「乱数 Vi を定義して C ＞ Vi ≡ Ai mod C」であるのと同じですよね？
ViからAiをつくる、と言う意味なら、Ai mod C == ViとなるAiは無数にあるので違ってきます。
Ai の代わりに「C-Xi ＞ Vi ＞ -Xi であるような乱数 Vi だけを使う」としているのと変わらないじゃないですか。
「～」は、「Aiの範囲をC>Ai+Xi>0となるようにする（その後AをVに書き直す）」と等価ですが、そうするとBi = Ai + Xn div Cは常に0になります。
BiはP0(Rnの集計者)には分からない数値である必要があり、重要な点が変わってしまっています。(Ai >> Cはそのため)
CがXiに比べてあまりにも大きいと、実は「巡回群じゃない」と仮定して計算できてしまう
のではなく、「Bi=Vi + Xi div Cがゼロであるとき、～計算できてしまう」のであって、CがXiに比べて大きくてもAiがCより十分に大きくBiが推定できないなら、RiとAiからXiを計算できません。