Article

Physical Zero-Knowledge Proofs for Five Cells

Author:

Suthee RuangwisesAuthors Info & Claims

Progress in Cryptology – LATINCRYPT 2023: 8th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2023, Quito, Ecuador, October 3–6, 2023, Proceedings

Pages 315 - 330

https://doi.org/10.1007/978-3-031-44469-2_16

Published: 03 October 2023 Publication History

Abstract

Five Cells is a logic puzzle consisting of a rectangular grid, with some cells containing a number. The player has to partition the grid into pentominoes such that the number in each cell must be equal to the number of edges of that cell that are borders of pentominoes. In this paper, we propose two physical zero-knowledge proof protocols for Five Cells using a deck of playing cards, which allow a prover to physically show that he/she knows a solution of the puzzle without revealing it. In the optimization of our first protocol, we also develop a technique to reduce the number of required cards from quadratic to linear in the number of cells, which can be used in other zero-knowledge proof protocols related to graph coloring as well.

References

[1]

Bultel, X., Dreier, J., Dumas, J.G., Lafourcade, P.: Physical zero-knowledge proofs for Akari, Takuzu, Kakuro and KenKen. In: Proceedings of the 8th International Conference on Fun with Algorithms (FUN), pp. 8:1–8:20 (2016)

[2]

Bultel, X., et al.: Physical zero-knowledge proof for Makaro. In: Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pp. 111–125 (2018)

[3]

Chiba N, Nishizeki T, and Saito N A linear 5-coloring algorithm of planar graphs J. Algorithms 1981 2 4 317-327

[4]

Chien, Y.-F., Hon, W.-K.: Cryptographic and physical zero-knowledge proof: from Sudoku to Nonogram. In: Proceedings of the 5th International Conference on Fun with Algorithms (FUN), pp. 102–112 (2010)

[5]

Dumas J-G, Lafourcade P, Miyahara D, Mizuki T, Sasaki T, and Sone H Du D-Z, Duan Z, and Tian C Interactive physical zero-knowledge proof for Norinori Computing and Combinatorics 2019 Cham Springer 166-177

Digital Library

[6]

Fukusawa, T., Manabe, Y.: Card-based zero-knowledge proof for the nearest neighbor property: zero-knowledge proof of ABC end view. In: Proceedings of the 12th International Conference on Security, Privacy and Applied Cryptographic Engineering (SPACE), pp. 147–161 (2022)

[7]

Goldwasser S, Micali S, and Rackoff C The knowledge complexity of interactive proof systems SIAM J. Comput. 1989 18 1 186-208

Digital Library

[8]

Gradwohl R, Naor M, Pinkas B, and Rothblum GN Cryptographic and physical zero-knowledge proof systems for solutions of sudoku puzzles Theory Comput. Syst. 2009 44 2 245-268

Digital Library

[9]

Iwamoto, C., Ide, T.: Five cells and tilepaint are NP-complete. IEICE Trans. Inf. Syst. 105-D(3), 508–516 (2022)

[10]

Koch, A., Walzer, S.: Foundations for actively secure card-based cryptography. In: Proceedings of the 10th International Conference on Fun with Algorithms (FUN), pp. 17:1–17:23 (2020)

[11]

Lafourcade P, Miyahara D, Mizuki T, Robert L, Sasaki T, and Sone H How to construct physical zero-knowledge proofs for puzzles with a “single loop” condition Theoret. Comput. Sci. 2021 888 41-55

Digital Library

[12]

Miyahara, D., et al.: Card-based ZKP protocols for Takuzu and Juosan. In: Proceedings of the 10th International Conference on Fun with Algorithms (FUN), pp. 20:1–20:21 (2020)

[13]

Miyahara, D., Sasaki, T., Mizuki, T., Sone, H.: Card-based physical zero-knowledge proof for kakuro. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E102.A(9), 1072–1078 (2019)

[14]

Nikoli: Five Cells. www.nikoli.co.jp/en/puzzles/five_cells/

[15]

Robert, L., Miyahara, D., Lafourcade, P., Libralesso, L., Mizuki, T.: Physical zero-knowledge proof and NP-completeness proof of Suguru puzzle. Inf. Comput. 285(B), 104858 (2022)

[16]

Robert L, Miyahara D, Lafourcade P, and Mizuki T Card-based ZKP for connectivity: applications to nurikabe, Hitori, and Heyawake N. Gener. Comput. 2022 40 1 149-171

Digital Library

[17]

