Paper 2025/924 Original: eprint.iacr.org/2025/924 ↗
Card-Based Protocol Counting Connected Components of Graphs
Abstract
Card-based cryptography is a research area for realizing cryptographic functionality, such as secure multiparty computation and zero-knowledge proofs, by using a deck of physical cards and/or other non-electrical tools. Motivated by zero-knowledge proofs for solutions in pencil puzzles, there is a direction of recent studies on card-based protocols to verify connectivity of a set of cells or edges on lattice-shaped boards. In this paper, we generalize the problem to counting connected components of a subset of the vertex set on any graph, and propose a card-based protocol for the problem.
Metadata
- Available format(s)
PDF- Category
- Cryptographic protocols
- Publication info
- Preprint.
- History
- 2025-10-06: last updated
- 2025-05-22: published
- Short URL
- https://ia.cr/2025/924
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2025/924,
author = {Koji Nuida},
title = {Card-Based Protocol Counting Connected Components of Graphs},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/924},
year = {2025},
url = {https://eprint.iacr.org/2025/924}
}