Document Open Access Logo

How to Physically Verify a Rectangle in a Grid: A Physical ZKP for Shikaku

Authors Suthee Ruangwises , Toshiya Itoh

PDF
Thumbnail PDF

File

LIPIcs.FUN.2022.24.pdf
  • Filesize: 0.63 MB
  • 12 pages

Document Identifiers

Author Details

Suthee Ruangwises
  • Department of Mathematical and Computing Science, Tokyo Institute of Technology, Japan
Toshiya Itoh
  • Department of Mathematical and Computing Science, Tokyo Institute of Technology, Japan

Cite AsGet BibTex

Suthee Ruangwises and Toshiya Itoh. How to Physically Verify a Rectangle in a Grid: A Physical ZKP for Shikaku. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 24:1-24:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.FUN.2022.24

Abstract

Shikaku is a pencil puzzle consisting of a rectangular grid, with some cells containing a number. The player has to partition the grid into rectangles such that each rectangle contains exactly one number equal to the area of that rectangle. In this paper, we propose two physical zero-knowledge proof protocols for Shikaku 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. Most importantly, in our second protocol we develop a general technique to physically verify a rectangle-shaped area with a certain size in a rectangular grid, which can be used to verify other problems with similar constraints.

Subject Classification

ACM Subject Classification
  • Security and privacy → Information-theoretic techniques
  • Theory of computation → Cryptographic protocols
