Card-Based Zero-Knowledge Proof for Sudoku

Fun with Algorithms (2018)

Tatsuya Sasaki Takaaki Mizuki Hideaki Sone

Citation

Reference

Related Paper

Citation Trend

Abstract:

In 2009, Gradwohl, Naor, Pinkas, and Rothblum proposed physical zero-knowledge proof protocols for Sudoku. That is, for a puzzle instance of Sudoku, their excellent protocols allow a prover to convince a verifier that there is a solution to the Sudoku puzzle and that he/she knows it, without revealing any information about the solution. The possible drawback is that the existing protocols have a soundness error with a non-zero probability or need special cards (such as scratch-off cards). Thus, in this study, we propose new protocols to perform zero-knowledge proof for Sudoku that use a normal deck of playing cards and have no soundness error. Our protocols can be easily implemented by humans with a reasonable number of playing cards.

Keywords:

Zero-knowledge proof

Soundness

Gas meter prover

Zero (linguistics)

Proof of concept

Topics:

graph theory and CDMA systems

10.4230/lipics.fun.2018.29

Cite

Card-Based Cryptographic Protocols Using a Minimal Number of Cards

Lecture notes in computer science (2015)

Alexander Koch Stefan Walzer Kevin Härtel

Las vegas

10.1007/978-3-662-48797-6_32

Cite

Citations (87)

The Minimum Number of Cards in Practical Card-Based Protocols

Lecture notes in computer science (2017)

Julia Kästner Alexander Koch Stefan Walzer Daiki Miyahara Yu‐ichi Hayashi

Shuffling

Copying

Negation

10.1007/978-3-319-70700-6_5

Cite

Citations (44)

Cryptographic and Physical Zero-Knowledge Proof: From Sudoku to Nonogram

Lecture notes in computer science (2010)

Yu-Feng Chien Wing-Kai Hon

Zero-knowledge proof

Zero (linguistics)

Gas meter prover

Proof of concept

10.1007/978-3-642-13122-6_12

Cite

Citations (40)

Efficient Card-Based Protocols for Generating a Hidden Random Permutation Without Fixed Points

Lecture notes in computer science (2015)

Ishikawa Rie Eikoh Chida Takaaki Mizuki

Bit-reversal permutation

10.1007/978-3-319-21819-9_16

Cite

Citations (64)

Efficient card-based zero-knowledge proof for Sudoku

Theoretical Computer Science (2020)

Tatsuya Sasaki Daiki Miyahara Takaaki Mizuki Hideaki Sone

In 2009, Gradwohl, Naor, Pinkas, and Rothblum proposed physical zero-knowledge proof protocols for Sudoku. That is, for a puzzle instance of Sudoku, their excellent protocols allow a prover to convince a verifier that there is a solution to the Sudoku puzzle and the prover knows it, without revealing any information about the solution. The possible drawback is that the existing protocols have an extractability error with a non-zero probability, or need special cards (such as scratch-off cards). Thus, in this study, we propose new protocols to perform zero-knowledge proof of knowledge for Sudoku using a normal deck of playing cards with no extractability error. Our protocols can be easily implemented by humans with a reasonable number of playing cards.

Gas meter prover

Zero-knowledge proof

Zero (linguistics)

Proof of concept

10.1016/j.tcs.2020.05.036

Cite

Citations (60)

Six-Card Secure AND and Four-Card Secure XOR

Lecture notes in computer science (2009)

Takaaki Mizuki Hideaki Sone

Bitwise operation

XOR gate