2026-08-17T18:52:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5869 2024-03-06T10:37:05Z ddc:004 open_access

Physical Zero-Knowledge Proofs for Akari, Takuzu, Kakuro and KenKen Bultel, Xavier Dreier, Jannik Dumas, Jean-Guillaume Lafourcade, Pascal Physical Cryptography ZKP Games Akari Kakuro KenKen Takuzu 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Xavier Bultel and Jannik Dreier and Jean-Guillaume Dumas and Pascal Lafourcade 2016 Is Part Of LIPIcs, Volume 49, 8th International Conference on Fun with Algorithms (FUN 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2016.8 urn:nbn:de:0030-drops-58693 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2016.8 eng https://creativecommons.org/licenses/by/3.0/legalcode