💻 computer science

NP-Completeness and Physical Zero-Knowledge Proof of Hotaru Beam

本論文は、論理パズル「Hotaru Beam」が NP 完全であることを示し、その解を秘密裏に証明するための物理的ゼロ知識証明プロトコルを提案しています。

原著者： Taisei Otsuji, Peter Fulla, Takuro Fukunaga

公開日 2026-03-03

📖 1 分で読めます☕ さくっと読める

原著者： Taisei Otsuji, Peter Fulla, Takuro Fukunaga

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

この論文は、**「ホタルビーム（Hotaru Beam）」というパズルが、数学的に非常に難しい問題であることを証明し、さらに「答えを知っていることを、答えを一言も言わずに相手に納得させる」**という魔法のような技術（ゼロ知識証明）を、トランプやカードを使って実際に実現する方法を提案しています。

まるで「探偵が犯人の正体を明かさずに、犯人が自分であることを証明する」ような話です。

以下に、専門用語を排し、身近な例え話を使って解説します。

1. ホタルビームって何？（パズルのルール）

まず、このパズルのルールをイメージしてください。

舞台: 格子状のマス目があるボード。
登場人物: マス目に置かれた「ホタル（円）」たち。
目的: ホタルから光の線（ビーム）を出して、すべてのホタルを一本の線でつなぐこと。
ルール:
1. 線は交差したり分岐したりしてはいけない（迷路のような一本道）。
2. 各ホタルの中には数字が入っている場合があり、その数字は「線が曲がる回数」を指定します（数字がない場合は自由）。
3. 最終的に、すべてのホタルが一つにつながっていなければなりません。

【例え話】
ホタルたちは「迷子になった子供」で、線は「手をつなぐロープ」です。数字は「子供がロープを曲げる回数」の制限です。すべての子供が手をつなぎ、一つの大きな輪になるようにロープを配置するのがゴールです。

2. なぜ難しいのか？（NP 完全性）

論文の前半では、「このパズルの正解を見つけるのは、コンピュータでも非常に大変だ」と証明しています。

NP 完全性とは？
パズルが「正解かどうか」をチェックするのは簡単ですが（答えを見れば一瞬でわかる）、**「正解をゼロから作り出す」**のは、問題が大きくなると途方もない時間がかかる、という性質です。
証明の方法:
研究者たちは、このパズルを「論理パズル（3-SAT）」という、すでに「超難問」として知られている問題に変換できることを示しました。つまり、「ホタルビームが解ければ、その論理パズルも解ける」という関係があるため、ホタルビームも同じくらい難しい（NP 完全）だと結論づけています。

【例え話】
「この巨大な迷路の出口を見つけるのは、地図を全部チェックし尽くすほど大変だ」ということを、別の有名な難問（例：「100 人の人間を部屋に割り当てる問題」）とつなげて証明したのです。

3. ゼロ知識証明（ZKP）とは？（答えを見せずに証明する魔法）

ここが論文の一番面白い部分です。

従来の問題: パズルを解いた人が「解いたよ！」と言っても、相手が「本当か？」と疑うと、答えを見せなければなりません。でも、答えを見せたら、相手も解けてしまい、パズルの面白さが消えてしまいます。
ゼロ知識証明の解決策:
「答えを一言も言わず、見せもせず」に、「私が解いていることを 100% 証明する」方法です。

【例え話：色付きのカード】
相手が「答えを知っている」と信じるために、以下の手順で行います。

カードの準備: 紙のカードに、パズルのマス目やホタルの位置を書き、裏返して並べます。
プロの動き: 答えを知っている人（プロ）は、カードを裏返したまま、パズルのルールに従って「線を引く」動作をカードの上で行います。
検証: 相手が「本当にルール通りか？」をチェックするために、特定のカードを裏返したり、カードの並びをシャッフルしたりします。
結果: 相手がチェックした結果、ルール違反が見つからなければ「プロは正解を知っているに違いない」と納得します。しかし、プロが実際にどこに線を引いたか（正解そのもの）は、相手が一度も目撃していません。

