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 Suguru. A ZKP protocol allows a prover (P) to prove that he knows a solution of a Suguru grid to a verifier (V) without leaking any information on the solution. For constructing such a physical ZKP protocol, we only rely on a small number of physical cards and an adapted encoding. For a grid of Suguru with n cells, we only use \(5n+5\) cards. Moreover, we prove the three classical security properties of a ZKP: completeness, extractability, and zero-knowledge.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Notes
- 1.
Moreover, if \(\mathcal {P}\) is NP-complete, then the ZKP should be run in a polynomial time [7]. Otherwise it might be easier to find a solution than proving that a solution is a correct solution, making the proof pointless.
- 2.
This implies the standard soundness property, which ensures that if there exists no solution of the puzzle, then the prover is not able to convince the verifier regardless of the prover’s behavior.
- 3.
- 4.
For example, in Fig. 1 the upper left region can be directly completed with a 1.
- 5.
We could have encoded each cell with a total of \(\ell \) cards where \(\ell \) is the number of cells in the region (thus, a region with two cells has its cell encoded with only two cards, a red and a black). Yet, this would lead to inconstancy in the encoding rule which is required in the neighbour verification.
- 6.
- 7.
- 8.
References
Bultel, X., Dreier, J., Dumas, J., Lafourcade, P.: Physical zero-knowledge proofs for Akari, Takuzu, Kakuro and KenKen. In: Demaine, E.D., Grandoni, F. (eds.) 8th International Conference on Fun with Algorithms, FUN 2016, June 8–10, 2016, La Maddalena, Italy. LIPIcs, vol. 49, pp. 8:1–8:20. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2016). https://doi.org/10.4230/LIPIcs.FUN.2016.8
Bultel, X., et al.: Physical zero-knowledge proof for Makaro. In: Izumi, T., Kuznetsov, P. (eds.) SSS 2018. LNCS, vol. 11201, pp. 111–125. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03232-6_8
Cramer, R., Damgård, I., Nielsen, J.B.: Multiparty computation from threshold homomorphic encryption. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 280–300. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44987-6_18
Damgård, I., Faust, S., Hazay, C.: Secure two-party computation with low communication. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 54–74. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-28914-9_4
Dumas, J.-G., Lafourcade, P., Miyahara, D., Mizuki, T., Sasaki, T., Sone, H.: Interactive physical zero-knowledge proof for Norinori. In: Du, D.-Z., Duan, Z., Tian, C. (eds.) COCOON 2019. LNCS, vol. 11653, pp. 166–177. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26176-4_14
Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity and a methodology of cryptographic protocol design. In: 27th Annual Symposium on Foundations of Computer Science (SFCS 1986), pp. 174–187, October 1986. https://doi.org/10.1109/SFCS.1986.47
Goldreich, O., Micali, S., Wigderson, A.: How to prove all NP statements in zero-knowledge and a methodology of cryptographic protocol design (extended abstract). In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 171–185. Springer, Heidelberg (1987). https://doi.org/10.1007/3-540-47721-7_11
Goldwasser, S., Micali, S., Rackoff, C.: Knowledge complexity of interactive proof-systems. In: Conference Proceedings of the Annual ACM Symposium on Theory of Computing, pp. 291–304 (1985). https://doi.org/10.1145/3335741.3335750
Gradwohl, R., Naor, M., Pinkas, B., Rothblum, G.N.: Cryptographic and physical zero-knowledge proof systems for solutions of sudoku puzzles. In: Crescenzi, P., Prencipe, G., Pucci, G. (eds.) FUN 2007. LNCS, vol. 4475, pp. 166–182. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-72914-3_16
Ishikawa, R., Chida, E., Mizuki, T.: Efficient card-based protocols for generating a hidden random permutation without fixed points. In: Calude, C.S., Dinneen, M.J. (eds.) UCNC 2015. LNCS, vol. 9252, pp. 215–226. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-21819-9_16
Iwamoto, C., Haruishi, M., Ibusuki, T.: Herugolf and Makaro are NP-complete. In: Ito, H., Leonardi, S., Pagli, L., Prencipe, G. (eds.) Fun with Algorithms 2018. LIPIcs, vol. 100, pp. 24:1–24:11. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2018)
Lafourcade, P., Miyahara, D., Mizuki, T., Sasaki, T., Sone, H.: A physical ZKP for Slitherlink: how to perform physical topology-preserving computation. In: Heng, S.-H., Lopez, J. (eds.) ISPEC 2019. LNCS, vol. 11879, pp. 135–151. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-34339-2_8
Miyahara, D., et al.: Card-based ZKP protocols for Takuzu and Juosan. In: Farach-Colton, M., Prencipe, G., Uehara, R. (eds.) Fun with Algorithms 2020. LIPIcs (2020)
Miyahara, D., Sasaki, T., Mizuki, T., Sone, H.: Card-based physical zero-knowledge proof for Kakuro. IEICE Trans. Fund. Electron. Commun. Comput. Sci. E102.A(9), 1072–1078 (2019). https://doi.org/10.1587/transfun.E102.A.1072
Quisquater, J.-J., et al.: How to explain zero-knowledge protocols to your children. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 628–631. Springer, New York (1990). https://doi.org/10.1007/0-387-34805-0_60
Romero-Tris, C., Castellà-Roca, J., Viejo, A.: Multi-party private web search with untrusted partners. In: Rajarajan, M., Piper, F., Wang, H., Kesidis, G. (eds.) SecureComm 2011. LNICST, vol. 96, pp. 261–280. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-31909-9_15
Ruangwises, S., Itoh, T.: Physical zero-knowledge proof for Numberlink. In: Farach-Colton, M., Prencipe, G., Uehara, R. (eds.) Fun with Algorithms 2020. LIPIcs (2020)
Sasaki, T., Miyahara, D., Mizuki, T., Sone, H.: Efficient card-based zero-knowledge proof for Sudoku. Theor. Comput. Sci. (2020). https://doi.org/10.1016/j.tcs.2020.05.036, http://www.sciencedirect.com/science/article/pii/S0304397520303200
Shamir, A.: IP = PSPACE. J. ACM 39(4), 869–877 (1992). https://doi.org/10.1145/146585.146609
Acknowledgements
We thank the anonymous referees, whose comments have helped us to improve the presentation of the paper. This work was supported in part by JSPS KAKENHI Grant Number JP19J21153.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Robert, L., Miyahara, D., Lafourcade, P., Mizuki, T. (2020). Physical Zero-Knowledge Proof for Suguru Puzzle. In: Devismes, S., Mittal, N. (eds) Stabilization, Safety, and Security of Distributed Systems. SSS 2020. Lecture Notes in Computer Science(), vol 12514. Springer, Cham. https://doi.org/10.1007/978-3-030-64348-5_19
Download citation
DOI: https://doi.org/10.1007/978-3-030-64348-5_19
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-64347-8
Online ISBN: 978-3-030-64348-5
eBook Packages: Computer ScienceComputer Science (R0)