research-article

How to construct physical zero-knowledge proofs for puzzles with a “single loop” condition

Authors:

Pascal Lafourcade,

Daiki Miyahara,

Takaaki Mizuki,

Tatsuya Sasaki,

Hideaki SoneAuthors Info & Claims

Volume 888, Issue C

Pages 41 - 55

https://doi.org/10.1016/j.tcs.2021.07.019

Published: 04 October 2021 Publication History

Abstract

We propose a technique to construct physical Zero-Knowledge Proof (ZKP) protocols for puzzles that require a single loop draw feature. Our approach is based on the observation that a loop has only one hole and this property remains stable by some simple transformations. Using this trick, we can transform a simple big loop, which is visible to anyone, into the solution loop by using transformations that do not disclose any information about the solution. We illustrate our technique by applying it to construct physical ZKP protocols for two Nikoli puzzles: Slitherlink and Masyu.

References

[1]

Slitherlink, Nikoli (1989) : https://www.nikoli.co.jp/en/puzzles/slitherlink.html.

[2]

Y. Abe, M. Iwamoto, K. Ohta, Efficient private PEZ protocols for symmetric functions, in: D. Hofheinz, A. Rosen (Eds.), Theory of Cryptography, in: LNCS, vol. 11891, Springer, Cham, 2019, pp. 372–392,.

Digital Library

[3]

J. Balogh, J.A. Csirik, Y. Ishai, E. Kushilevitz, Private computation using a PEZ dispenser, Theor. Comput. Sci. 306 (1–3) (2003) 69–84,.

[4]

X. Bultel, J. Dreier, J. Dumas, P. Lafourcade, D. Miyahara, T. Mizuki, A. Nagao, T. Sasaki, K. Shinagawa, H. Sone, Physical zero-knowledge proof for Makaro, in: T. Izumi, P. Kuznetsov (Eds.), SSS 2018, in: LNCS, vol. 11201, Springer, 2018, pp. 111–125,.

[5]

X. Bultel, J. Dreier, J.-G. Dumas, P. Lafourcade, Physical zero-knowledge proofs for Akari, Takuzu, Kakuro and KenKen, in: E.D. Demaine, F. Grandoni (Eds.), Fun with Algorithms 2016, in: LIPIcs, vol. 49, 2016, pp. 8:1–8:20,.

[6]

Y.-F. Chien, W.-K. Hon, Cryptographic and physical zero-knowledge proof: from Sudoku to nonogram, in: P. Boldi, L. Gargano (Eds.), Fun with Algorithms 2010, in: LNCS, vol. 6099, Springer, 2010, pp. 102–112,.

[7]

C. Crépeau, J. Kilian, Discreet solitary games, in: D.R. Stinson (Ed.), CRYPTO 1993, in: LNCS, vol. 773, Springer, Berlin, Heidelberg, 1994, pp. 319–330,.

[8]

P. D'Arco, R.D. Prisco, Secure computation without computers, Theor. Comput. Sci. 651 (2016) 11–36,.

Digital Library

[9]

B. den Boer, More efficient match-making and satisfiability: the five card trick, in: J. Quisquater, J. Vandewalle (Eds.), EUROCRYPT 1989, in: LNCS, vol. 434, Springer, 1989, pp. 208–217,.

[10]

J. Dumas, P. Lafourcade, D. Miyahara, T. Mizuki, T. Sasaki, H. Sone, Interactive physical zero-knowledge proof for Norinori, in: D.-Z. Du, Z. Duan, C. Tian (Eds.), COCOON 2019, in: LNCS, vol. 11653, Springer, 2019, pp. 166–177,.

Digital Library

[11]

Friedman, E. : Pearl puzzles are NP-complete. http://www.stetson.edu/~efriedma/papers/pearl.pdf.

[12]

O. Goldreich, A. Kahan, How to construct constant-round zero-knowledge proof systems for NP, J. Cryptol. 9 (3) (1996) 167–189,.

Digital Library

[13]

S. Goldwasser, S. Micali, C. Rackoff, The knowledge complexity of interactive proof-systems, in: STOC 1985, ACM, 1985, pp. 291–304,.

Digital Library

[14]

