ステンドグラスパズルに対するカードを用いたゼロ知識証明プロトコル

• Item type: SIG Technical Reports(1)
• 公開日: 2024-08-29
• タイトル: ステンドグラスパズルに対するカードを用いたゼロ知識証明プロトコル
• タイトル / 言語: en
• タイトル: Zero-Knowledge Proof Protocol Using Cards for Stained-Glass Puzzles
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 九州大学大学院システム情報科学府
• 著者所属: 広島大学大学院先進理工系科学研究科
• 著者所属: 九州大学大学院システム情報科学研究院
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Electrical Engineering, Kyushu University
• 著者所属(英): en
• 著者所属(英): Graduate School of Advanced Science and Engineering, Hiroshima University
• 著者所属(英): en
• 著者所属(英): Faculty of Information Science and Electrical Engineering, Kyushu University
• 著者名: 吉塚, 創也; 岩本, 宙造; 櫻井, 幸一
• 著者名(英): Soya, Yoshizuka; Chuzo, Iwamoto; Kouichi, Sakurai
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: ステンドグラスパズルは各ピースを赤または青の 2 色の内いずれかに塗り分けるパズルであり，ピースの境界線上には予め赤，青，そして黄色のいずれか 3 色に塗られた点が存在している．それぞれの点に隣接するピース群は，その点によって指定された色により赤，青のもののいずれかが過半数を占めているか，または同数でなければならない．ゼロ知識証明とは，ある知識を保有している証明者が知識そのものを一切漏らすことなく，検証者に対して知識を有している事実のみを納得させるための暗号技術である．そして，任意の NP 完全であるパズルに対してゼロ知識証明プロトコルを構成できることが知られており，またステンドグラスもその NP 完全性が証明された．したがって本稿ではステンドグラスの色の塗り分け方が，解の条件を満たしているかどうかを検証するための，物理的なカードを用いたゼロ知識証明プロトコルを提案する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Stained-glass puzzles are puzzles in which each piece is painted in one of two colors, red or blue, and there are three pre-painted points on the border of the pieces: red, blue, and yellow. The group of pieces adjacent to each point must have a majority or equal number of either red or blue pieces, depending on the color designated by the point. Zero-knowledge proofs are cryptographic techniques that allow a prover possessing some knowledge to convince a verifier only of the fact that he or she possesses knowledge, without divulging any knowledge itself. It is known that a zero-knowledge proof protocol can be constructed for any puzzle that is NP-complete, and stained glass has also been proven to be NP-complete. Therefore, this paper proposes a zero-knowledge proof protocol using physical cards to verify whether the coloring of stained glass satisfies the solution condition.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2024-AL-199, 号 2, p. 1-5, 発行日 2024-08-29
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会