Physical ZKP for Makaro Using a Standard Deck of Cards
Preprint
Abstract
Makaro is a logic puzzle with an objective to fill numbers into a rectangular grid to satisfy certain conditions. In 2018, Bultel et al. developed a physical zero-knowledge proof (ZKP) protocol for Makaro using a deck of cards, which allows a prover to physically convince a verifier that he/she knows a solution of the puzzle without revealing it. However, their protocol requires several identical copies of some cards, making it impractical as a deck of playing cards found in everyday life typically consists of all different cards. In this paper, we propose a new ZKP protocol for Makaro that can be implemented using a standard deck (a deck consisting of all different cards). Our protocol also uses asymptotically less cards than the protocol of Bultel et al. Most importantly, we develop a general method to encode a number with a sequence of all different cards. This allows us to securely compute several numerical functions using a standard deck, such as verifying that two given numbers are different and verifying that a number is the largest one among the given numbers.Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Physical zero-knowledge proof and NP-completeness proof of Suguru puzzleInformation and Computation, 2022
- Two Standard Decks of Playing Cards are Sufficient for a ZKP for SudokuNew Generation Computing, 2022
- Physical zero-knowledge proof for Ripple EffectTheoretical Computer Science, 2021
- How to construct physical zero-knowledge proofs for puzzles with a “single loop” conditionTheoretical Computer Science, 2021
- Card-Based Cryptography Meets Formal VerificationNew Generation Computing, 2021
- Efficient card-based zero-knowledge proof for SudokuTheoretical Computer Science, 2020
- Physical Zero-Knowledge Proof for Numberlink Puzzle and k Vertex-Disjoint Paths ProblemNew Generation Computing, 2020
- Practical card-based implementations of Yao's millionaire protocolTheoretical Computer Science, 2020
- Secure implementations of a random bisection cutInternational Journal of Information Security, 2019
- Cryptographic and Physical Zero-Knowledge Proof Systems for Solutions of Sudoku PuzzlesTheory of Computing Systems, 2008