R. Gradwohl, M. Naor, B. Pinkas, G.N. Rothblum, Cryptographic and physical zero-knowledge proof systems for solutions of Sudoku puzzles, Theory Comput. Syst. 44 (2) (2009) 245–268,.

Digital Library

[15]

R. Ishikawa, E. Chida, T. Mizuki, Efficient card-based protocols for generating a hidden random permutation without fixed points, in: C.S. Calude, M.J. Dinneen (Eds.), UCNC 2015, in: LNCS, vol. 9252, Springer, 2015, pp. 215–226,.

[16]

J. Kastner, A. Koch, S. Walzer, D. Miyahara, Y. Hayashi, T. Mizuki, H. Sone, The minimum number of cards in practical card-based protocols, in: T. Takagi, T. Peyrin (Eds.), ASIACRYPT 2017, in: LNCS, vol. 10626, Springer, 2017, pp. 126–155,.

Digital Library

[17]

G. Kendall, A. Parkes, K. Spoerer, A survey of NP-complete puzzles, ICGA J. 31 (2008) 13–34,.

[18]

A. Koch, M. Schrempp, M. Kirsten, Card-based cryptography meets formal verification, in: S.D. Galbraith, S. Moriai (Eds.), ASIACRYPT 2019, in: LNCS, vol. 11921, Springer, Cham, 2019, pp. 488–517,.

Digital Library

[19]

A. Koch, S. Walzer, Foundations for actively secure card-based cryptography, in: M. Farach-Colton, G. Prencipe, R. Uehara (Eds.), Fun with Algorithms 2021, in: LIPIcs, vol. 157, 2020, pp. 17:1–17:23,.

[20]

A. Koch, S. Walzer, K. Härtel, Card-based cryptographic protocols using a minimal number of cards, in: T. Iwata, J.H. Cheon (Eds.), ASIACRYPT 2015, in: LNCS, vol. 9452, Springer, 2015, pp. 783–807,.

Digital Library

[21]

J. Kölker, Selected Slither Link variants are NP-complete, J. Inf. Process. 20 (3) (2012) 709–712,.

[22]

P. Lafourcade, D. Miyahara, T. Mizuki, T. Sasaki, H. Sone, A physical ZKP for Slitherlink: how to perform physical topology-preserving computation, in: S. Heng, J. López (Eds.), Information Security Practice and Experience - 15th International Conference, in: LNCS, vol. 11879, ISPEC 2019, Springer, 2019, pp. 135–151,.

[23]

D. Miyahara, Y. Hayashi, T. Mizuki, H. Sone, Practical card-based implementations of Yao's millionaire protocol, Theor. Comput. Sci. 803 (2020) 207–221,.

Digital Library

[24]

D. Miyahara, L. Robert, P. Lafourcade, S. Takeshige, T. Mizuki, K. Shinagawa, A. Nagao, H. Sone, Card-based ZKP protocols for Takuzu and Juosan, in: M. Farach-Colton, G. Prencipe, R. Uehara (Eds.), 10th International Conference on Fun with Algorithms (FUN 2020), in: Leibniz International Proceedings in Informatics (LIPIcs), vol. 157, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2020, pp. 20:1–20:21. https://drops.dagstuhl.de/opus/volltexte/2020/12781.

[25]

T. Mizuki, Card-based protocols for securely computing the conjunction of multiple variables, Theor. Comput. Sci. 622 (C) (2016) 34–44,.

Digital Library

[26]

T. Mizuki, M. Kumamoto, H. Sone, The five-card trick can be done with four cards, in: X. Wang, K. Sako (Eds.), ASIACRYPT 2012, in: LNCS, vol. 7658, Springer, Berlin, Heidelberg, 2012, pp. 598–606,.

Digital Library

[27]

T. Mizuki, H. Sone, Six-card secure AND and four-card secure XOR, in: X. Deng, J.E. Hopcroft, J. Xue (Eds.), Frontiers in Algorithmics, in: LNCS, vol. 5598, FAW 2009, Springer, 2009, pp. 358–369,.

Digital Library

[28]

T. Moran, M. Naor, Basing cryptographic protocols on tamper-evident seals, Theor. Comput. Sci. 411 (10) (2010) 1283–1310,.

Digital Library

[29]

