| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2025-03-07 14:40 トークンスライディング型独立集合遷移問題に対する物理的ゼロ知識証明 ○池内唯斗・上嶋章宏（阪電通大）  COMP2024-30 |
|
| 抄録 | （和） | グラフの独立集合とは隣接する2頂点を含まない頂点部分集合を指す．グラフ$G$の2つの独立集合$I_s$と$I_t$が与えられ，$I_s$の各頂点にトークンが置かれているとする．このとき，遷移制約を満たすトークンの移動を繰り返し，独立集合のみを経由して$I_s$から$I_t$へ遷移できるかを判定する問題を独立集合遷移問題と呼ぶ．本稿ではトークンが置かれた頂点$v$から空の隣接頂点$w$に向け辺$(v, w)$に沿ってトークンを移動させるトークンスライディング（Token Sliding; TS）型の遷移制約に基づく独立集合遷移問題に注目する．TS型独立集合遷移問題は一般にPSPACE完全であり，DAGに限定してもNP完全であることなどが知られている．本稿では，TS型独立集合遷移問題に対しゼロ知識証明の概念を適用し，$I_s$から$I_t$に至る遷移系列を知る証明者が，その知識を漏らすことなく知っているという事実を検証者に納得させる物理的ゼロ知識証明プロトコルを提案する． |
| （英） | An independent set in a graph is a set of pairwise non-adjacent vertices. Given two independent sets $I_s$ and $I_t$ of a graph $G$, imagine that a token is placed on each vertex in $I_s$. Then, The Independent Set Reconfiguration Problem (ISRP) is defined as determining whether it is possible to transition from $I_s$ to $I_t$ via a sequence of independent sets by repeatedly moving tokens that satisfy some transition constraint. In this paper, we focus on ISRP under the Token Sliding (TS) which enforces that, in each transition of the sequence, a token on one vertex $v$ can be slid to adjacent vertex $w$ along edge $(v, w)$. It is known that solving ISRP under TS is generally PSPACE-complete, and is NP-complete even when restricted to DAGs. In this paper, we apply the concept of zero-knowledge proofs to ISRP under TS. We propose a physical zero-knowledge proof protocol, in which a prover who knows a transition sequence from $I_s$ to $I_t$ can convince a verifier that the prover knows the transition sequence without revealing any information about it. | |
| キーワード | （和） | カードベース暗号 / ゼロ知識証明 / 組合せ遷移問題 / 独立集合 / トークンスライディング / / / |
| （英） | card-based cryptography / zero-knowledge proof / combinatorial reconfiguration problem / independent set / token sliding / / / | |
| 文献情報 | 信学技報, vol. 124, no. 424, COMP2024-30, pp. 29-36, 2025年3月. | |
| 資料番号 | COMP2024-30 | |
| 発行日 | 2025-02-28 (COMP) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2024-30 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2025-03-07 - 2025-03-07 |
| 開催地（和） | お茶の水女子大学 国際留学生プラザ3F セミナー室 |
| 開催地（英） | Ochanomizu University |
| テーマ（和） | 理論計算機科学，一般 |
| テーマ（英） | Theoretical Computer Science, etc |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2025-03-COMP |
| 本文の言語 | 日本語 |
| タイトル（和） | トークンスライディング型独立集合遷移問題に対する物理的ゼロ知識証明 |
| サブタイトル（和） | |
| タイトル（英） | Card-Based Zero-Knowledge Proof Protocol for Independent Set Reconfiguration Problem Under Token Sliding |
| サブタイトル（英） | |
| キーワード(1)（和/英） | カードベース暗号 / card-based cryptography |
| キーワード(2)（和/英） | ゼロ知識証明 / zero-knowledge proof |
| キーワード(3)（和/英） | 組合せ遷移問題 / combinatorial reconfiguration problem |
| キーワード(4)（和/英） | 独立集合 / independent set |
| キーワード(5)（和/英） | トークンスライディング / token sliding |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 池内 唯斗 / Yuito Ikeuchi / イケウチ ユイト |
| 第1著者 所属（和/英） | 大阪電気通信大学 (略称： 阪電通大) Osaka Electro-Communication University (略称： Osaka Electro-Communication Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 上嶋 章宏 / Akihiro Uejima / ウエジマ アキヒロ |
| 第2著者 所属（和/英） | 大阪電気通信大学 (略称： 阪電通大) Osaka Electro-Communication University (略称： Osaka Electro-Communication Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2025-03-07 14:40:00 |
| 発表時間 | 30分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2024-30 |
| 巻番号（vol） | vol.124 |
| 号番号（no） | no.424 |
| ページ範囲 | pp.29-36 |
| ページ数 | 8 |
| 発行日 | 2025-02-28 (COMP) |
[研究会発表申込システムのトップページに戻る]