Robert L, Miyahara D, Lafourcade P, and Mizuki T Devismes S, Petit F, Altisen K, Di Luna GA, and Fernandez Anta A Card-based ZKP protocol for Nurimisaki Stabilization, Safety, and Security of Distributed Systems (SSS) 2022 Cham Springer 285-298

Digital Library

[18]

Robert L, Miyahara D, Lafourcade P, and Mizuki T Du DZ, Du D, Wu C, and Xu D Hide a liar: card-based ZKP protocol for Usowan Theory and Applications of Models of Computation (TAMC) 2022 Cham Springer 201-217

Digital Library

[19]

Robertson, N., Sanders, D.P., Seymour, P., Thomas, R.: Efficiently four-coloring planar graphs. In: Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC), pp. 571–575 (1996)

[20]

Ruangwises, S.: An improved physical ZKP for Nonogram and Nonogram color. J. Comb. Optim. 45(5), 122 (2023)

[21]

Ruangwises, S.: Physical zero-knowledge proof for ball sort puzzle. In: Proceedings of the 19th Conference on Computability in Europe (CiE), pp. 246–257 (2023)

[22]

Ruangwises, S.: Physically verifying the first nonzero term in a sequence: physical ZKPs for ABC end view and Goishi Hiroi. In: Proceedings of the 17th Conference on Frontiers of Algorithmic Wisdom (FAW), pp. 171–183 (2023)

[23]

Ruangwises S Two standard decks of playing cards are sufficient for a ZKP for Sudoku N. Gener. Comput. 2022 40 1 49-65

Digital Library

[24]

Ruangwises, S., Itoh, T.: How to physically verify a rectangle in a grid: a physical ZKP for Shikaku. In: Proceedings of the 11th International Conference on Fun with Algorithms (FUN), pp. 24:1–24:12 (2022)

[25]

Ruangwises S and Itoh T Physical zero-knowledge proof for Numberlink puzzle and vertex-disjoint paths problem N. Gener. Comput. 2021 39 1 3-17

Digital Library

[26]

Ruangwises S and Itoh T Physical zero-knowledge proof for ripple effect Theoret. Comput. Sci. 2021 895 115-123

Digital Library

[27]

Ruangwises, S., Itoh, T.: Physical ZKP for connected spanning subgraph: applications to bridges puzzle and other problems. In: Proceedings of the 19th International Conference on Unconventional Computation and Natural Computation (UCNC), pp. 149–163 (2021)

[28]

Ruangwises, S., Itoh, T.: Physical ZKP for Makaro using a standard deck of cards. In: Proceedings of the 17th Annual Conference on Theory and Applications of Models of Computation (TAMC), pp. 43–54 (2022)

[29]

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

[30]

Shinagawa, K., et al.: Card-based protocols using regular polygon cards. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E100.A(9), 1900–1909 (2017)

[31]

Thomassen C Every planar graph is 5-choosable J. Comb. Theory Ser. B 1994 62 1 180-181

Digital Library

[32]

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

Digital Library

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

Recommendations

Physical ZKP for Makaro Using a Standard Deck of Cards
Theory and Applications of Models of Computation
Abstract
Makaro is a logic puzzle with an objective to fill numbers into a rectangular grid to satisfy certain conditions. In 2018, Bultel et al. developed a physical zero-knowledge proof (ZKP) protocol for Makaro using a deck of cards, which allows a ...
An improved physical ZKP for nonogram and nonogram color
Abstract
Nonogram is a pencil puzzle consisting of a rectangular white grid where the player has to paint some cells black according to given constraints. Chien and Hon (Proceedings of the 5th international conference on fun with algorithms (FUN), 2010) ...
Physical zero-knowledge proof for Ripple Effect
Abstract
Ripple Effect is a logic puzzle where the player has to fill numbers into empty cells in a rectangular grid. The grid is divided into rooms, and each room must contain consecutive integers starting from 1 to its size. Also, if two ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Progress in Cryptology – LATINCRYPT 2023: 8th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2023, Quito, Ecuador, October 3–6, 2023, Proceedings

Oct 2023

400 pages

ISBN:978-3-031-44468-5

DOI:10.1007/978-3-031-44469-2

Editors:
Abdelrahaman Aly
https://ror.org/001kv2y39Technology Innovation Institute, Abu Dhabi, United Arab Emirates
,
Mehdi Tibouchi
NTT Social Informatics Laboratories, Tokyo, Japan

© The Author(s), under exclusive license to Springer Nature Switzerland AG 2023.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 03 October 2023

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
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

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 Table of Contents