Keywords
  • Zero-knowledge proof
  • Card-based cryptography
  • Shikaku
  • Puzzles
  • Games

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. X. Bultel, J. Dreier, J.-G. Dumas, and P. Lafourcade. Physical zero-knowledge proofs for Akari, Takuzu, Kakuro and KenKen. In Proceedings of the 8th International Conference on Fun with Algorithms (FUN), pages 8:1-8:20, 2016. URL: https://doi.org/10.4230/LIPIcs.FUN.2016.8.
  2. X. Bultel, J. Dreier, J.-G. Dumas, P. Lafourcade, D. Miyahara, T. Mizuki, A. Nagao, T. Sasaki, K. Shinagawa, and H. Sone. Physical zero-knowledge proof for Makaro. In Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pages 111-125, 2018. URL: https://doi.org/10.1007/978-3-030-03232-6_8.
  3. Y.-F. Chien and W.-K. Hon. Cryptographic and physical zero-knowledge proof: From Sudoku to Nonogram. In Proceedings of the 5th International Conference on Fun with Algorithms (FUN), pages 102-112, 2010. URL: https://doi.org/10.1007/978-3-642-13122-6_12.
  4. J.-G. Dumas, P. Lafourcade, D. Miyahara, T. Mizuki, T. Sasaki, and H. Sone. Interactive physical zero-knowledge proof for Norinori. In Proceedings of the 25th International Computing and Combinatorics Conference (COCOON), pages 166-177, 2019. URL: https://doi.org/10.1007/978-3-030-26176-4_14.
  5. O. Goldreich, S. Micali, and A. Wigderson. Proofs that yield nothing but their validity and a methodology of cryptographic protocol design. Journal of the ACM, 38(3):691-729, 1991. URL: https://doi.org/10.1145/116825.116852.
  6. S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof systems. SIAM Journal on Computing, 18(1):186-208, 1989. URL: https://doi.org/10.1137/0218012.
  7. Google Play: Shikaku. URL: https://play.google.com/store/search?q=Shikaku&c=apps.
  8. R. Gradwohl, M. Naor, B. Pinkas, and G.N. Rothblum. Cryptographic and physical zero-knowledge proof systems for solutions of sudoku puzzles. Theory of Computing Systems, 44(2):245-268, 2009. URL: https://doi.org/10.1007/s00224-008-9119-9.
  9. R. Isuzugawa, D. Miyahara, and T. Mizuki. Zero-knowledge proof protocol for cryptarithmetic using dihedral cards. In Proceedings of the 19th International Conference on Unconventional Computation and Natural Computation (UCNC), pages 51-67, 2021. URL: https://doi.org/10.1007/978-3-030-87993-8_4.
  10. A. Koch and S. Walzer. Foundations for actively secure card-based cryptography. In Proceedings of the 10th International Conference on Fun with Algorithms (FUN), pages 17:1-17:23, 2020. URL: https://doi.org/10.4230/LIPIcs.FUN.2021.17.
  11. P. Lafourcade, D. Miyahara, T. Mizuki, L. Robert, T. Sasaki, and H. Sone. How to construct physical zero-knowledge proofs for puzzles with a "single loop" condition. Theoretical Computer Science, 888:41-55, 2021. URL: https://doi.org/10.1016/j.tcs.2021.07.019.
  12. D. Miyahara, L. Robert, P. Lafourcade, S. Takeshige, T. Mizuki, K. Shinagawa, A. Nagao, and H. Sone. Card-based zkp protocols for takuzu and juosan. In Proceedings of the 10th International Conference on Fun with Algorithms (FUN), pages 20:1-20:21, 2020. URL: https://doi.org/10.4230/LIPIcs.FUN.2021.20.
  13. D. Miyahara, T. Sasaki, T. Mizuki, and H. Sone. Card-based physical zero-knowledge proof for Kakuro. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E102.A(9):1072-1078, 2019. URL: https://doi.org/10.1587/transfun.E102.A.1072.
  14. L. Robert, D. Miyahara, P. Lafourcade, and T. Mizuki. Physical zero-knowledge proof for suguru puzzle. In Proceedings of the 22nd International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pages 235-247, 2020. URL: https://doi.org/10.1007/978-3-030-64348-5_19.
  15. L. Robert, D. Miyahara, P. Lafourcade, and T. Mizuki. Interactive physical zkp for connectivity: Applications to nurikabe and hitori. In Proceedings of the 17th Conference on Computability in Europe (CiE), pages 373-384, 2021. URL: https://doi.org/10.1007/978-3-030-80049-9_37.
  16. S. Ruangwises. An improved physical zkp for nonogram. In Proceedings of the 15th Annual International Conference on Combinatorial Optimization and Applications (COCOA), pages 262-272, 2021. URL: https://doi.org/10.1007/978-3-030-92681-6_22.
  17. S. Ruangwises. Two standard decks of playing cards are sufficient for a zkp for sudoku. In Proceedings of the 27th International Computing and Combinatorics Conference (COCOON), pages 631-642, 2021. URL: https://doi.org/10.1007/978-3-030-89543-3_52.
  18. S. Ruangwises and T. Itoh. Physical zero-knowledge proof for numberlink puzzle and k vertex-disjoint paths problem. New Generation Computin, 39(1):3-17, 2021. URL: https://doi.org/10.1007/s00354-020-00114-y.
  19. S. Ruangwises and T. Itoh. Physical zero-knowledge proof for ripple effect. Theoretical Computer Science, 895:115-123, 2021. URL: https://doi.org/10.1016/j.tcs.2021.09.034.
  20. S. Ruangwises and T. Itoh. 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), pages 149-163, 2021. URL: https://doi.org/10.1007/978-3-030-87993-8_10.
  21. T. Sasaki, D. Miyahara, T. Mizuki, and H. Sone. Efficient card-based zero-knowledge proof for sudoku. Theoretical Computer Science, 839:135-142, 2020. URL: https://doi.org/10.1016/j.tcs.2020.05.036.
  22. K. Shinagawa, T. Mizuki, J.C.N. Schuldt, K. Nuida, N. Kanayama, T. Nishide, G. Hanaoka, and E. Okamoto. Card-based protocols using regular polygon cards. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E100.A(9):1900-1909, 2017. URL: https://doi.org/10.1587/transfun.E100.A.1900.
  23. Y. Takenaga, S. Aoyagi, S. Iwata, and T. Kasai. Shikaku and ripple effect are np-complete. Congressus Numerantium, 216:119-127, 2013. Google Scholar
  24. I. Ueda, D. Miyahara, A. Nishimura, Y. Hayashi, T. Mizuki, and H. Sone. Secure implementations of a random bisection cut. International Journal of Information Security, 19(4):445-452, 2020. URL: https://doi.org/10.1007/s10207-019-00463-w.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact