Search papers, labs, and topics across Lattice.
The paper demonstrates that the Hotaru Beam logic puzzle is NP-complete, establishing its computational complexity. It addresses the problem of proving knowledge of a solution without revealing the solution itself. The authors present a physical zero-knowledge proof protocol for Hotaru Beam, enabling verifiable solution possession without information leakage.
Hotaru Beam, a pencil-and-paper puzzle, is now formally NP-complete, and you can prove you solved it without revealing the solution using physical objects.
Hotaru Beam is a logic puzzle which objective is to connect circles placed on a grid by drawing only lines with specified starting points and numbers of bends. A zero-knowledge proof is a communication protocol that allows one player to persuade the other that they are in possession of a certain piece of information without actually revealing it. We show that Hotaru Beam is NP-complete and present a physical zero-knowledge proof (i.e. implementable using physical items) for proving that one knows a solution to the puzzle.
