💻 computer science

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

This paper establishes that the logic puzzle Hotaru Beam is NP-complete and proposes a physical zero-knowledge proof protocol that allows a player to demonstrate knowledge of a solution without revealing the solution itself.

Original authors: Taisei Otsuji, Peter Fulla, Takuro Fukunaga

Published 2026-03-03

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Taisei Otsuji, Peter Fulla, Takuro Fukunaga

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: A Light Puzzle and a Magic Trick

Imagine a puzzle called Hotaru Beam (Firefly Beam). You have a grid with glowing fireflies placed on it. Your job is to draw lines (beams of light) connecting all the fireflies together. But there are strict rules:

The lines can't cross or branch out.
Some fireflies have numbers on them, telling you exactly how many times the beam must "bend" (turn a corner) before it hits another firefly.
The Goal: All fireflies must end up connected in one big, single group.

The paper does two main things:

It proves the puzzle is hard. (Mathematically, it's "NP-complete," meaning as the puzzle gets bigger, it becomes exponentially harder to solve, and no computer can solve every version quickly).
It invents a magic trick. This trick allows someone (the "Prover") to prove to a skeptic (the "Verifier") that they have solved the puzzle, without showing them the solution.

Part 1: Why is this puzzle so hard? (The NP-Completeness)

Think of the puzzle like a massive maze where every turn you make affects every other turn. The authors proved that solving Hotaru Beam is just as hard as solving the most famous logic problems in computer science (like the "3-SAT" problem).

The Analogy:
Imagine you are trying to organize a massive dinner party where every guest has specific seating rules based on who they like and dislike. If you can find a seating chart that satisfies everyone, you've solved the puzzle. The authors showed that Hotaru Beam is essentially a visual version of this seating chart problem. If you could solve Hotaru Beam instantly, you could instantly solve any complex logic problem in existence. Since we know those logic problems are incredibly difficult, Hotaru Beam is too.

Part 2: The Magic Trick (Physical Zero-Knowledge Proof)

Now, imagine you solved the puzzle, but you want to prove it to your friend, Vera, without letting her peek at your paper. If you just show her the answer, she learns your secret. If you don't show her, she won't believe you.

The authors created a Physical Zero-Knowledge Proof (ZKP). This is a game played with playing cards (or similar items) where you can prove you know the solution without revealing a single detail of it.

The Setup: The Board and the Ledger

To play this game, you need two things:

The Board: A grid of cards representing the puzzle. Empty spots are marked with a heart (♡), and fireflies are marked with numbers.
The Connections Ledger: A list of cards tracking which fireflies are connected. Initially, no one is connected.

The Core Mechanism: The "Beam Embedding"

This is the coolest part. You have to draw a beam on the board, but you can't just show Vera the line. Instead, you use a special card-shuffling routine.

The Analogy: The Invisible Paintbrush
Imagine you have a magic paintbrush that turns empty spots (hearts) into blocked spots (spades ♣) to show where your beam went.

The Problem: If you just paint the line, Vera sees the whole path.
The Solution: You use a "Mask." You take a long strip of cards that looks like a random mix of hearts and spades. You secretly align this strip under your board.
The Shuffle: You shuffle the cards in a way that moves the "paint" (the spades) to the exact spots where your beam goes, but Vera only sees that the cards changed from hearts to spades. She doesn't see where you moved them or how long the line is.

It's like having a magic eraser that only erases the specific path you drew, but to an observer, it just looks like the paper changed color in a mysterious way.

The "Bend" Challenge

The hardest part of Hotaru Beam is the bending constraint. Some fireflies say, "My beam must turn exactly 2 times."

The Challenge: How do you prove you turned exactly 2 times without showing the turns?
The Trick: The authors invented a protocol where you can count your turns using the cards. You create a "counter" with the cards. Every time you make a turn, you swap a specific card. At the end, you prove to Vera that you have exactly the right number of "turn cards" in your hand, without showing her the shape of the beam.

The "Connectivity" Check

Finally, you have to prove that all fireflies are connected.

The Ledger: Throughout the game, you update a "Connections Ledger." Every time you connect Firefly A to Firefly B, you mark them as "friends" in the ledger.
The Final Proof: At the end, you shuffle the ledger cards. You prove to Vera that every single firefly is now marked as "connected" to every other firefly. She sees that the ledger is full of "True" (T) cards, meaning everyone is in the same group, but she never saw the actual lines drawn on the board.

Why Does This Matter?

It's a New Kind of Security: Usually, Zero-Knowledge Proofs are done on computers with complex math. This paper shows you can do it with physical cards that anyone can understand. It's like a magic trick you can perform at a dinner party to prove you know a secret without telling it.
It Solves a Hard Problem: It proves that even for very difficult puzzles (like Hotaru Beam), you can verify a solution without cheating.
New Tools: The authors created new "card tricks" (protocols) for handling lines and bends. These tricks could be used to create similar proof games for other types of puzzles, like mazes or network designs.

Summary in One Sentence

The authors proved that the "Firefly Beam" puzzle is mathematically very hard, but they also invented a clever card game that lets you prove you solved it to a skeptic without ever showing them the actual solution, using magic shuffles and invisible paintbrushes.

1. Problem Definition: Hotaru Beam

Hotaru Beam is a logic puzzle created by Nikoli, played on a rectangular grid containing circles ("fireflies").

Objective: Connect all fireflies into a single connected component by drawing lines (beams) that follow specific rules.
Constraints:
1. Non-intersection/Branching: Beams cannot cross or branch. A beam cannot end at a firefly's starting dot if another beam originates there.
2. Bending Constraint: Each firefly may contain a number indicating the exact number of bends (turns) the beam starting from it must make. If no number is present, the bend count is unrestricted.
3. Connectivity Constraint: All fireflies must eventually form a single connected component.
Input/Output: The input is the grid configuration; the output is a valid set of beams satisfying all constraints.

2. Methodology

The paper employs two distinct methodological approaches:

Complexity Theory: To determine the computational complexity of the puzzle.
Cryptography (Physical ZKP): To design a protocol where a Prover (Peter) convinces a Verifier (Vera) that they know a solution without revealing the solution itself, using only physical cards.

A. NP-Completeness Proof

The authors prove that deciding whether a Hotaru Beam instance has a solution is NP-complete.

Membership in NP: A solution can be verified in polynomial time.
NP-Hardness: Established via a reduction from the Planar Monotone 3-SAT problem (known to be NP-complete).
- Reduction Strategy: The authors construct "gadgets" on the Hotaru Beam grid to simulate Boolean variables and clauses.
  - Variable Gadgets: Simulate true/false states using beam configurations with specific bend counts (0, 1, or 2).
  - Clause Gadgets: Simulate logical OR operations. Positive clauses are placed above the x-axis, negative clauses below.
  - Connectivity: The global connectivity constraint of the puzzle forces the logical consistency of the variable assignments. A valid solution to the puzzle exists if and only if the 3-SAT formula is satisfiable.

B. Physical Zero-Knowledge Proof (ZKP) Protocol

The authors design a card-based physical ZKP. The protocol relies on a deck of cards with distinct faces (♣, ♠, ♡, ♢, and numbers) and a "board" representation.

Key Components of the Protocol:

Data Structures:
- The Board: A $w \times h$ grid of cards representing the puzzle board. Face-down cards represent empty grid points ( $\heartsuit$ ), while specific cards represent fireflies. As beams are drawn, $\heartsuit$ cards are replaced with $\clubsuit$ (occupied) or $\diamondsuit$ (turning points).
- Connections Table: An $n \times n$ structure (where $n$ is the number of fireflies) tracking connectivity. It uses "logical card pairs" ( $\clubsuit\heartsuit$ for True, $\heartsuit\clubsuit$ for False) to indicate if two fireflies are in the same connected component.
Core Subroutines:
- Pile-Shifting Shuffle: Randomizes the order of card piles to hide the prover's actions.
- Pile Choosing: Allows the prover to select a specific pile (e.g., a specific row/column of the board) without the verifier knowing which one was chosen.
- Logical Operations: Protocols to compute logical OR ( $b_1 \lor b_2$ ) on hidden card pairs to update the connectivity table.
The "Segment Embedding" Protocol (Innovation):
This is the core mechanism for drawing a beam without revealing its path or bend count.
- Process: Peter selects a starting card (firefly dot) and a length $l$ . He replaces a sequence of $\heartsuit$ cards with $\clubsuit$ cards (path) and a final $\diamondsuit$ card (bend point).
- Hiding Information:
  - Length ( $l$ ): Hidden via a "mask sequence" and shuffling.
  - Direction: Hidden by preparing two mask sequences (left/right) and secretly choosing one.
  - Bend Count: If the bend count is not fixed by the puzzle, Peter adds "dummy" segments of length 0 to make the total number of segments constant, hiding the actual number of bends.
- Verification: The verifier checks that the replacement cards match the protocol rules (e.g., ensuring a $\diamondsuit$ appears at the correct relative position) without seeing the actual path.
Connectivity Verification:
After embedding all beams, Peter updates the Connections Table. He uses logical OR operations on the table columns to merge connected components. Finally, he proves that all fireflies are connected (all pairs in the table are True) without revealing the specific connections.

3. Key Contributions

Complexity Classification: First proof that Hotaru Beam is NP-complete.
Novel Physical ZKP: The first physical ZKP for Hotaru Beam.
Innovative Protocols:
- Segment Embedding: A method to draw lines on a grid and enforce bend constraints while hiding the geometry of the line.
- Dynamic Connectivity Tracking: A method to maintain and verify the connectivity of a graph (the solution) dynamically during the ZKP process using a logical card table.
Handling Geometric Constraints: Successfully integrating the "bend count" constraint into a physical ZKP, which is more complex than standard connectivity puzzles like Numberlink or Bridges.

4. Results

Theoretical: The problem is confirmed to be NP-complete.
Protocol: A deterministic physical ZKP is constructed that satisfies:
- Completeness: If Peter knows the solution, Vera accepts.
- Soundness: If Peter does not know the solution, Vera rejects (with high probability, though the paper notes their specific protocol is deterministic with no error allowance in the described steps).
- Zero-Knowledge: Vera learns nothing about the solution (path, bends, or connectivity structure) other than its existence.
Simulation: The paper provides detailed step-by-step examples (Figures 1–10) demonstrating how the card manipulations simulate the puzzle solution.

5. Significance

Advancement in Puzzle ZKPs: This work extends the scope of physical ZKPs from standard connectivity puzzles (like Sudoku or Slitherlink) to puzzles with complex geometric constraints (bend counts).
Educational Value: The use of everyday cards makes complex cryptographic concepts (NP-completeness, zero-knowledge) accessible to non-experts.
Generalizability: The "segment embedding" and "connectivity table" techniques are proposed as valuable tools for designing ZKPs for other geometric problems and graph-based puzzles.
Practical Application: It demonstrates that secure, privacy-preserving verification of puzzle solutions is feasible without digital computers, relying solely on physical manipulation and human interaction.

In summary, the paper successfully bridges computational complexity theory and practical cryptography, providing a rigorous proof of the difficulty of Hotaru Beam and a creative, implementable protocol for verifying solutions privately.