Paper 2017/863

The Minimum Number of Cards in Practical Card-based Protocols

Julia Kastner, Alexander Koch, Stefan Walzer, Daiki Miyahara, Yu-ichi Hayashi, Takaaki Mizuki, and Hideaki Sone

Abstract

The elegant “five-card trick” of den Boer (EUROCRYPT 1989) allows two players to securely compute a logical AND of two private bits, using five playing cards of symbols $\heartsuit$ and $\clubsuit$. Since then, card-based protocols have been successfully put to use in classroom environments, vividly illustrating secure multiparty computation – and evoked research on the minimum number of cards needed for several functionalities. Securely computing arbitrary circuits needs protocols for negation, AND and bit copy in committed-format, where outputs are commitments again. Negation just swaps the bit's cards, computing AND and copying a bit $n$ times can be done with six and $2n+2$ cards, respectively, using the simple protocols of Mizuki and Sone (FAW 2009). Koch, Walzer and Härtel (ASIACRYPT 2015) showed that five cards suffice for computing AND in finite runtime, albeit using relatively complex and unpractical shuffle operations. In this paper, we show that if we restrict shuffling to closed permutation sets, the six-card protocol is optimal in the finite-runtime setting. If we additionally assume a uniform distribution on the permutations in a shuffle, we show that restart-free four-card AND protocols are impossible. These shuffles are easy to perform even in an actively secure manner (Koch and Walzer, ePrint 2017). For copying bit commitments, the protocol of Nishimura et al. (ePrint 2017) needs only $2n+1$ cards, but performs a number of complex shuffling steps that is only finite in expectation. We show that it is impossible to go with less cards. If we require an a priori bound on the runtime, we show that the $(2n+2)$-card protocol is card-minimal.

Note: Full version (provides proof of Prop. 1, discussion of Fig. 1, slightly more discussion on open problems).

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in ASIACRYPT 2017
Keywords
Card-based protocolsCommitted formatBoolean ANDCOPYSecure computationCryptography without computers
Contact author(s)
alexander koch @ kit edu
History
2017-09-12: revised
2017-09-11: received
See all versions
Short URL
https://ia.cr/2017/863
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/863,
      author = {Julia Kastner and Alexander Koch and Stefan Walzer and Daiki Miyahara and Yu-ichi Hayashi and Takaaki Mizuki and Hideaki Sone},
      title = {The Minimum Number of Cards in Practical Card-based Protocols},
      howpublished = {Cryptology ePrint Archive, Paper 2017/863},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/863}},
      url = {https://eprint.iacr.org/2017/863}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.