TY - JOUR
T1 - Card-Based Protocol Counting Connected Components of Graphs
AU - Nuida, Koji
N1 - Publisher Copyright:
© The Author(s), under exclusive licence to The Japanese Society for Artificial Intelligence and Springer Nature Japan KK, part of Springer Nature 2025.
PY - 2025/11
Y1 - 2025/11
N2 - 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.
AB - 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.
KW - Card-based protocols
KW - Connected components
KW - Cryptography
KW - Graphs
UR - https://www.scopus.com/pages/publications/105017632219
UR - https://www.scopus.com/pages/publications/105017632219#tab=citedBy
U2 - 10.1007/s00354-025-00304-6
DO - 10.1007/s00354-025-00304-6
M3 - Article
AN - SCOPUS:105017632219
SN - 0288-3635
VL - 43
JO - New Generation Computing
JF - New Generation Computing
IS - 4
M1 - 18
ER -