Ripple Effect is a logic puzzle with an objective to fill numbers into a
rectangular grid divided into rooms. Each room must contain consecutive
integers starting from 1 to its size. Also, if two cells in the same row or
column have the same number $x$, the space separating the two cells must be at
least $x$ cells. In this paper, we propose a physical protocol of
zero-knowledge proof for Ripple Effect puzzle using a deck of cards, which
allows a prover to physically show that he/she knows a solution without
revealing it. In particular, we develop a physical protocol that, given a
secret number $x$ and a list of numbers, verifies that $x$ does not appear
among the first $x$ numbers in the list without revealing $x$ or any number in
the list.

Go to Source of this post
Author Of this post: <a href="http://arxiv.org/find/cs/1/au:+Ruangwises_S/0/1/0/all/0/1">Suthee Ruangwises</a>, <a href="http://arxiv.org/find/cs/1/au:+Itoh_T/0/1/0/all/0/1">Toshiya Itoh</a>

By admin