Card-based physical zero-knowledge proof for kakuro

Daiki Miyahara, Tatsuya Sasaki, Takaaki Mizuki, Hideaki Sone

Research output: Contribution to journalArticlepeer-review

33 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)1072-1078
Number of pages7
JournalIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Issue number9
Publication statusPublished - 2019


  • Card-based protocols
  • Cryptography
  • Kakuro
  • Physical zero-knowledge proof
  • Real-life hands-on cryptography


Dive into the research topics of 'Card-based physical zero-knowledge proof for kakuro'. Together they form a unique fingerprint.

Cite this