How to construct physical zero-knowledge proofs for puzzles with a ``single loop condition

DOI10.1016/j.tcs.2021.07.019OpenAlexW3184569853WikidataQ113863188 ScholiaQ113863188MaRDI QIDQ820565

Pascal Lafourcade, Léo Robert, Tatsuya Sasaki, Hideaki Sone, Daiki Miyahara, Takaaki Mizuki

Publication date: 27 September 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2021.07.019

zbMATH Keywords

cryptographyMasyuNikoliphysical zero-knowledge proofSlitherlink

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items

An improved physical ZKP for Nonogram ⋮ Zero-knowledge proof protocol for cryptarithmetic using dihedral cards ⋮ Physical zero-knowledge proof and NP-completeness proof of Suguru puzzle ⋮ 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 ⋮ Card-based zero-knowledge proof protocols for graph problems and their computational model

Cites Work

• Unnamed Item
• Unnamed Item
• Secure computation without computers
• Secure multiparty computations without computers
• Private computation using a PEZ dispenser.
• The minimum number of cards in practical card-based protocols
• How to construct constant-round zero-knowledge proof systems for NP
• Interactive physical ZKP for connectivity: applications to Nurikabe and Hitori
• A physical ZKP for Slitherlink: how to perform physical topology-preserving computation
• Efficient private PEZ protocols for symmetric functions
• Card-based cryptography meets formal verification
• 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
• Basing cryptographic protocols on tamper-evident seals
• 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
• Card-Based Cryptographic Protocols Using a Minimal Number of Cards
• Efficient Card-Based Protocols for Generating a Hidden Random Permutation Without Fixed Points
• The knowledge complexity of interactive proof-systems
• The Five-Card Trick Can Be Done with Four Cards
• More Efficient Match-Making and Satisfiability The Five Card Trick
• Six-Card Secure AND and Four-Card Secure XOR
• Physical zero-knowledge proof for ripple effect
• Computations with a deck of cards
• Card-based protocols for securely computing the conjunction of multiple variables
• Physical zero-knowledge proof for Makaro