V. Niemi, A. Renvall, Secure multiparty computations without computers, Theor. Comput. Sci. 191 (1–2) (1998) 173–183,.

Digital Library

[30]

A. Nishimura, Y. Hayashi, T. Mizuki, H. Sone, Pile-shifting scramble for card-based protocols, IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 101 (9) (2018) 1494–1502,.

[31]

L. Robert, D. Miyahara, P. Lafourcade, T. Mizuki, Physical zero-knowledge proof for Suguru puzzle, in: S. Devismes, N. Mittal (Eds.), Stabilization, Safety, and Security of Distributed Systems, in: LNCS, vol. 12514, Springer, Cham, 2020, pp. 235–247,.

Digital Library

[32]

L. Robert, D. Miyahara, P. Lafourcade, T. Mizuki, Interactive physical ZKP for connectivity: applications to Nurikabe and Hitori, in: L. De Mol, A. Weiermann, F. Manea, D. Fernández-Duque (Eds.), Beyond the Horizon of Computability, in: LNCS, vol. 12813, Springer, Cham, 2021, pp. 373–384,.

Digital Library

[33]

S. Ruangwises, T. Itoh, Physical zero-knowledge proof for numberlink puzzle and k vertex-disjoint paths problem, New Gener. Comput. 39 (2021) 3–17,.

Digital Library

[34]

S. Ruangwises, T. Itoh, Physical zero-knowledge proof for Ripple Effect, in: S. Hong, S. Nandy, R. Uehara (Eds.), WALCOM: Algorithms and Computation, in: LNCS, vol. 11737, Springer, Cham, 2021, pp. 296–307,.

Digital Library

[35]

T. Sasaki, D. Miyahara, T. Mizuki, H. Sone, Efficient card-based zero-knowledge proof for Sudoku, Theor. Comput. Sci. 839 (2020) 135–142,.

[36]

K. Shinagawa, K. Nuida, A single shuffle is enough for secure card-based computation of any Boolean circuit, Discrete Appl. Math. 289 (2021) 248–261,.

[37]

A. Stiglic, Computations with a deck of cards, Theor. Comput. Sci. 259 (1–2) (2001) 671–678,.

[38]

K. Takashima, Y. Abe, T. Sasaki, D. Miyahara, K. Shinagawa, T. Mizuki, H. Sone, Card-based protocols for secure ranking computations, Theor. Comput. Sci. 845 (2020) 122–135,.

[39]

I. Ueda, D. Miyahara, A. Nishimura, Y. Hayashi, T. Mizuki, H. Sone, Secure implementations of a random bisection cut, Int. J. Inf. Secur. 19 (2020) 445–452,.

Digital Library

[40]

T. Yato, T. Seta, Complexity and completeness of finding another solution and its application to puzzles, IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E86-A (5) (2003) 1052–1060. https://search.ieice.org/bin/summary.php?id=e86-a_5_1052.

Cited By

Tamura YSuzuki AMizuki T(2024)Card-Based Zero-Knowledge Proof Protocols for the 15-Puzzle and the Token Swapping ProblemProceedings of the 11th ACM Asia Public-Key Cryptography Workshop10.1145/3659467.3659905(11-22)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1145/3659467.3659905
Ruangwises S(2024)Verifying the first nonzero term: physical ZKPs for ABC End View, Goishi Hiroi, and ToichikaJournal of Combinatorial Optimization10.1007/s10878-024-01170-647:4Online publication date: 5-May-2024
https://dl.acm.org/doi/10.1007/s10878-024-01170-6
Robert LMiyahara DLafourcade PMizuki T(2023)Physical ZKP protocols for Nurimisaki and KurodokoTheoretical Computer Science10.1016/j.tcs.2023.114071972:COnline publication date: 13-Sep-2023
https://dl.acm.org/doi/10.1016/j.tcs.2023.114071
Show More Cited By

Index Terms

How to construct physical zero-knowledge proofs for puzzles with a “single loop” condition

Index terms have been assigned to the content through auto-classification.

Recommendations

Physical Zero-Knowledge Proof for Suguru Puzzle
Stabilization, Safety, and Security of Distributed Systems
Abstract
Suguru is a paper and pencil puzzle invented by Naoki Inaba. The goal of the game is to fulfil a grid with numbers between 1 and 5 and to respect three simple constraints. In this paper we design a physical Zero-Knowledge Proof (ZKP) protocol for ...
Zero-Knowledge Proofs from Secure Multiparty Computation

