The search functionality is under construction.

The search functionality is under construction.

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

Daiki MIYAHARA

Tohoku University,National Institute of Advanced Industrial Science and Technology

Tatsuya SASAKI

Tohoku University

Takaaki MIZUKI

Tohoku University

Hideaki SONE

Tohoku University

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.

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 -