Verifying the first nonzero term: physical ZKPs for ABC End View, Goishi Hiroi, and Toichika

Suthee Ruangwises ()
Additional contact information
Suthee Ruangwises: The University of Electro-Communications

Journal of Combinatorial Optimization, 2024, vol. 47, issue 4, No 16, 18 pages

Abstract: Abstract In this paper, we propose a physical protocol to verify the first nonzero term of a sequence using a deck of cards. The protocol lets a prover show the value of the first nonzero term of a given sequence to a verifier without revealing which term it is. Our protocol uses $$\varTheta (1)$$ Θ ( 1 ) shuffles, which is asymptotically lower than that of an existing protocol of Fukusawa and Manabe which uses $$\varTheta (n)$$ Θ ( n ) shuffles, where n is the length of the sequence. We also apply our protocol to construct zero-knowledge proof protocols for three well-known logic puzzles: ABC End View, Goishi Hiroi, and Toichika. These protocols enable a prover to physically show that he/she know solutions of the puzzles without revealing them.

Keywords: Zero-knowledge proof; Card-based cryptography; Sequence; ABC End View; Goishi Hiroi; Toichika; Puzzle (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-024-01170-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:47:y:2024:i:4:d:10.1007_s10878-024-01170-6

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-024-01170-6

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().