Only Two Shuffles Perform Card-Based Zero-Knowledge Proof for Sudoku of Any Size

Abstract

Sudoku is a popular pencil puzzle where a player fills in the empty cells with numbers on an n × n board so that each row, column, and -block must contain all the numbers from 1 to n; a typical puzzle size is n = 9. In 2007, Gradwohl, Naor, Pinkas, and Rothblum proposed a physical zero-knowledge proof protocol for Sudoku using a physical deck of cards; their card-based protocol requires 3nℓ shuffles, where ℓ is a security parameter to eliminate the soundness error. Since the invention of this seminal protocol, several soundness-error-free protocols were constructed to reduce the number of required shuffles; the state-of-the-art one was designed in 2023, which uses shuffles. In this paper, we show that only three or two shuffles are sufficient to construct a zero-knowledge proof protocol for Sudoku, no matter how large n is, i.e., we propose two card-based protocols using constant numbers (namely, 3 and 2) of shuffles. Our proposed protocols are simple and efficient enough for people to execute for a 9 × 9 Sudoku puzzle in reality.