著者

石川 理恵 千田 栄幸 水木 敬明

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. ISEC, 情報セキュリティ (ISSN:09135685)

巻号頁・発行日

vol.114, no.319, pp.13-18, 2014-11-14

---

n人のプレーヤーがいて,プレゼント交換を行いたい場面を考える.すなわち,不動点(fixed point)を持たない置換をランダムに生成したい.裏面が同一の模様である4色のカードを用いると,そのようなランダム置換を秘匿したままで生成できるとともに,置換しのものを明らかにすることなく,不動点を持たないことの証明が可能であることが知られている.本研究では,この問題の解法の効率化に取り組む.すなわち,既存の手法ではn^2に比例した枚数のカードが必要であるが,本研究ではnlognに比例した枚数のカードで十分であり,色も2色で十分であることを示す.