Physical Zero-knowledge Proofs for Flow Free, Hamiltonian Cycles, and Many-to-many k-disjoint Covering Paths
This addresses the need for accessible, physical implementations of zero-knowledge proofs in cryptography and puzzle-solving domains, though it appears incremental as it builds on existing card-based proof techniques.
The paper tackles the problem of constructing physical zero-knowledge proofs using a standard deck of cards, specifically for Hamiltonian cycles and Flow Free puzzles, with the result being protocols that are perfectly sound and zero-knowledge, and can be extended to cover many-to-many k-disjoint path coverings.
In this paper we describe protocols which use a standard deck of cards to provide a perfectly sound zero-knowledge proof for Hamiltonian cycles and Flow Free puzzles. The latter can easily be extended to provide a protocol for a zero-knowledge proof of many-to-many k-disjoint path coverings.