Physical zero-knowledge proof and NP-completeness proof of Suguru puzzle
From MaRDI portal
Publication:2672240
DOI10.1016/j.ic.2021.104858zbMath1487.68123OpenAlexW4200101193WikidataQ113872836 ScholiaQ113872836MaRDI QIDQ2672240
Luc Libralesso, Takaaki Mizuki, Léo Robert, Daiki Miyahara, Pascal Lafourcade
Publication date: 8 June 2022
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2021.104858
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (10)
Physical ZKP protocols for Nurimisaki and Kurodoko ⋮ Card-minimal protocols for three-input functions with standard playing cards ⋮ 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 ⋮ Card-based zero-knowledge proof for the nearest neighbor property: zero-knowledge proof of ABC end view ⋮ Physical zero-knowledge proof for ball sort puzzle ⋮ Card-based ZKP protocol for Nurimisaki ⋮ Secure computations through checking suits of playing cards ⋮ An improved physical ZKP for nonogram and nonogram color
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- How to construct physical zero-knowledge proofs for puzzles with a ``single loop condition
- Private computation using a PEZ dispenser.
- \textsc{Hanano} puzzle is \textsf{NP}-hard
- Efficient private PEZ protocols for symmetric functions
- Efficient card-based zero-knowledge proof for Sudoku
- Card-based protocols for secure ranking computations
- A single shuffle is enough for secure card-based computation of any Boolean circuit
- Cryptographic and physical zero-knowledge proof systems for solutions of Sudoku puzzles
- Practical card-based implementations of Yao's millionaire protocol
- Interactive physical zero-knowledge proof for Norinori
- Secure Two-Party Computation with Low Communication
- Efficient Card-Based Protocols for Generating a Hidden Random Permutation Without Fixed Points
- Computational Complexity of NURIKABE
- Planar Formulae and Their Uses
- IP = PSPACE
- Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
- The knowledge complexity of interactive proof-systems
- Physical zero-knowledge proof for ripple effect
- Physical zero-knowledge proof for Makaro
This page was built for publication: Physical zero-knowledge proof and NP-completeness proof of Suguru puzzle
