著者

岡田 政則 岡本 栄司

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.1998, no.62, pp.57-64, 1998-07-22

---

実社会においては,プライバシー保護の観点からある種のランダムネスの利用の要求がある.この場合,完全にランダムな状態でなくても低コストで十分プライバシーが守られる状態が生成できれば都合が良い.本論文では,最初にシャフリングを定義し,シャフリング近似の概念を導入する.そのランダムネスの尺度としては相対エントロピーを利用し,ランダムネスのコストとしてシャフリングを生成する回路の素子の個数を利用する.このためにまずその個数にコストを表す関数としての妥当性があることを検証する.例として複数の投票所からなる投票集計のモデルを取り上げる.そこでは選挙とその投票結果のプライバシー保護をランダムネスとその生成コストの関係として考察している.Randomness is used for a protection of privacy in the actual world. To investigate randomness, we show the definition of the shuffling S_n of n input data; and, we define the pseudo-shuffling S^^^_n by S_2 0nly. The definition of randomness is represented by relative entropy, and the cost of randomness is expressed by the number of shuffling S_2 in pseudo-shuffling S_n. We consider pseudo-shuffling as an approximation of shuffling with some constraints. Finally, we show a problem related to ballot boxes in the election as an example.