Card-Based Physical Zero-Knowledge Proof for Kakuro

Daiki MIYAHARA  Tatsuya SASAKI  Takaaki MIZUKI  Hideaki SONE  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E102-A   No.9   pp.1072-1078
Publication Date: 2019/09/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E102.A.1072
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: Cryptography and Information Security
Keyword: 
cryptography,  card-based protocols,  real-life hands-on cryptography,  Kakuro,  physical zero-knowledge proof,  

Full Text: PDF(1.2MB)>>
Buy this Article




Summary: 
Kakuro is a popular logic puzzle, in which a player fills in all empty squares with digits from 1 to 9 so that the sum of digits in each (horizontal or vertical) line is equal to a given number, called a clue, and digits in each line are all different. In 2016, Bultel, Dreier, Dumas, and Lafourcade proposed a physical zero-knowledge proof protocol for Kakuro using a deck of cards; their proposed protocol enables a prover to convince a verifier that the prover knows the solution of a Kakuro puzzle without revealing any information about the solution. One possible drawback of their protocol would be that the protocol is not perfectly extractable, implying that a prover who does not know the solution can convince a verifier with a small probability; therefore, one has to repeat the protocol to make such an error become negligible. In this paper, to overcome this, we design zero-knowledge proof protocols for Kakuro having perfect extractability property. Our improvement relies on the ideas behind the copy protocols in the field of card-based cryptography. By executing our protocols with a real deck of physical playing cards, humans can practically perform an efficient zero-knowledge proof of knowledge for Kakuro.