これを何回も繰り返せば、確率的に「偶然の一致」はあり得なくなるため、プロが本当に解いていると信じられます。

4. この論文のすごいところ（2 つの新しいアイデア）

既存のカードを使った証明法では、この「ホタルビーム」特有の**「曲がる回数」**というルールを隠すのが難しかったです。そこで、研究者は 2 つの新しい工夫を考案しました。

① 「線を引きながら、曲がり回数を隠す」テクニック

工夫: 線が曲がる場所を、カードの裏側で操作する「マスク（隠し絵）」のような仕組みを作りました。
例え話: 線が曲がったかどうかを相手に見せるのではなく、「ここから先は線が通っているよ」ということだけをカードで示し、「どこで曲がったか」はカードの裏側で秘密に保ちます。

② 「つながりを追跡する」テーブル

工夫: どのホタルとどのホタルがつながっているかを記録する「つながり表（Connections Table）」というカードの列を使います。
例え話: ホタル A と B がつながったら、その表に「A と B は仲良し（つながっている）」と印をつけます。パズルが終わった頃には、すべてのホタルが「仲良し」になっていることを、カードの裏側で確認します。これにより、「全部つながっている」という条件も、答えを見せずに証明できます。

5. まとめ：なぜこれが重要なのか？

この研究は、単にパズルの解き方を紹介しただけではありません。

パズルの難しさを証明した: ホタルビームは、数学的に「解くのが超難しい」問題であることを示しました。
物理的な「秘密保持」技術を開発した: コンピュータの暗号技術（ゼロ知識証明）を、トランプやカードという誰でも持っている道具で実現できることを示しました。

【最終的なメッセージ】
「答えを教えずに、『私が知っている』と相手を納得させる」という魔法は、インターネットのセキュリティ（パスワード入力など）にも使われる重要な技術です。この論文は、その魔法を「カードゲーム」のように誰でも理解し、実際に手で行える形にまで落とし込んだ画期的なものです。

つまり、「数学の難しい証明」を「カード遊び」に変えて、誰でも体験できるようにしたというのが、この論文の最大の功績です。

論文「Hotaru Beam の NP 完全性と物理的ゼロ知識証明」の技術的サマリー

本論文は、パズル「Hotaru Beam（ホタルビーム）」の計算複雑性クラスに関する証明と、その解を秘密に保持したまま検証者に証明する「物理的ゼロ知識証明（Physical Zero-Knowledge Proof, ZKP）」の構築を扱っています。以下に、問題定義、手法、主要な貢献、結果、および意義について詳細にまとめます。

1. 問題定義：Hotaru Beam

Hotaru Beam は、日本のパズルメーカー・ニコリによって考案された論理パズルです。

盤面: 長方形のグリッド上に、いくつかの「ホタル（円）」が配置されています。
ルール:
1. 各ホタルの境界上の特定の点（ドット）から光線（ビーム）を引き、他のホタルの境界で止めます。
2. ビームは交差したり分岐したりしてはなりません。
3. 各ホタル内部の数字は、そのホタルから出るビームの「曲がり回数（ベンド数）」を指定します（数字がない場合は制限なし）。
4. 連結性制約: 全てのホタルがビームによって単一の連結成分に繋がっていなければなりません。
目的: 全ての制約を満たすビームの配置（解）を見つけること。

2. 主要な貢献と結果

2.1 NP 完全性の証明

著者は、Hotaru Beam がNP 完全であることを証明しました。

手法: 「平面単調 3-SAT（Planar Monotone 3-SAT）」問題からの多項式時間帰着（Reduction）を用いています。
構成: 変数、正の節、負の節に対応する「ガジェット（小道具）」を Hotaru Beam のグリッド上に設計しました。
- 変数ガジェットは、ビームの曲がり方（真/偽）を表現します。
- 節ガジェットは、変数との接続可能性を表現します。
- 変数ガジェット同士をループ状に接続し、節ガジェットからのビームが変数ガジェットに到達できるかどうかが、3-SAT の充足可能性に対応します。
結果: Hotaru Beam が解を持つことと、対応する 3-SAT 式が充足可能であることは同値であるため、問題の NP 完全性が示されました。