A zero-knowledge proof allows a prover to convince a verifier of an assertion without revealing any further information beyond the fact that the assertion is true. Secure multiparty computation allows $n$ mutually suspicious players to jointly compute a ...
Cryptographic and Physical Zero-Knowledge Proof Systems for Solutions of Sudoku Puzzles

We consider cryptographic and physical zero-knowledge proof schemes for Sudoku, a popular combinatorial puzzle. We discuss methods that allow one party, the prover, to convince another party, the verifier, that the prover has solved a Sudoku puzzle, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Theoretical Computer Science

Theoretical Computer Science Volume 888, Issue C

Oct 2021

133 pages

ISSN:0304-3975

Issue’s Table of Contents

The Authors.

Publisher

Elsevier Science Publishers Ltd.

United Kingdom

Publication History

Published: 04 October 2021

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Tamura YSuzuki AMizuki T(2024)Card-Based Zero-Knowledge Proof Protocols for the 15-Puzzle and the Token Swapping ProblemProceedings of the 11th ACM Asia Public-Key Cryptography Workshop10.1145/3659467.3659905(11-22)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1145/3659467.3659905
Ruangwises S(2024)Verifying the first nonzero term: physical ZKPs for ABC End View, Goishi Hiroi, and ToichikaJournal of Combinatorial Optimization10.1007/s10878-024-01170-647:4Online publication date: 5-May-2024
https://dl.acm.org/doi/10.1007/s10878-024-01170-6
Robert LMiyahara DLafourcade PMizuki T(2023)Physical ZKP protocols for Nurimisaki and KurodokoTheoretical Computer Science10.1016/j.tcs.2023.114071972:COnline publication date: 13-Sep-2023
https://dl.acm.org/doi/10.1016/j.tcs.2023.114071
Ruangwises S(2023)An improved physical ZKP for nonogram and nonogram colorJournal of Combinatorial Optimization10.1007/s10878-023-01050-545:5Online publication date: 15-Jun-2023
https://dl.acm.org/doi/10.1007/s10878-023-01050-5
Ruangwises S(2023)Physical Zero-Knowledge Proofs for Five CellsProgress in Cryptology – LATINCRYPT 202310.1007/978-3-031-44469-2_16(315-330)Online publication date: 3-Oct-2023
https://dl.acm.org/doi/10.1007/978-3-031-44469-2_16
Ruangwises S(2023)Physically Verifying the First Nonzero Term in a Sequence: Physical ZKPs for ABC End View and Goishi HiroiFrontiers of Algorithmics10.1007/978-3-031-39344-0_13(171-183)Online publication date: 14-Aug-2023
https://dl.acm.org/doi/10.1007/978-3-031-39344-0_13
Ruangwises S(2023)Physical Zero-Knowledge Proof for Ball Sort PuzzleUnity of Logic and Computation10.1007/978-3-031-36978-0_20(246-257)Online publication date: 24-Jul-2023
https://dl.acm.org/doi/10.1007/978-3-031-36978-0_20
Kuzuma TIsuzugawa RToyoda KMiyahara DMizuki TCruz JYanai N(2022)Card-based Single-shuffle Protocols for Secure Multiple-input AND and XOR ComputationsProceedings of the 9th ACM on ASIA Public-Key Cryptography Workshop10.1145/3494105.3526236(51-58)Online publication date: 30-May-2022
https://dl.acm.org/doi/10.1145/3494105.3526236
Robert LMiyahara DLafourcade PLibralesso LMizuki T(2022)Physical zero-knowledge proof and NP-completeness proof of Suguru puzzleInformation and Computation10.1016/j.ic.2021.104858285:PBOnline publication date: 1-May-2022
https://dl.acm.org/doi/10.1016/j.ic.2021.104858
Miyamoto KShinagawa K(2022)Graph Automorphism Shuffles from Pile-Scramble ShufflesNew Generation Computing10.1007/s00354-022-00164-440:1(199-223)Online publication date: 2-Apr-2022
https://dl.acm.org/doi/10.1007/s00354-022-00164-4
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents