Two UNO Decks Efficiently Perform Zero-Knowledge Proof for Sudoku

Assume that there is a challenging Sudoku puzzle such that a prover knows a solution while a verifier does not know any solution. A zero-knowledge proof protocol allows the prover to convince the verifier that the prover knows the solution without revealing any information about it. In 2007, Gradwohl et al. constructed the first physical zero-knowledge proof protocol for Sudoku using a physical deck of playing cards; its drawback would be to have a soundness error. In 2018, Sasaki et al. improved upon the previous protocol by developing soundness-error-free protocols; their possible drawback would be to require many standard decks of playing cards, namely nine (or more) decks. In 2021, Ruangwises designed a novel protocol using only two standard decks of playing cards although it requires 322 shuffles, making it difficult to use in practical applications. In this paper, to reduce both the numbers of required decks and shuffles, we consider the use of UNO decks, which are commercially available: we propose a zero-knowledge proof protocol for Sudoku that requires only two UNO decks and 16 shuffles. Thus, the proposed protocol uses reasonable numbers of decks and shuffles, and we believe that it is efficient enough for humans to execute practically.