Document Open Access Logo

Physical Zero-Knowledge Proofs for Akari, Takuzu, Kakuro and KenKen

Authors Xavier Bultel, Jannik Dreier, Jean-Guillaume Dumas, Pascal Lafourcade

PDF
Thumbnail PDF

File

LIPIcs.FUN.2016.8.pdf
  • Filesize: 0.58 MB
  • 20 pages

Document Identifiers

Author Details

Xavier Bultel
Jannik Dreier
Jean-Guillaume Dumas
Pascal Lafourcade

Cite AsGet BibTex

Xavier Bultel, Jannik Dreier, Jean-Guillaume Dumas, and Pascal Lafourcade. Physical Zero-Knowledge Proofs for Akari, Takuzu, Kakuro and KenKen. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.FUN.2016.8

Abstract

Akari, Takuzu, Kakuro and KenKen are logic games similar to Sudoku. In Akari, a labyrinth on a grid has to be lit by placing lanterns, respecting various constraints. In Takuzu a grid has to be filled with 0's and 1's, while respecting certain constraints. In Kakuro a grid has to be filled with numbers such that the sums per row and column match given values; similarly in KenKen a grid has to be filled with numbers such that in given areas the product, sum, difference or quotient equals a given value. We give physical algorithms to realize zero-knowledge proofs for these games which allow a player to show that he knows a solution without revealing it. These interactive proofs can be realized with simple office material as they only rely on cards and envelopes. Moreover, we formalize our algorithms and prove their security.
Keywords
  • Physical Cryptography
  • ZKP
  • Games
  • Akari
  • Kakuro
  • KenKen
  • Takuzu

Metrics

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

References

  1. Michael Ben-Or, Oded Goldreich, Shafi Goldwasser, Johan Håstad, Joe Kilian, Silvio Micali, and Phillipe Rogaway. Everything provable is provable in zero-knowledge. In CRYPTO'88, pages 37-56. Springer, 1990. Google Scholar
  2. Marzio De Biasi. Binary puzzle is NP-complete. 2012. URL: http://www.nearly42.org/vdisk/cstheory/binaryp.pdf.
  3. Manuel Blum, Paul Feldman, and Silvio Micali. Non-interactive zero-knowledge and its applications. In STOC'88, pages 103-112. ACM, 1988. Google Scholar
  4. Yu-Feng Chien and Wing-Kai Hon. Cryptographic and physical zero-knowledge proof: From sudoku to nonogram. In Fun with Algorithms, 5th International Conference, FUN'10, volume 6099 of LNCS, pages 102-112, 2010. Google Scholar
  5. Erik D. Demaine. Playing games with algorithms: Algorithmic combinatorial game theory. In Mathematical Foundations of Computer Science 2001, volume 2136 of LNCS, pages 18-32, 2001. Google Scholar
  6. Jannik Dreier, Hugo Jonker, and Pascal Lafourcade. Secure auctions without cryptography. In Fun with Algorithms, 7th International Conference, FUN'14, pages 158-170, 2014. Google Scholar
  7. Oded Goldreich and Ariel Kahan. How to construct constant-round zero-knowledge proof systems for NP. Journal of Cryptology, 9(3):167-189, 1991. Google Scholar
  8. Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof-systems. In STOC'85, pages 291-304. ACM, 1985. Google Scholar
  9. Ronen Gradwohl, Moni Naor, Benny Pinkas, and Guy N. Rothblum. Cryptographic and physical zero-knowledge proof systems for solutions of sudoku puzzles. In Fun with Algorithms, 4th International Conference, FUN'07, pages 166-182. Springer-Verlag, 2007. Google Scholar
  10. Kazuya Haraguchi and Hirotaka Ono. BLOCKSUM is NP-complete. IEICE Transactions, 96-D(3):481-488, 2013. Google Scholar
  11. Kazuya Haraguchi and Hirotaka Ono. How simple algorithms can solve latin square completion-type puzzles approximately. JIP, 23(3):276-283, 2015. Google Scholar
  12. Graham Kendall, Andrew J. Parkes, and Kristian Spoerer. A survey of NP-complete puzzles. ICGA Journal, 31(1):13-34, 2008. Google Scholar
  13. Jonas Kölker. I/O-Efficient Multiparty Computation, Formulaic Secret Sharing and NP-Complete Puzzles. PhD thesis, Aarhus University, 2012. Google Scholar
  14. Brandon McPhail. Light up is NP-complete. feb 2005. URL: http://www.mountainvistasoft.com/docs/lightup-is-np-complete.pdf.
  15. Alfred J. Menezes, Scott A. Vanstone, and Paul C. Van Oorschot. Handbook of Applied Cryptography. CRC Press, Inc., Boca Raton, FL, USA, 1st edition, 1996. Google Scholar
  16. Takaaki Mizuki and Hiroki Shizuya. Practical card-based cryptography. In Fun with Algorithms, 7th International Conference, FUN'14, pages 313-324, 2014. Google Scholar
  17. Moni Naor, Yael Naor, and Omer Reingold. Applied kid cryptography or how to convince your children you are not cheating. In Eurocrypt’94, pages 1-12, 1999. Google Scholar
  18. Jean-Jacques Quisquater, Myriam Quisquater, Muriel Quisquater, Michaël Quisquater, Louis Guillou, Marie Annick Guillou, Gaïd Guillou, Anna Guillou, Gwenolé Guillou, Soazig Guillou, and Thomas A. Berson. How to explain zero-knowledge protocols to your children. In CRYPTO'89, pages 628-631. Springer-Verlag, 1990. Google Scholar
  19. J. Barkley Rosser and Lowell Schoenfeld. Approximate formulas for some functions of prime numbers. Illinois Journal of Mathematics, 6:64-94, 1962. Google Scholar
  20. Dennis Shasha. Upstart puzzles: Proving without teaching/teaching without proving. Commun. ACM, 57(11):120-120, 2014. Google Scholar
  21. Will Shortz. Easy Kakuro: 100 Addictive Logic Puzzles. St. Martin’s Griffin, 2006. Google Scholar
  22. Seta Takahiro. The complexities of puzzles, cross sum and their another solution problems(asp). Master’s thesis, University of Tokyo, 2001. Google Scholar
  23. Putranto Hadi Utomo and Ruud Pellikaan. Binary puzzles as an erasure decoding problem. In Proceedings of the 36th WIC Symposium on Information Theory in the Benelux, pages 129-134, 2015. Google Scholar
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