IEICE TRANSACTIONS on Fundamentals
Card-Based Physical Zero-Knowledge Proof for Kakuro
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E102-A No.9 pp.1072-1078
- Publication Date
- 2019/09/01
- Publicized
- 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
Authors
Daiki MIYAHARA
Tohoku University,National Institute of Advanced Industrial Science and Technology
Tatsuya SASAKI
Tohoku University
Takaaki MIZUKI
Tohoku University
Hideaki SONE
Tohoku University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Daiki MIYAHARA, Tatsuya SASAKI, Takaaki MIZUKI, Hideaki SONE, "Card-Based Physical Zero-Knowledge Proof for Kakuro" in IEICE TRANSACTIONS on Fundamentals,
vol. E102-A, no. 9, pp. 1072-1078, September 2019, doi: 10.1587/transfun.E102.A.1072.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E102.A.1072/_p
Copy
@ARTICLE{e102-a_9_1072,
author={Daiki MIYAHARA, Tatsuya SASAKI, Takaaki MIZUKI, Hideaki SONE, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Card-Based Physical Zero-Knowledge Proof for Kakuro},
year={2019},
volume={E102-A},
number={9},
pages={1072-1078},
abstract={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.},
keywords={},
doi={10.1587/transfun.E102.A.1072},
ISSN={1745-1337},
month={September},}
Copy
TY - JOUR
TI - Card-Based Physical Zero-Knowledge Proof for Kakuro
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1072
EP - 1078
AU - Daiki MIYAHARA
AU - Tatsuya SASAKI
AU - Takaaki MIZUKI
AU - Hideaki SONE
PY - 2019
DO - 10.1587/transfun.E102.A.1072
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E102-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2019
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.
ER -
English
