| 講演名 | 2014-11-21 カード組を用いた不動点のない置換のランダム生成(情報セキュリティ,ライフログ活用技術,ライフインテリジェンス,オフィス情報システム,一般) 石川 理恵, 千田 栄幸, 水木 敬明, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | n人のプレーヤーがいて,プレゼント交換を行いたい場面を考える.すなわち,不動点(fixed point)を持たない置換をランダムに生成したい.裏面が同一の模様である4色のカードを用いると,そのようなランダム置換を秘匿したままで生成できるとともに,置換しのものを明らかにすることなく,不動点を持たないことの証明が可能であることが知られている.本研究では,この問題の解法の効率化に取り組む.すなわち,既存の手法ではn^2に比例した枚数のカードが必要であるが,本研究ではnlognに比例した枚数のカードで十分であり,色も2色で十分であることを示す. |
| 抄録(英) | Consider a scenario where there are n players who want to exchange gifts. That is, we want to generate a random permutation having no fixed point. It is known that such a random permutation can be obtained in a hidden way by using a number of cards of four colors with identical backs, such that it has no fixed point for sure without revealing the permutation itself. This paper deals with such a problem and improves the known result: while the known protocol needs O(n^2) cards of four colors, our improved protocol requires only O(nlogn) cards of two colors. |
| キーワード(和) | カードベース暗号プロトコル / カードゲーム / コンピュータ非依存暗号 / 安全な計算 / 不動点 / ランダム置換 |
| キーワード(英) | Card-based protocols / Card games / Cryptography without computers / Secure computations / Fixed points / Random permutations |
| 資料番号 | ISEC2014-58,SITE2014-49,LOIS2014-28 |
| 発行日 |
| 研究会情報 | |
| 研究会 | LOIS |
|---|---|
| 開催期間 | 2014/11/14(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Life Intelligence and Office Information Systems (LOIS) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | カード組を用いた不動点のない置換のランダム生成(情報セキュリティ,ライフログ活用技術,ライフインテリジェンス,オフィス情報システム,一般) |
| サブタイトル（和） | |
| タイトル（英） | Card-based Generation of Random Permutations without Fixed Points |
| サブタイトル（和） | |
| キーワード(1)（和/英） | カードベース暗号プロトコル / Card-based protocols |
| キーワード(2)（和/英） | カードゲーム / Card games |
| キーワード(3)（和/英） | コンピュータ非依存暗号 / Cryptography without computers |
| キーワード(4)（和/英） | 安全な計算 / Secure computations |
| キーワード(5)（和/英） | 不動点 / Fixed points |
| キーワード(6)（和/英） | ランダム置換 / Random permutations |
| 第 1 著者 氏名（和/英） | 石川 理恵 / Rie ISHIKAWA |
| 第 1 著者 所属（和/英） | 一関工業高等専門学校電気情報工学科 Electrical and Computer Engineering, National Institute of Technology, Ichinoseki College |
| 第 2 著者 氏名（和/英） | 千田 栄幸 / Eikoh CHIDA |
| 第 2 著者 所属（和/英） | 一関工業高等専門学校電気情報工学科 Electrical and Computer Engineering, National Institute of Technology, Ichinoseki College |
| 第 3 著者 氏名（和/英） | 水木 敬明 / Takaaki MIZUKI |
| 第 3 著者 所属（和/英） | 東北大学サイバーサイエンスセンター Cyberscience Center, Tohoku University |
| 発表年月日 | 2014-11-21 |
| 資料番号 | ISEC2014-58,SITE2014-49,LOIS2014-28 |
| 巻番号（vol） | vol.114 |
| 号番号（no） | 321 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |