[Resource Topic] 2018/951: The Landscape of Optimal Card-based Protocols

Welcome to the resource topic for 2018/951

The Landscape of Optimal Card-based Protocols

Authors: Alexander Koch


In the area of card-based cryptography one devises small and easy to perform protocols for secure multiparty computation using a deck of physical playing cards with indistinguishable backs, which can be run if no trusted computer is available, or in classroom settings to illustrate privacy notions and secure computations. Initiated by the “Five-Card Trick” of den Boer (EUROCRYPT 1989) for computing the AND of two players’ bits, and the work of Crépeau and Kilian (CRYPTO 1993) introducing committed format protocols which can be used as building blocks in larger computations, this is a field with a growing number of simple protocols. This paper devises two new AND protocols which are card-minimal w.r.t. specific requirements, and shows the card-minimality of the COPY protocol (necessary in arbitrary circuits, due to the physical nature of card-encoded bits) of Mizuki and Sone (FAW 2009) and the AND protocol of Abe et al. (APKC 2018). By this, we completely determine the landscape of card-minimal protocols with respect to runtime requirements (finite runtime or Las Vegas behavior with/without restarts) and practicality demands on the shuffling operations. Moreover, we systematize and extend techniques for proving lower bounds on the number of cards, which we believe is of independent interest.

ePrint: https://eprint.iacr.org/2018/951

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .