Card-based zero-knowledge proof protocols for graph problems and their computational model
From MaRDI portal
Publication:2697917
DOI10.1007/978-3-030-90402-9_8OpenAlexW3210890153MaRDI QIDQ2697917
Hiromichi Haneda, Takaaki Mizuki, Daiki Miyahara
Publication date: 13 April 2023
Full work available at URL: https://doi.org/10.1007/978-3-030-90402-9_8
graph isomorphism problemcard-based cryptographyphysical zero-knowledge proofgraph 3-coloring problem
Cryptography (94A60) Coloring of graphs and hypergraphs (05C15) Authentication, digital signatures and secret sharing (94A62) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items
Physical zero-knowledge proof protocol for Topswops ⋮ Secure computations through checking suits of playing cards
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- How to construct physical zero-knowledge proofs for puzzles with a ``single loop condition
- Secure multiparty computations without computers
- Some simplified NP-complete graph problems
- Interactive physical ZKP for connectivity: applications to Nurikabe and Hitori
- Physical ZKP for connected spanning subgraph: applications to bridges puzzle and other problems
- 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
- Two standard decks of playing cards are sufficient for a ZKP for Sudoku
- Efficient Card-Based Protocols for Generating a Hidden Random Permutation Without Fixed Points
- Multi-party Computation with Small Shuffle Complexity Using Regular Polygon 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
- Reducibility among Combinatorial Problems
- Six-Card Secure AND and Four-Card Secure XOR
- Graph isomorphism in quasipolynomial time [extended abstract]
- Physical zero-knowledge proof for ripple effect
- Physical zero-knowledge proof for Makaro
