Physical ZKP for connected spanning subgraph: applications to bridges puzzle and other problems

DOI10.1007/978-3-030-87993-8_10OpenAlexW3130037434MaRDI QIDQ2152094

Toshiya Itoh, Suthee Ruangwises

Publication date: 6 July 2022

Full work available at URL: https://arxiv.org/abs/2011.02313

zbMATH Keywords

puzzlegraphHamiltonian cyclebridgesmaximum leaf spanning treezero-knowledge proofcard-based cryptographyconnected spanning subgraph

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum algorithms and complexity in the theory of computing (68Q12) Other nonclassical models of computation (68Q09) Biologically inspired models of computation (DNA computing, membrane computing, etc.) (68Q07)

Related Items (12)

An improved physical ZKP for Nonogram ⋮ Zero-knowledge proof protocol for cryptarithmetic using dihedral cards ⋮ Physical ZKP protocols for Nurimisaki and Kurodoko ⋮ Physical zero-knowledge proof protocol for Topswops ⋮ Physical ZKP for Makaro using a standard deck of cards ⋮ Hide a liar: card-based ZKP protocol for Usowan ⋮ Physical zero-knowledge proof for ball sort puzzle ⋮ Single-shuffle card-based protocol with eight cards per gate ⋮ Card-based ZKP protocol for Nurimisaki ⋮ An improved physical ZKP for nonogram and nonogram color ⋮ Two standard decks of playing cards are sufficient for a ZKP for Sudoku ⋮ Card-based zero-knowledge proof protocols for graph problems and their computational model

Cites Work

• Unnamed Item
• Unnamed Item
• Hashiwokakero is NP-complete
• Secure grouping protocol using a deck of cards
• Interactive physical ZKP for connectivity: applications to Nurikabe and Hitori
• A physical ZKP for Slitherlink: how to perform physical topology-preserving computation
• Efficient card-based zero-knowledge proof for Sudoku
• Cryptographic and physical zero-knowledge proof systems for solutions of Sudoku puzzles
• Interactive physical zero-knowledge proof for Norinori
• Card-based Protocols Using Triangle Cards
• The Knowledge Complexity of Interactive Proof Systems
• Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
• Physical zero-knowledge proof for ripple effect
• Physical zero-knowledge proof for Makaro

This page was built for publication: Physical ZKP for connected spanning subgraph: applications to bridges puzzle and other problems