Physical ZKP for Makaro Using a Standard Deck of Cards
This work addresses a practical limitation for implementing secure physical zero-knowledge proofs in everyday settings, though it is incremental as it builds on existing methods.
The paper tackles the impracticality of a prior physical zero-knowledge proof protocol for the Makaro puzzle, which required duplicate cards, by proposing a new protocol that uses a standard deck of all different cards and reduces card usage asymptotically.
Makaro is a logic puzzle with an objective to fill numbers into a rectangular grid to satisfy certain conditions. In 2018, Bultel et al. developed a physical zero-knowledge proof (ZKP) protocol for Makaro using a deck of cards, which allows a prover to physically convince a verifier that he/she knows a solution of the puzzle without revealing it. However, their protocol requires several identical copies of some cards, making it impractical as a deck of playing cards found in everyday life typically consists of all different cards. In this paper, we propose a new ZKP protocol for Makaro that can be implemented using a standard deck (a deck consisting of all different cards). Our protocol also uses asymptotically less cards than the protocol of Bultel et al. Most importantly, we develop a general method to encode a number with a sequence of all different cards. This allows us to securely compute several numerical functions using a standard deck, such as verifying that two given numbers are different and verifying that a number is the largest one among the given numbers.