Card-Based Protocol Counting Connected Components of Graphs

Koji Nuida

Paper 2025/924

Card-Based Protocol Counting Connected Components of Graphs

Koji Nuida

, Kyushu University, National Institute of Advanced Industrial Science and Technology

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 subsets on any graph, and propose a card-based protocol for the problem.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: card-based cryptography graphs connected components
Contact author(s): nuida @ imi kyushu-u ac jp
History: 2025-05-23: approved; 2025-05-22: received; See all versions
Short URL: https://ia.cr/2025/924
License: CC BY

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}
}