TY - JOUR

T1 - Card-based physical zero-knowledge proof for kakuro

AU - Miyahara, Daiki

AU - Sasaki, Tatsuya

AU - Mizuki, Takaaki

AU - Sone, Hideaki

N1 - Funding Information:
We thank the anonymous referees, whose comments helped us to improve the presentation of the paper. This work was supported by JSPS KAKENHI Grant Number 17K00001.
Publisher Copyright:
Copyright © 2019 The Institute of Electronics, Information and Communication Engineers.

PY - 2019

Y1 - 2019

N2 - 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.

AB - 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.

KW - Card-based protocols

KW - Cryptography

KW - Kakuro

KW - Physical zero-knowledge proof

KW - Real-life hands-on cryptography

UR - http://www.scopus.com/inward/record.url?scp=85072660315&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85072660315&partnerID=8YFLogxK

U2 - 10.1587/transfun.E102.A.1072

DO - 10.1587/transfun.E102.A.1072

M3 - Article

AN - SCOPUS:85072660315

SN - 0916-8508

VL - E102A

SP - 1072

EP - 1078

JO - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

JF - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

IS - 9

ER -