2.2 物理的ゼロ知識証明（ZKP）の構築

Hotaru Beam の解を知っていることを、解そのものを明かさずに検証者に証明するプロトコルを提案しました。

特徴: 日常的な道具（カード）のみを用いて人間が実行可能な「物理的 ZKP」です。
証明者（Peter）: 解を知っている人。
検証者（Vera）: 解を知らない人。
目的: Peter が解を知っていることを Vera に確信させつつ、解の具体的な経路や構造を一切漏らさないこと。

3. 提案プロトコルの詳細と手法

本プロトコルは、カードを用いて盤面と接続状態を暗号化・管理する仕組みに基づいています。

3.1 基本構成要素

カード: 表に記号（♣, ♠, ♡, ♢）や数字、裏面は全て同じ。
盤面（Board）: グリッドの各点を表すカードの配置。
- 初期状態：ホタルの位置に数字カード、それ以外は「空（♡）」を表すカード。
- 進行中：ビームが通った場所を「壁（♣）」に置き換えます。
接続テーブル（Connections Table）: ホタル間の連結状態を管理する論理カードの配列。
- $n$ 個のホタルに対し、 $n \times n$ の論理カード対（True/False を表すカードペア）を保持します。
- 列 $i$ と行 $j$ のカード対が「True」であれば、ホタル $i$ と $j$ が連結されていることを意味します。

3.2 核心的なプロトコル

解の証明は、ビームを順次描画（埋め込み）するプロセスで行われます。

セグメント埋め込みプロトコル（Segment Embedding Protocol）:
- ビームの一部（直線区間）を描く際、盤面の「空（♡）」カードを「壁（♣）」や「方向指示（♢）」に置き換えます。
- 工夫: どの方向に、どの長さ（ $l$ $l$ ）のビームを描いたかを Vera に知られないようにします。
  - 「マスクシーケンス」を作成し、シャッフル（Pile-shifting shuffle）を用いて長さ $l$ や方向を隠蔽します。
  - 曲がり回数（ベンド数）の制約がある場合、その回数が正確に守られていることを、カードの配置パターンで検証可能にします。
接続テーブルの更新:
- ビームでホタル $s$ と $t$ を繋ぐと、接続テーブルの $(s, t)$ および $(t, s)$ のエントリを「True」に更新します。
- この際、論理演算（OR 演算）を用いて、既存の連結情報を維持しつつ新しい連結情報を追加します。
連結性制約の最終検証:
- 全てのビームを描き終えた後、接続テーブルの全てのカード対が「True」になっていることを確認します。
- グラフが連結であることを示すために、連結している列同士を反復的に結合（OR 演算）する操作を $n^2$ 回行い、最終的に Vera が全てのカードが True であることを確認します。

3.3 新規なアイデア

既存の ZKP（数独やスリザリンクなど）との違いとして、以下の 2 点が革新的です。

ベンド数の制約の実装: 単なる連結性だけでなく、「曲がり回数」という幾何学的制約を、カードの配置とプロトコルで厳密に管理・隠蔽する方法を提案しました。
接続状態の追跡: 幾何学的な経路を描画する過程で、論理的な「連結成分」の状態をカードテーブルで追跡・更新する仕組みを設計しました。

4. 意義と結論

理論的意義: Hotaru Beam が NP 完全であることを初めて証明し、その計算難易度を明確にしました。
実用的・教育的意義:
- 複雑な幾何学的制約（ベンド数）を含むパズルに対しても、物理的なカードを用いたゼロ知識証明が構築可能であることを示しました。
- 提案された「セグメント埋め込み」や「接続テーブル」の手法は、他の幾何学的パズルやグラフ構造の存在証明に応用可能な汎用性を持っています。
セキュリティ: 完全なゼロ知識性（Zero-knowledge）が保証されており、Vera は Peter が解を知っていること以外、何の追加情報も得られません。

本論文は、パズル理論と暗号理論（ゼロ知識証明）の交差点において、具体的な物理的実装を通じて新しい知見を提供した重要な研究です。