NP-completeness and physical zero-knowledge proofs for Zeiger

DOI10.1007/978-981-96-2845-2_20MaRDI QIDQ6996785zbMATH OpenFDO

Authors Suthee Ruangwises

Publication date 15 April 2025

Full work available at URL https://doi.org/10.1007/978-981-96-2845-2_20

zbMATH Keywords

card-based cryptographyNP-completenesspuzzleZeigerzero-knowledge proof

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• An improved physical ZKP for nonogram and nonogram color
• Card-based overwriting protocol for equality function and applications
• Efficient card-based protocols for generating a hidden random permutation without fixed points
• Efficient card-based zero-knowledge proof for Sudoku
• Hashiwokakero is NP-complete
• Herugolf and Makaro are NP-complete
• HIROIMONO Is NP-Complete
• How to construct physical zero-knowledge proofs for puzzles with a ``single loop condition
• How to Physically Verify a Rectangle in a Grid: A Physical ZKP for Shikaku
• Physical zero-knowledge proof for Makaro
• Physical zero-knowledge proof for ripple effect
• Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
• Securely computing the \(n\)-variable equality function with \(2n\) cards
• Shikaku and Ripple Effect are NP-complete
• The complexity of satisfiability problems
• The Knowledge Complexity of Interactive Proof Systems
• The Troubles of Interior Design–A Complexity Analysis of the Game Heyawake
• Verifying the first nonzero term: physical ZKPs for ABC end view, Goishi Hiroi, and Toichika

This page was built for publication: NP-completeness and physical zero-knowledge proofs for Zeiger

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6996785)