Physical Zero-Knowledge Proof for Ripple Effect
This addresses the need for secure, non-revealing verification in puzzle-solving contexts, but it is incremental as it applies existing zero-knowledge proof concepts to a specific puzzle domain.
The paper tackles the problem of creating a physical zero-knowledge proof for the Ripple Effect logic puzzle, using a deck of cards to allow a prover to demonstrate knowledge of a solution without revealing it, and specifically develops a protocol to verify that a secret number does not appear among the first numbers in a list without disclosure.
Ripple Effect is a logic puzzle where the player has to fill numbers into empty cells in a rectangular grid. The grid is divided into rooms, and each room must contain consecutive integers starting from 1 to its size. Also, if two cells in the same row or column contain the same number $x$, there must be a space of at least $x$ cells separating the two cells. In this paper, we develop a physical zero-knowledge proof for the Ripple Effect puzzle using a deck of cards, which allows a prover to convince a verifier that he/she knows a solution without revealing it. In particular, given a secret number $x$ and a list of numbers, our protocol can physically verify that $x$ does not appear among the first $x$ numbers in the list without revealing $x$ or any number in the list.