Physical Zero-Knowledge Proof for Ripple Effect

Abstract

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.

A preliminary version of this paper has appeared at WALCOM 2021

References in corpus (2)

• Two Standard Decks of Playing Cards are Sufficient for a ZKP for Sudoku
• Physical ZKP for Connected Spanning Subgraph: Applications to Bridges Puzzle and Other Problems

Cited by in corpus (10)

• Two Standard Decks of Playing Cards are Sufficient for a ZKP for Sudoku
• Physical ZKP for Makaro Using a Standard Deck of Cards
• Contagion Source Detection in Epidemic and Infodemic Outbreaks: Mathematical Analysis and Network Algorithms
• Physical Zero-Knowledge Proof for Ball Sort Puzzle
• An Improved Physical ZKP for Nonogram and Nonogram Color
• Using Five Cards to Encode Each Integer in $\mathbb{Z}/6\mathbb{Z}$
• Printing Protocol: Physical ZKPs for Decomposition Puzzles
• Verifying the First Nonzero Term: Physical ZKPs for ABC End View, Goishi Hiroi, and Toichika
• NP-Completeness and Physical Zero-Knowledge Proofs for Zeiger
• Tatami Printer: Physical ZKPs for Tatami Puzzles