  Shikaku is a pencil puzzle consisting of a rectangular grid, with some cells
containing a number. The player has to partition the grid into rectangles such
that each rectangle contains exactly one number equal to the area of that
rectangle. In this paper, we propose two physical zero-knowledge proof
protocols for Shikaku using a deck of playing cards, which allow a prover to
physically show that he/she knows a solution of the puzzle without revealing
it. Most importantly, in our second protocol we develop a general technique to
physically verify a rectangle-shaped area with a certain size in a rectangular
grid, which can be used to verify other problems with similar constraints.

Cryptography and Security;Combinatorics